\input TR10WideFormat \input GeoMacros \input KineMacros 

\begfile{Frames.tex of December 6, 1983 6:39 pm --- Stolfi}

\titlestuff{

\title{Cartesian Coordinates and Frames}
\shorttitle{Frames and Coordinates}

\author{Jorge Stolfi}

\abstract{Random ramblings on Frames, cartesian coordinates, Affine and Euclidean geometries, etc. Put homogeneous coordinates in a separate file.}
 }
 
% ADDITIONAL MACROS

% reference tags

\def\GeoText{GeoText}

% search macros

\def\Prob{}

% miscellaneous

\def\footprobwidth{432} % width of text in foot problems
\def\footprob#1#2{
  \botinsert{\ctrpar\pagewidth pt{\framebox{\small
    \hbox par \footprobwidth pt{{\bf Exercise #1}: #2}}} }}
\def\^#1{\vbox to 1em{}^#1\!}
\def\naturals{\hbox{\bi N\/}}
\def\Tran{\mathop{\char t\char r\char a\char n}}
\def\Scale{\mathop{\char s\char c\char a\char l\char e}}
\def\XRot{\mathop{\char X\char r\char o\char t}}
\def\YRot{\mathop{\char Y\char r\char o\char t}}
\def\ZRot{\mathop{\char Z\char r\char o\char t}}

 \section{\Sec{-1}. Review of classical geometry}

 \subsection{\Sbsec{\Sec{-1}.0}. Introduction}

There is a subtle difference on outlook between the languages of ``classical'' and ``computational'' geometries. Classical geometry studies the properties of the {\it Eulidean} plane, which is thought to have no explicit frame of reference or unit of measure. While the concepts of parallelism and orthogonality are in a sense ``intrinsic'' properties of the Euclidean plane, notions such as a point lying above a line, a circle being centered at the origin, or a segment having unit length, are not defined within the theory. Moreover, the Euclidean plane has no intrinsic ``orientation'': notions such as ``clockwise order'', ``positive angle'', ``left side of a line'', and so forth, are not defined in classical geometry, except relative to a suitable object (for example, a reference frame, or three given non-colinear points) whose ordering or handedness is established by convention. In other words, the Euclidean plane has no standard ``viewing side'': all geometrical properties of an object are unaffected by reflection around a line, which is equivalent to ``flipping the plane over''.

By contrast, those concepts have ``natural'' definitions in computational geometry, and are routinely employed in definitions, proofs and algorithms. The reason is that virtually all computational geometry algorithms take their inputs and return their outputs in numerical form, as coordinates relative to some reference frame external to the algorithm. This frame then provides a natural reference object in terms of which all those concepts can be defined. We can describe this situation in a more formal way by saying that the objects dealt with in computational geometry belong to the ``Cartesian'' plane $\reals^2$ (the set of all ordered pairs of real numbers) rather than to the classical Euclidean one. In the Cartesian plane there is a distinguished point (the {\it origin} $(0,0)$), two distingushed directions (the {\it $x$- and $y$-directions}), and a natural unit of distance ($\dist[(0,0), (0,1)] = 1$). In this space we can also give simple algebraic definitions for such concepts as ``clockwise order'' and ``positive angle'', as we shall see in the remainder of this section.      

These remarks can be generalized for spaces of higher dimensions. For example, in classical Euclidean geometry ordinary three-dimensional space has no preferred orientation: that is, there is no way to define a ``right-handed frame'', except relative to some other reference frame. In computational geometry, such a refrence frame is always implied by the encoding of the inputs and outputs, and by reference to that frame we can define unambiguously such notions as ``right-handed basis'' and ``positively oriented tetrahedron''. 

In the remainder of this section, we will rigorously define those concepts and study their properties. We will also discuss other systems of coordinates that extend the Cartesian system and are more convenient than it in some applications: these include the {\it homogeneous} and {\it stereographic} coordiantes.    

 \subsection{\Sbsec{\Sec{-1}.1}. Axiomatic Geometries}

Let us begin with a review of the concepts of affine and Euclidean spaces, as they are understood in ``classical'' geometry. A complete and rigorous tratment of this subject is certainly outside the scope of this book, so we will imit ourselves to a brief and somewhat informal overview.

The {\it axiomatic method} is the basic language of classical geometry. Each of the many types of geometrical ``spaces'' is defined as a collection of objects that satisfy certain basic axioms, or {\it postulates}, from which all other properties of those objects are derived as theorems. So, for example, an Euclidean plane is usually defined as consisting of a set $\Sscr$ of points, and distinguished subsets of $\Sscr$ (the {\it lines} and {\it segments}), that obey the {\it Euclidean postulates for the plane.}

Actually, for any such theory there are infinitely many sets of postulates, all equivalent in the sense that  we can derive exactly the same theorems from any of them. Which set of is ``best'' is largely a matter of taste. We will not attempt to choose a standard set of postulates for this book. This will not be a significant problem, since we will only endeavor to prove a theorem of geometry if it is sufficiently non-obvious or if it gives valuable insight on the topic at hand. We will never carry a proof to details fine enough for the choice of postulates to be relevant.

For these reasons, in the summary below we will mostly ignore the classical axiomatic model, and include in the the definitions of geometric objects and spaces many properties that traditionally have been derived as theorems.

\note{Talk on the pros and cons of axiomatic approach. Mention extensions and alternate geometries.}

Readers who wish to pursue this subject further are referred to the extensive bibliography on classical geometry. It is not easy to pick the ``best'' introductory text in this sea of books; we would suggest Xxx??? [\GeoText] as a good starting point.   

 \subsection{\Sbsec{\Sec{-1}.2}. Maps}

The set of all function (or {\it maps}) from a set $X$ into a set $Y$ is denoted by $X\mapsto Y$. we denote by $x^M$ the image of an element  $x$ of $X$ by a map $M$ of $X\mapsto Y$. If $M\in X\mapsto Y$ and $N\in Y\mapsto Z$, their {\it composition} $MN$ consists of applying first $M$ and then $N$, so that $x^{MN}=(x^M)^N$, for all $x\in X$.

If $M$ is a map from $X\mapsto X$, we denote by $M^k$ the function that is equivalent to applying $M$ $k$ times. In other words, $M^0$ is the {\it identity map} $I
X$ (that takes every element of $X$ to itself), and $M^k=(M^{k-1})M=MM^{k-1}$ for integer $k>0$. If $M\in X\mapsto Y$ is one-to-one and onto, we can define its {\it inverse} $M^{-1}$, a map from $Y\mapsto X$ such that $MM^{-1}=I
X$, $M^{-1}M=I
Y$.

 \section{\Sec0. Affine geometry}

 \subsection{\Sbsec{\Sec0.1}. Affine metrics}

Let $\Sp$ be an arbitrary set. A function $f$ from $\reals\times\Sp\times\Sp\mapsto\Sp$ is called an {\it affine metric}\foot\dag{Warning: this nomenclature is probably quite non-standard.} on $\Sp$ if it has the properties listed below:

\begitems

\itemno{AM2.} $f(0,x,y)=x$, $f(1,x,y)=y$;

\itemno{AM2.} $f(\alpha,x,y)=f(\beta,x,y)$ iff $x=y$ or $\alpha=\beta$;

\itemno{AM3.} $f(\alpha,x,y)=f(1-\alpha,y,x)$ for all $x,y,\alpha$;

\itemno{AM4.} $f(\alpha, x, f(\beta, x, y))=f(\alpha\beta, x, y)$ 

 \subsection{\Sbsec{\Sec0.1}. Affine spaces}

For the purposes of this section, we will define a {\it line} as a topological space $l$ homeomorphic with the set of real numbers $\reals$. Among other things, the existence of such an homeomorphism allows us to tell, given any three distinct points on a line, which of the three lies {\it between} the other two. The set of all points on $l$ lying between two given points $a, b$ on it is the {\it segment $ab$} of $l$.

An {\it affine space of rank $r$} consists of a set $\Sp$ and a function from $\reals\times\Sp\times\Sp\mapsto\Sp$ satisfying the properties stated below. The elements of $\Sp$ will be called the {\it points} of the space. The function is the {\it affine metric. The elements of $\Sp$ are  {\it affine metric  (the {\it straight lines} of $\pi$) that satisfy the properties below: 

\begitems
\itemno{A1.} Any two straight lines are either parallel or have a single point in common.
\itemno{A2.} Given any two distinct points of $\pi$ there is exactly one straight line containing them.
\itemno{A3.} Given any straight line $l$, and any point $p$ of $\pi$, there is exactly one straight line of $\pi$ containing $p$ and not intersecting $l$.
\itemno{A4.} There are at least three points not on the same straight line.
\enditems

In the above, we say that two straight lines are {\it parallel} if they are either coincident or disjoint. The straight lines define a topological structure on $\pi$: a set $S\subset \pi$ is a {\it neighborhood} of a point $x$ if every line through $x$ conains a segment  If the congruence predicate is not specified, but all Euclidean axioms not connected with the latter still hold, the set $\Sscr$ is called an {\it affine space}. In affine spaces we can define the concept of parallel lines and segements, but not those concepts derived from general congruence, such as perpendicular lines, circles, congruence of angles, and so forth. However, by using Thales construction we can still define a more limited form of congruence, that applies only to parallel segments. More precidsely, we say that two such segments $ab$ on line $l$ and $a\pr b\pr$ on a parallel line $l\pr$ are {\it congruent} if ???

\footprob{\Prob{\Sbsec{\Sec0.2}.1}}{Show that an affine plane is homeomorphic to $\reals^2$.\lp
{\it Ans\/}: Take three points $o,a,b$ not on the same line. Let $l
x$ be the line through $o,x$ and $l
y$ the one through $o,b$. Let $p$ be any point of $\pi$. The parallel $s
x$ to $l
x$ through $p$ must meet $l
y$ at a single point. Proof: it cannot be coincident to $l
y$, for $l
y$ is not parallel to $l
x$. It cannot be disjoint from $l
y$, for otherwise $l
y$ and $l
x$ would be two distict parallels to $s
x$ through $o$. So, $s
x$ and $l
y$ meet at a point $p
y$. In the same way, the parallel $s
y$ to $l
y$ through $p$ meets $l
x$ at a point $p
x$\lp
}     

 \subsection{\Sbsec{\Sec0.2}. Vectors and vector bases}

 \subsection{\Sbsec{\Sec0.3}. Frames in Affine spaces}

A {\it coordinate frame} $G$ for a $d$-dimensional affine space $\Sp$ consists of a point $\^oG$ of $\Sp$ (the {\it reference point} or {\it origin} of the frame), and $d$ linearly independent vectors $\^1G,$ $\^2G,\ldots,$ $\^dG.$ The line passing through $\^oG$ and parallel to $\^iG$ is called the {\it $i$-th coordinate axis} of $G$.

Let $p$ be a point of $\Sp$. The {\it Cartesian coordinates of $p$ in the frame $G$} are the real numbers $p^G
1, p^G
2, \ldots, p^G
d$ such that
$$p = p^G
1\; \^1G + p^G
2 \;\^2G +\cdotss+ p^G
d\; \^dG + \^oG.
  \eqno(\Eq{\Sbsec{\Sec0.3}.1}$$
We will usually write Cartesian coordinates in {\it normalized homogeneous form}, that is, as a $1\times(d+1)$ array $\hop{p^G
1\;  p^G
2\; \ldots\; p^G
d \hom 1}$, that will be denoted by $p^G$.

The coordinates of a vector $v$ in the frame $G$ are the unique $d$ real numbers $v^G
1, v^G
2, \ldots, v^G
d$ such that $v = v^G
1 \^1G + v^G
2 \^2G + \cdotss+ v^G
d \^dG$ (note: without $\^oG$). In homogeneous form, the coordinates of a vector are written as the $1\times(d+1)$ array $v^G = \hov{v^G
1\;  v^G
2 \;\ldots\; v^G
d \; 0}$  (note: last element is $0$, not $1$).

To obtain the coordinates of the point $p$ and of the vector $v$ in a different frame $H$, we post-multiply $p^G$  and $v^G$ by the $(d+1)\times(d+1)$ array
$$G^H=\left[\matrix5{
  (\^1G)^H
1  (\^1G)^H
2  (\^1G)^H
d  \ldots  0\cr
  (\^2G)^H
1  (\^2G)^H
2  (\^2G)^H
d  \ldots  0\cr
  (\^dG)^H
1  (\^dG)^H
2  (\^dG)^H
d  \ldots  0\cr
    \vdots      \vdots      \vdots            \vdots\cr
  (\^oG)^H
1  (\^oG)^H
2  (\^oG)^H
d  \ldots  1\cr}\right]$$

where $(\^iG)^H
j$ (as defined in the previous paragraphs) is the $j$-th coordinate of the vector $\^iG$ in the frame $H$, and so forth.  That is, the rows of $G^H$ are the homogeneous coordinates of $\^1G, \^2G, \ldots, \^dG$, and $\^oG$ in the frame $H$.  The array $G^H$ is called the {\it matrix of $G$ in the frame $H$}.

Proof that the array multiplication really does what we claim: by carrying it out for a point p, we get the 1x4 array 

$$\eqalign{
  \left[\right. p^G
x\; (\^xG)^H
x + p^G
y\; (\^yG)^H
x + p^G
z\; (\^zG)^H
x +(\^oG)^H
x,\cr\vsk3
  \null         p^G
x\; (\^xG)^H
y + p^G
y\; (\^yG)^H
y + p^G
z\; (\^zG)^H
y + (\^oG)^H
y,\cr\vsk3
  \null         p^G
x\; (\^xG)^H
z + p^G
y\; (\^yG)^H
z + p^G
z\; (\^zG)^H
z + (\^oG)^H
z, 1]\cr}$$

We must check that

$$\eqalign{
  \null  (p^G
x (\^xG)^H
x + p^G
y (\^yG)^H
x + p^G
z (\^zG)^H
x + (\^oG)^H
x) \^xH\cr\vsk3
  + \;     (p^G
x (\^xG)^H
y + p^G
y (\^yG)^H
y + p^G
z (\^zG)^H
y + (\^oG)^H
y) \^yH\cr\vsk3
  + \;     (p^G
x (\^xG)^H
z + p^G
y (\^yG)^H
z + p^G
z (\^zG)^H
z + (\^oG)^H
z) \^zH + \^oH  = p \cr}$$
This is just a matter of expanding the expression above and using the identities below (from the definitions):

$$\eqalign{
  (\^xG)^H
x\; \^xH + (\^xG)^H
y\; \^yH + (\^xG)^H
z\; \^zH  = \^xG,\cr\vsk3
  (\^yG)^H
x\; \^xH + (\^yG)^H
y\; \^yH + (\^yG)^H
z\; \^zH  = \^yG,\cr\vsk3
  (\^zG)^H
x\; \^xH + (\^zG)^H
y\; \^yH + (\^zG)^H
z\; \^zH  = \^zG,\cr\vsk3
  (\^oG)^H
x\; \^xH + (\^oG)^H
y\; \^yH + (\^oG)^H
z\; \^zH  + \^oH = \^oG,\cr}$$

and finally

$$p^G
x \^xG + p^G
y \^yG + p^G
z \^zG + \^oG = p.$$

We have proved our claim, namely $p^G\cdot G^H = p^H$.
  
Similarly, to obtain the matrix $K^H$ of an arbitrary frame $K$ in the frame $H$, we post-multiply $K^G$ by the matrix $G^H$:

$$K^G G^H = K^H$$

(We can easily prove this by considering the effect of post-multiplying separately each row of $K^G$  by $G^H$.)

Most of the matrix products we will consider are of the form $p^A A^B B^C C^D$... or  $A^B B^C C^D$..., where the superscript of each term is the frame represented by the following term. For succintness, we will omit the superscripts in such products, and write just $pABC^D$ and $ABC^D$, respectively.

The {\it length} of a vector $v$ {\it relative to a frame} $G$ is by definition the real number $\sqrt{(v^G
x)^2 + (v^G
x)^2 + (v^G
x)^2}$.  The {\it distance} between two points $p, q$ {\it relative to $G$} is the length (rel. to $G$) of the vector $p - q$. Two vectors $u,v$ are said to be {\it orthogonal relative to $G$} if $u^G
x v^G
x + u^G
y v^G
y +u^G
z v^G
z = 0$. 

An {\it affine transformation} is a mapping of three space into itself that preserves parallelism (and therefore collinearity, ratios of areas, ratios of lengths along the same direction, etc.)  We denote by $pF$ the image of a point $p$ under an affine map $F$.  The image of a vector $v$ under $F$ is defined as being the vector $vF$ such that $(p+v)F = pF + vF$ for all points $p$.  The image of a frame $H$ under a mapping $F$ results by applying $F$ to the origin and vectors of $H$. The coordinates of $pF$ or $vF$ in a given frame $H $can be computed by post-multiplying $p^H$ or $v^H$, respectively, by the 4x4 array

$$\left[\matrix4{
  (\^xHF)^H
x  (\^xHF)^H
y  (\^xHF)^H
z  0\cr\vsk3
  (\^yHF)^H
x  (\^yHF)^H
y  (\^yHF)^H
z  0\cr\vsk3
  (\^zHF)^H
x  (\^zHF)^H
y  (\^zHF)^H
z  0\cr\vsk3
  (\^oHF)^H
x  (\^oHF)^H
y  (\^oHF)^H
z  1\cr}\right]$$
  
where $(\^xHF)^H
y$ (as usual) is the y-coordinate of the vector $(\^xH)F$ in the frame H, and so forth.  That is, the rows of this matrix are the homogeneous coordinates of $\^xHF, \^yHF, \^zHF$, and $\^oHF$ in the frame $H$ itself.  This matrix is precisely the matrix that describes the frame $HF$ in the frame $H$, that is, $(HF)^H$. Conversely, every pair of frames $G$, $H$ defines an affine map, that takes $G$ into  $H,$ and whose matrix is precisely $H^G$.

Furthermore, any $4\times 4$ matrix whose last column is $[0,0,0,1]^T$ is the matrix of an affine map in any given frame. It is worth pointing out that {\it the map depends on the frame, as well as on the matrix}; and, conversely, {\it the matrix depends on frame, as well as on the map}.

The {\it composition} of two affine mappings $F$ and $E$ is the mapping $FE$ that satisfies

$$ p (FE) = (pF)E $$

for all points $p$. It is easy to prove that such a vector exists, and also that its matrix in an arbitrary frame $G$ satisfies the equation

$$(FE)^G = F^G E^G.$$  

A {\it translation} is an affine map that corresponds to adding a fixed vector $v$ to every point of space. Its matrix in a frem $G$ is

$$ \left[\matrix4{
  1  0  0  0\cr\vsk3
  0  1  0  0\cr\vsk3
  0  0  1  0\cr\vsk3
  v
x^G  v
y^G  v
z^G  1\cr}\right] $$

We denote the matrix above by $\Tran(v
x^G, v
y^G, v
z^G)$. Expressing the same result in a different language, we can say that the image of a vector $v$ by an affine mapping $F$ is by definition the vector $vF$ such that for any point $p$ we have $(p+v)F=pF+vF$. The coordinates of that vector in a frame $G$ are given by 

$$(vF)^G = v^G F^G.$$  

An affine map is said to be a {\it scaling relative to a frame $G$} if its matrix in that frame has the form

$$ \Scale(\lambda
x, \lambda
y, \lambda
z)^G = \left[\matrix4{
  \lambda
x  0  0  0\cr\vsk3
  0  \lambda
y  0  0\cr\vsk3
  0  0  \lambda
z  0\cr\vsk3
  0  0  0  1\cr}\right] $$

Such a transformation maps the point with coordinates $p^G = [p
x^G\;\; p
y^G\;\; p
z^G\;\; 1]$ to the point with coordinates $p^G \Scale(\lambda
x, \lambda
y, \lambda
z)^G = [\lambda
x\cdot p
x^G\;\; \lambda
y\cdot p
y^G\;\; \lambda
z\cdot p
z^G\;\; 1]$, hence its name. The scaling is said to be {\it uniform} if $\lambda
x=\lambda
y=\lambda
z=\lambda$; in that case, we write the matrix above simply as $\Scale(\lambda)$. A uniform scaling with respect to $G$ simply ``enlarges'' or ``shrinks'' all distances and lengths (relative to $G$) by a factor $\lambda$, preserving directions and orthogonality (relative to $G$). If the axes of $G$ are pairwise orthogonal with respect to a frame $H$, then a uniform scaling by $\lambda$ relative to $G$ is also a uniform scaling by $\lambda$ relative to $H$.  

An affine transformation that keeps the origin of $G$ fixed and preserves all distances between points (rel. to $G$) is a {\it rotation relative} to $G$. Of particular interest are the {\it rotations around the $x, y$, or $z$ axis of $G$}, that keep fixed all points in the specified axis. These rotations have the matrices

$$ \XRot(\theta)^G=\ldots ,$$

$$ \YRot(\theta)^G=\ldots ,$$

and

$$ \ZRot(\theta)^G=\ldots ,$$

Note that an affine map $F$ that is a rotation relative to a frame $G$ may not be a rotation relative to another frame $H$. A sufficient condition for this to be true is that the axes of $G$ be all of the same length and pairwise orthogonal relative to $H$; that is, $G$ be obtained from $H$ by a  translation + rotation + uniform scaling (relative to $H$). 



 \subsection{\Sbsec{\Sec0.4}. Euclidean spaces}

 A {\it segment} of $l$ is a subset of $l$ that is homeomorphic to an open interval By definition consits of set $\Sscr$ of {\it points}, and a collection of subsets of $\Sscr$ (the {\it segments}), that satisfy a specific set of postulates. We need not concern ourselves with the precise form of those postulates. For our purposes, it suffices to say that they give $\Sscr$ a topological structure homeomorphic to that of the set of real numbers, with segments corresponding to  establish  We need only know that from those postulates All properties of the segments and points in a straight line that we know from classical geometry can be proved from these postulates and from the axioms of set theory. In particular, the postulates imply that the points of an Euclidean line can be put in one-to-one correspondence with the real numbers, in such a way that congruent segments correspond to two open inervals of equal length, and vice-versa.    

In axiomatic geometry, an {\it Euclidean line} consits of set $\Sscr$ of {\it points}, a collection of subsets of $\Sscr$ (the {\it segments}), and an equivalence relation ({\it congruence}) over the segments, that satisfy the so-called {\it Euclidean postulates for the line}. All properties of the segments and points in a straight line that we know from classical geometry can be proved from these postulates and from the axioms of set theory. In particular, the postulates imply that the points of an Euclidean line can be put in one-to-one correspondence with the real numbers, in such a way that congruent segments correspond to two open inervals of equal length, and vice-versa.    

An {\it Euclidean plane} consists of a set of points $\Sscr$, plus a collection of Euclidean lines whose points cover $\Sscr$, the two satisfying the so-called {\it Euclidean axioms for the plane}. ``Two distinct lines have at most one point in common,'' and ``there is exactly one line that contains two distinct given points,'' are two classical Euclidean postulates.

Many important geometrical and topological concepts can be defined in terms of the basic concepts of point, line and segment. Examples are the interior and boundary of a set, the ordering of three points along a line, the notion of a convex set, and many others. Chief among these is the property of two lines being {\it parallel} to each other, which means they are either coincident or have no common point\foot\dag{Most authors would not consider two coincident lines to be parallel. This may be related to (or derived from) the reluctance of ancient mathematicians to consider zero as a number. We believe our definition greatly simplifies the wording of most theorems and proofs.}. Two segments are parallel if they are contained in parallel lines. A theorem that can be proved from the Euclidean axioms says that two lines, each parallel to a third, are parallel each other; it follows that parallelism is an equivalence relation among lines and segments. The famous ``Fith Postulate'' of Euclidean plane geometry, that played an important historical role in the development of mathematics, states that given a line and a point, there is exactly one parallel to that line that passes through that point. 

A notion that {\em cannot} be defined exclusively in terms of the concepts of point, line and segment is that of two segments being {\it congruent}, that is, having the same length. Perpendicular lines, circles, congruent angles, regular polygons, and many other concepts are in a sense equivalent to the notion of congruence: if we consider any one of them to be a ``primitive'' concept, we can define all the others in terms of it. The Euclidean axioms specify several properties of this congruence relation, but they are not strong enough to define it unambiguously. In other words, in order to completely specify an Euclidean plane it is not enough to specify what are the points, lines, and segments: we must also specify which pairs of segements are congruent to each other (in a manner compatibel with the axioms).      

In general, we define an {\it Euclidean space of dimension $d$} (for any $d\in \naturals$) as consisting of a set of points $\Sscr$, plus a collection of Euclidean spaces of dimension $d-1$ (the $(d-1)$-dimensional hyperplanes of $\Sscr$) ({\it three-dimensional}) {\it Euclidean space} is defined in essentially the same way, as a set $\Sscr$ of points, plus a system of distinguished subsets ({\it planes}, {\it lines}, and {\it segments}) that satisfy the so-called {\it Euclidean axioms for the space}. The axioms are such that the points, lines, and segments contained in each plane constitute by themselves an Euclidean plane. In general, aconsists of set of points, a set of segments, and a system of $k$-dimensional    
 
Historically, Euclidean geometry was born as a ``physical'' theory, which purported to study the properties of ``physical'' space and ``physical'' solid objects. Euclid's axioms were supposed to be {\bf empirical} facts, simple enough to be accepted as true by everybody. \note{Why exactly did Euclid start with a {\it minimal} set of axioms? Philosophical reasons? Aesthetic pleasure? Concern about self-consistency? Academic game (i.e., ``let's see who can prove the most theorems with the fewest assumptions'')? }
 
 \section{\Sec1. [Extracts from letter to E. Bier]}

 \subsection{\Sbsec{\Sec1.1}. From Physics to Mathematics}

The ``Cartesian'' view:

\item Space is simply R3.

\item There is a natural WORLD frame: position (0,0,0), vectors (1,0,0), (0,1,0), (0,0,1).

\item A point, a vector, and the coordinates of a point wrt WORLD are the same thing.

\item There is a notion of ``true'' orthogonality (without reference to a frame): xX+yY+zZ=0. As a consequence you can compare non-parallel distances, and talk of a ``rotation", also without reference to a specific frame. 

\item There is a natural unit of distance: dist((000),(100))=1.

The ``Classical Physics'' or ``Euclidean'' view:

\item Space is physical space, or anything ``isomorphic'' to it.

\item Points are locations in this space.

\item Vectors are the same as translations: you can add (compose) two vectors,  or add (apply) a vector to a point, or subtract two points and get a vector, but not add two points, or talk of the ``tip of a vector".

\item There is no distinguished origin or direction: we may think of the WORLD frame as being chosen arbitrarily by the user.

\item SolidViews knows about and manipulates only the coordinates of points and vectors and frames wrt some frame (ultimately, WORLD), but the points and frames themselves are physical objects external to SolidViews.

\item There is a notion of ``true'' orthogonality, so e.g. you may ask the user to choose an orthogonal basis to be the WORLD. This also implies one can compare lengths even of non-parallel segments, so you can ask the user to pick WORLD with axes of equal length. You can also talk of a ``rotation'' without reference to a specific frame. 

\item There is no ``absolute'' unit of length, however, so you cannot ask the user to take WORLD with ``unit length'' vectors. Length and distance are always relative to some frame (see below).

The ``Linear Algebra'' ("Einstenian?") view:

\item Same as  ``classical physiscs", except that there is no notion of ``true'' orthogonality: You cannot even ask the user to choose WORLD orthogonal.

There are probably many other viewpoints you can think of, but my impression is that most of the time geometers/mathematicians/physicists/computergraphicians are talking about one of these. The Cartesian view is more economical and simpler in many ways, but the Euclidean view seems to be the most natural for non-mathematicians (You seem to be assuming this view, except in a couple of places.)

Of course which one you pick makes no real difference from the practical or mathematical point of view, but it determines the language you are allowed to use
in the ``basic notions'' section. For example, in the Cartesian viewpoint you define WORLD as being the frame $\la(000),(001),\ldots\ra$; in the Euclidean and Einstenian views you say WORLD is some arbitrary frame chosen by the user, and (in the Euclidean view only) you may require it to be orthogonal and with axes of equal length. Also (to be really nit-picking) in these two viewpoints the ``coordinates of a vector'' must be defined independently of the ``coordinates of a point", since vectors and points are very different beasts.

PS: If this seems nonsense to you, don't worry: it seems nonsense to mee, too, but I hoped that by writing it up I could see things more clearly (I still don't).

 \section{\Sec2. Additional geometric tools}

 % Begin

\digress{{\bf Note:} This section is here mainly for historical reasons. Logically, it belongs to much earlier in the book.}

\note{There is much duplication in what follows, particularly between the 2D and 3D sections. They probably should be developed in parallel. Some of the plane properties could go to exercises.}

 \subsection{\Sbsec{\Sec2.1}. The Cartesian plane}

The algorithmic character of computational geometry forces us to be explicit about ``sideness'' tests and constraints that are normally taken for granted in geometrical discussions. For example, in many algorithms it is necessary to test on which side of a line a given point lies, whether a point lies ``above'' another, or wheter an angle is clockwise or counterclockwise.

In classical plane geometry there is no direct way to distinguish the two half-planes determined by a line, or to distinguish a positive (counterclockwise) turn from a negative one. The classical Euclidean plane has no ``viewing side''; that is, all geometrical properties of an object are unaffected by reflection around a line, which is equivalent to ``flipping the plane over''\foot\dag{Moreover, the Euclidean plane has no distingushed point, direction, or unit of length: the properties of an object are unaffected by a rigid rotation or translation, or by an uniform change of scale.}. Sideness relations have to be introduced indirectly. For example, in Euclidean geometry it is meaningful to say whether two points are on the same side of a line, or on opposite sides of it; therefore, if we fix a ``reference'' point $r$, then given any line $\lscr$ not passing through $r$ we can distinguish the the side of $\lscr$ that contains $r$ from the one that does not.   

In computational geometry, however, we work on the {\it Cartesian plane} $\reals^2$, which has a richer structure than the Euclidean one. Specificaly, in the Cartesian plane there is a distinguished point (the origin), a distinguished unit of length (the distance between $(0,0)$ and $(0,1)$), a distinguished ``East'' direction (that of the positive $x$-axis) and a distingushed ``North'' direction orthogonal to it (that of the positive $y$-axis). We can therefore speak meaningfully of an horizontal segment, of the half-plane above a given line, of the extremal point of a set in the $+x$ direction, and so on.

 \subsection{\Sbsec{\Sec2.2}. Orientation of triangles}

In particular, the East and North directions allow us to distinguish  the ``clockwise'' and ``counterclockwise'' senses of rotation. Informally speaking, we are moving {\it clockwise} around a point $p$ if we are going in the general South direction with the line of motion passing East of $p$, or if we are going Eastwards with the line of motion passing North of $p$, and so forth. A triangle $abc$ is {\it clockwise oriented} (writeen $\CW(a,b,c)$) if we move that way around $c$ when going from $a$ to $b$. We write $\CCW(a,b,c)$ if the triangle $abc$ has the opposite ({\it counterclockwise}) orientation.\figspace3cm

These intuitive concept are neatly captured by a simple algebraic formula:

\definition{\Def{36}}{Three points $a$, $b$, and $c$ of $\reals^2$ are said to be {\it positively oriented}, written $\POS(a,b,c)$, if the determinant
$$\Delta(a,b,c)=\detmat{\matrix3{
  x
ay
a1\cr
  x
by
b1\cr
  x
cy
c1\cr}}\eqno(\Eq{36})$$
is positive. If $\Delta(a,b,c)$ is negative, we say $a,b,$ and $c$ are {\it negatively oriented}, and we write $\NEG(a,b,c)$.} 

It is a rather well-known fact that $\CCW(a,b,c)\eqv\POS(a,b,c)$, and $\CW(a,b,c)\eqv\NEG(a,b,c)$ for any triangle $abc$. However, considering the importance of these predicates for geometrical algorithms, it is worth spending a few lines to show this equivalence.

Let us assume first that the side $ab$ is not vertical, that is, $x
a\neq x
b$. The line of the motion from $a$ to $b$ will intercept the vertical line passing through $c$ at the ordinate
$$y\ast=y
a + {{x
a-x
c}\over{x
a-x
b}}(y
b-y
a).$$\figspace3cm

For the triangle $abc$ to be counterclockwise oriented we must have $y
ast>y
c$ when $x
a>x
b$, and $y
ast<y
c$ when $x
a<x
b$. This is equivalent to the condition
$$\left(y
a-y
c +{{x
a-x
c}\over{x
a-x
b}}(y
b-y
a)\right)(x
a-x
b)>0,$$
that is,
$$(y
a-y
c)(x
a-x
b) + (x
a-x
c)(y
b-y
a) >0.\eqno(\Eq{36A})$$

If $ab$ is vertical, we must have $y
a\neq y
b$. The line $ab$ cuts the horizontal line through $c$ at the abcissa $x
a=x
b$. For $abc$ to be counterclockwise oriented, we must have $x
a>x
c$ if $y
b>y
a$, and $x
a<x
c$ if $y
b<y
a$; that is, $ (x
a-x
c)(y
b-y
a) >0$. Since $(x
a-x
b)=0$, this condition is equivalent to inequality (\Eq{36A}). But that comes out to be
$$x
ay
b-y
ax
b+x
by
c-y
bx
c+x
cy
a-y
cx
a>0,$$
which is otained from (\Eq{36}) by expanding the determinant. We conclude that $\CCW(a,b,c)\eqv\POS(a,b,c)$. An entirely similar argument shows that $\CW\eqv\NEG$. 

The predicates $\POS$ and $\NEG$ are defined for any three points $a,b,c$, even if they are colinear or coincident. From the theory of determinants we have
$$\eqalignno{\Delta(a,b,c)=\detmat{\matrix3{
    x
a-x
cy
a-y
c0\cr\vsk3
    x
b-x
cy
b-y
c0\cr\vsk3
    x
cy
c1\cr}}\cr\vsk6
   \null=\detmat{\matrix2{
    x
a-x
cy
a-y
c\cr\vsk3
    x
b-x
cy
b-y
c\cr}}(\Eq{37A})\cr\vsk6
  \null=(x
a-x
c)(y
b-y
c)-(y
a-y
c)(x
b-x
c).(\Eq{38A})\cr}$$

Now let $u=a-c=(x
a-x
c,y
a-y
c)$ and $v=b-c=(x
b-x
c, y
a-y
c)$. From (\Eq{37A}), we see that 
$$\Delta(a,b,c)=\detmat{\matrix2{
    x
uy
u\cr
    x
vy
y\cr}}.\eqno(\Eq{39A})$$
The points $a,b,c$ are colinear if and only if $u$ is a multiple of $v$, or vice-versa. This is precisely the condition for the determinant above to be zero. So, {\it the three points are colinear if and only if $\POS(a,b,c)$ and $\NEG(a,b,c)$ are both false}\foot\dag{Note that this includes the case where two or more of the points are coincident.}. In those cases, we will define $\CCW(a,b,c)$ and $\CW(a,b,c)$ to be both false. With this convention, $\CCW$ and $\CW$ become identical to $\POS$ and $\NEG$.

Equation (\Eq{38A}) gives an efficient formula for computing $\CCW(a,b,c)$, that requires only five subtractions and two multiplications.

\note{discuss numerical stability}

\note{comment on other meanings of $\CCW$: positive area, positive angle, ccw as seen from an interior point, etc. Say that the affine maps that preserve $\CCW$ are those with positive determinant. In fact, (\Eq{39A}) is the determinant of the affine map that takes $(0,1),(1,0),(0,0)$ to $a,b,c$, respectively.}
 
Note that the order of the points $a,b,$ and $c$ is important. Intuitively, we expect the orientation of the triangle $bac$ to be opposite to that of $abc$. Indeed, by the elementary properties of determinants we have
$$\Delta(b,a,c)=\detmat{\matrix3{
  x
by
b1\cr
  x
ay
a1\cr
  x
cy
c1\cr}}=-\detmat{\matrix3{
  x
ay
a1\cr
  x
by
b1\cr
  x
cy
c1\cr}}=-\Delta(a,b,c),$$
so we conclude $\CCW(b,a,c)\eqv\CW(a,b,c)$. In general, we have the following:

\theorem{\Th{49A}}{Let $a\pr$, $b\pr$, and $c\pr$ be any permutation of the three points $a, b$, and $c$. Then $\POS(a\pr, b\pr, c\pr)$ is the equivalent to $\POS(a,b,c)$ or $\NEG(a,b,c)$, depending on whether the permutation is even or odd, respectively. That is, $$\twoline{\POS(a,b,c)\eqv\POS(b,c,a)\eqv\POS(c,a,b)}{2pt} {\eqv\NEG(c,b,a)\eqv\NEG(b,a,c)\eqv\NEG(a,c,b)}$$}

 \subsection{\Sbsec{\Sec2.2}. Oriented lines}

In the Cartesian plane $\reals^2$, we define an {\it oriented line} as a classical (non-oriented) line $\lscr$ endowed with a {\it normal direction} $\hat \lscr$, a unit vector perpendicular to $\lscr$. This enables us to distinguish the {\it left side} of $\lscr$, the half-plane of $\lscr$ into which $\hat\lscr$ points, from its {\it right side}.  

\note{Defining oriented lines in the 2SP requires care, since some lines have no normals, and the normal at the bottomm is different from that on top. Consider defining them as a line plus a distinction of which is the positive side. This has the advantage of being generalizable to circles as weel. The definition of (tangent) direction vector then becomes a problem.}

An oriented line $\lscr$ is uniquely determined by its normal vector and any point on $\lscr$. The line can also be specified by a {\it characteristic function}, a function $f$ of $\reals^2\mapsto\reals$ that is zero on $\lscr$, positive on its left side, and negative on its right side. An important example is the {\it signed distance} from $\lscr$ to an arbitrary point $p=(x,y)$, denoted by $\sdist(\lscr, p)$, that is the usual Euclidean distance between the two (measured perpendicularly to $\lscr$) taken with plus or minus sign depending on whether $p$ lies in the left or right side of $\lscr$.

\note{Consider defining characteristic functions so that they are positive on the right (and normals to be right-pointing, and the 1's column in $\Delta$ to be the first one. Note that this last suggestion inverts the meaning of $\POS$ for 3-space but not for $2-space$. It seems to make $\incircle$ and $\POS$ to agree.}

Let $\lscr$ be the oriented line with normal vector $\hat\lscr=(X, Y)$ and passing through the point $q=(x
q,y
q)$. For an arbitrary point $p=(x,y)$, the signed distance $\sdist(\lscr, p)$ is the component $\hat\lscr\cdot(p-q)$ of $p-q$ in the normal direction $\hat\lscr$.\figspace3cm

This gives
$$\eqalign{\sdist(\lscr, p)=X(x-x
q) +
  Y(y-y
q)\cr
\null=Xx + Yy  -
  (Xx
q+Yy
q)\cr}\eqno(\Eq{91A})$$
This shows that a that any oriented line has a characteristic function of the form $f(x,y)=X x+Y y+W$, that is, a first-degree polynomial in $x$ and $y$.

Conversely, any first-degree polinomial $f(x,y)=X x+Y y+W$ such that $X$ and $Y$ are not both zero is a characteristic function for some oriented line $\lscr$. This line has unit normal vector
$$\hat\lscr={1\over{\sqrt{X^2+Y^2}}}\,(X, Y),\eqno(\Eq{92A})$$
and passes through the point 
$$\lscr
0=-{W\over{X^2+Y^2}}\,(X, Y).\eqno(\Eq{93A})$$
This can be easily verified by substituting these values back into (\Eq{91A}): we get
$$\sdist(\lscr, p)={{Xx+Yy+W}\over{\sqrt{X^2+Y^2}}}.\eqno(\Eq{94A})$$
Since this has the same sign as $f(x,y)=Xx+Yy+W$, we conclude that the latter too is a characteristic function for $\lscr$. The line $\lscr$ is unique, and will be denoted by $\hol{X,Y\hom W}$. 

\note{The justification for this notation is by analogy with homogeneous coordinates of a point, $[x,y\hom w]$.}

When $X^2+Y^2=1$, the coefficients are said to be {\it normalized}, and the formulas above simplify to
$$\hat\lscr=(X, Y),$$
$$\lscr
0=(-WX, -WY),$$
and
$$\sdist(\lscr, p)=Xx+Yy+W,$$

The point $\lscr
0$ given by the formulas above is the point on $\lscr\hol{X,Y\hom W}$ that is closest to the origin. The distance from the origin to $\lscr$ is
$$\sdist(\lscr, O)={W\over{\sqrt{X^2+Y^2}}}\eqno(\Eq{95A})$$
or, if the coefficients are normalized,
$$\sdist(\pi, O)=W.$$


Clearly, $\hol{X, Y\hom W}$ and $\hol{X\pr, Y\pr\hom W\pr}$ denote the same oriented line if and only there is a {\it positive} real number $\alpha$ such that $X\pr=\alpha X$, $Y\pr=\alpha Y$, and $W\pr=\alpha W$. It follows that every oriented line has a unique set of normalized coefficients. The oriented line $\hol{-X, -Y\hom -W}$ passes through the same points as $\hol{X, Y\hom W}$, but has the opposite orientation: the left side of one is the right side of the other, and vice-versa. 

\footprob{\Prob{\Sbsec{\Sec2.2}.1}}{When and where does the line $\lscr=\hol{X, Y\hom W}$ intersect the three coordinate axes?}

\footprob{\Prob{\Sbsec{\Sec2.2}.2}}{What is the relationship between $\hol{X, Y\hom W}$ and $\hol{X, Y\hom -W}$?}

\note{Develop the analogous theory for points in homogenous coordinates}

 \subsection{\Sbsec{\Sec2.3}. The oriented line determined by two points}

\definition{\Def{37A}}{If $a,b$ are two distinct points of $\reals^2$, we define the {\it oriented line from $a$ to $b$} , or simply the {\it line $ab$}, as being the (classical) line through those two points, oriented so that a point $c$ is on its left (resp.right) side if and only if $a,b,$ and $c$ are positively (resp. negatively) oriented.}

To show that this line is always well defined, let us analyze how the predicate $\POS(a,b,c)$ depends on the point $c=$, when $a$ and $b$ are two (fixed) distinct points. If we expand the determinant (\Eq{36}) of definition \Def{36} by its last row, we get
$$\Delta(a,b,c)=Xx
c+Yy
c+W,\eqno(\Eq{51A})$$
where
$$X=+\detmat{\matrix2{
    y
a1\cr
    y
b1\cr}}=(y
a-y
b),$$
$$Y=-\detmat{\matrix2{
    x
a1\cr
    x
b1\cr}}=-(x
a-x
b),$$
and
$$W=+\detmat{\matrix2{
    x
ay
a\cr
    x
by
b\cr}}=x
ay
b-x
by
a.$$

Note that $X$, $Y$, and $W$ do not depend on the point $c$. As we observed, expression (\Eq{51A}) is zero when $c=a$ or $c=b$. On the other hand, since $a$ and $b$ are distinct, there is some point $c$ that is not colinear with them, and for this point $\Delta(a,b,c)$ is nonzero. It follows that not both of $X$ and $Y$ in (\Eq{51A}) are zero, so $\hol{X, Y\hom W}$ is a valid oriented line with characteristic function $f(x,y)=Xx+Yy+W=\Delta(a,b,(x,y))$. By definition \Def{36}, this line has the required properties. The only other oriented line through $a$ and $b$ is the opposite of this one; its left and right sides are reversed, and therefore it does not satisfy definition \Def{37A}. This shows the line $ab$ exists and is unique.

 \subsection{\Sbsec{\Sec2.4}. Orientation of tetrahedra}

In this book we will be concerned mostly with computational geometry on the plane. As a general rule, problems in three and higher dimensional spaces will be discussed quite informally, and only if they are a natural extension of their planar counterparts. However, it is often the case that a purely planar problems can be reduced, via some appropriate mapping of its input data, into a simpler geometrical problem in a space of higher dimension. For example, a line segment $pq$ on the plane can be viewed as a point $(x
p, y
p, x
q, y
q)$ in $\reals^4$. Such reductions justify the development of basic tools for computational geometry in spaces of higher dimension.

The $\POS$ and $negor$ predicates can be generalized to higher dimensional spaces in a most natural way:

\definition{\Def{37}}{We say that $k+1$ points $a
0, a
1, \ldots, a
k$, of $\reals^k$ (in that order) are {\it positively oriented} (denoted by $\POS(a
0, a
1, \ldots, a
k)$) if the determinant
$$\Delta(a
1, a
2, \ldots, a
{k+1})=\detmat{\matrix5{
    x
{01}x
{02}\ldotsx
{0k}1\cr\vsk3
    x
{11}x
{12}\ldotsx
{1k}1\cr\vsk3
    \vdots\vdots \vdots\cr\vsk3
    x
{k1}x
{k2}\ldotsx
{kk}1\cr}}\eqno(\Eq{38})$$
is positive. If $\Delta$ is negative, we say the points are {\it negatively oriented} (written as $\NEG(a
0, a
1, \ldots, a
k)$).}

In particular, given four points $a,b,c,$ and $d$ in three-dimensional space, we have 
$$\Delta(a,b,c,d)=\detmat{\matrix4{
    x
ay
az
a1\cr\vsk3
    x
by
bz
b1\cr\vsk3
    x
cy
cz
c1\cr\vsk3
    x
dy
dz
d1\cr}}\eqno(\Eq{38B})$$

The predicates $\POS(a,b,c,d)$ and $\NEG(a,b,c,d)$ are both false if $\Delta(a,b,c,d)$ is zero. Subtracting the last row of (\Eq{38B}) from the first three, we get
$$\Delta(a,b,c,d)=\detmat{\matrix3{
    x
a-x
dy
a-y
dz
a-z
d\cr\vsk3
    x
b-x
dy
b-y
dz
b-z
d\cr\vsk3
    x
c-x
dy
c-y
dz
c-z
d\cr}}.\eqno(\Eq{37B})$$
This determinant is zero if and only if the three vectors $a-d$, $b-d$ and $c-d$ are linearly dependent, that is, the four points $a,b,c,d$ lie on the same plane. This includes the cases where two or more of the points are coincident, or three of them are colinear.

\note{comment on other meanings of $\CCW$: the three vectors $a-d$, $b-d$, and $c-d$, in that order, constitute a right-handed basis. That is, the determinant (\Eq{37B}) of the linear transformation mapping the standard basis into those three vectors is positive.}

We remark in passing that the volume of the tetrahedron with vertices $a$, $b$, $c$ , and $d$ is ${1\over6}\leftv\Delta(a,b,c,d)\rightv$.

The value of $\Delta(a,b,c,d)$ can be computed by expanding (\Eq{37B}), along any row or column, into a linear combination of three $2\times 2$ determinants; this requires 9 mutiplications and 14 additions/subtractions in total.

\note{Gaussian decomposition of (\Eq{37B}) does not help at this point: requires 7 multiplications, 3 divisions, and 14 additions/subtractions. It gets better at higher dimensions, of course.}

\note{Remark on best ways to compute $\POS$; give code?}

Theorem \Th{49A} clearly generalizes to arbitrary dimensions. Let $a
0\pr, a
1\pr, \ldots, a
k\pr$ be a permutation of $a
0, a
1, \ldots, a
k$; then $\POS(a
0\pr, a
1\pr, \ldots, a
k\pr$ is equivalent to $\POS(a
0, a
1, \ldots, a
k)$ or $\NEG(a
0, a
1, \ldots, a
k)$, depending on whether the permutation is even or odd, respectively. In particular, $$\POS(a,b,c,d)\eqv\NEG(b,c,d,a)\eqv\POS(c,d,a,b)\eqv\NEG(d,a,b,c).$$  

 \subsection{\Sbsec{\Sec2.5}. Oriented planes}

The concept of oriented line extends quite naturally to Euclidean spaces of more than two dimensions. In the three-dimensioanl space $\reals^3$, we define an {\it oriented plane} $\pi$ as a plane (in the classical sense) endowed with a {\it normal direction} $\hat \pi$, a unit vector perpendicular to it. We are therefore able to distinguish the {\it left half-space} of $\pi$, into which $\hat \pi$ points, from its {\it right half-space}. Like a line, an oriented plane $\pi$ is uniquely determined by its normal vector and a point on $\pi$.

A {\it characteristic function} for $\pi$ is a function from $\reals^3\mapsto\reals$ that is zero, positive, or negative depending on whether the argument is on $\pi$, on its left half-space, or on its right-half-space, respectively. The signed distance from $\pi$ to a point $p$ is defined exactly as for oriented lines, and it too is given by $\sdist(\pi, p)=\hat\pi\cdot(p-q)$ where $q$ is any point on $\pi$.\figspace4cm 

If $\hat\pi=(X,Y,Z)$ and $p=(x,y,z)$, we have
$$\sdist(\pi, p)=Xx + Yy +Zz - (Xx
q+Yy
q+Zz
q),\eqno(\Eq{91B})$$
proving that every oriented plane has a characteristic function that is a first-degree polynomial in $x$, $y$ and $z$. Conversely, any such polynomial $f(x,y,z)=Xx+Yy+Zz+W$ (with $X,Y,$ and $Z$ not all zero) is a characteristic function for a unique oriented plane, denoted  by $\hol{X,Y,Z\hom W}$. Its unit normal vector is
$$\hat\pi={1\over{\sqrt{X^2+Y^2+Z^2}}}\,(X, Y, Z),\eqno(\Eq{92B})$$
and it passes through the point 
$$\pi
0=-{W\over{X^2+Y^2+Z^2}}\,(X, Y, Z).\eqno(\Eq{93B})$$
The coefficients are  said to be {\it normalized} if $X^2+Y^2+Z^2=1$.

As in the case of lines, the planes $\hol{X, Y, Z\hom W}$ and $\hol{X\pr, Y\pr, Z\pr\hom W\pr}$ denote the same oriented plane if and only there is a {\it positive} real number $\alpha$ such that $X\pr=\alpha X$, $Y\pr=\alpha Y$, $Z\pr=\alpha Z$, and $W\pr=\alpha W$. It follows that every oriented plane has a unique set of normalized coefficients. The oriented plane $\hol{-X, -Y, -Z\hom -W}$ passes through the same points as $\hol{X, Y, Z\hom W}$, but has the opposite orientation: the left half-space of one is the right half-space of the other, and vice-versa. 

\footprob{\Prob{\Sbsec{\Sec2.5}.1}}{When and where does the plane $\pi=\hol{X, Y, Z\hom W}$ intersect the three coordinate axes?}

\footprob{\Prob{\Sbsec{\Sec2.5}.2}}{What is the relationship between $\hol{X, Y, Z\hom W}$ and $\hol{X, Y, Z\hom -W}$?}

\footprob{\Prob{\Sbsec{\Sec2.5}.3}}{Generalize oriented plane and related concepts to higher dimensions}

\note{Develop the analogous theory for points in homogenous coordinates}

 \subsection{\Sbsec{\Sec2.6}. The oriented plane through three given points}

The oriented plane through three given points is also defined by a generalization of definition \Def{37A}:

\definition{\Def{37B}}{If $a,b, c$ are three non-colinear points of $\reals^3$, we define the {\it oriented plane through $a$, $b$ and $c$} , or simply the {\it plane $abc$}, as being the (classical) plane through those three points, oriented so that a point $d$ is on its left (resp.right) half-space if and only if $a,b, c,$ and $d$ are positively (resp. negatively) oriented.}

It is easy to prove that this plane always exists and is unique. Its characteristic function is
$$\Delta(a,b,c,d)=Xx
d+Yy
d+Zz
d+W,\eqno(\Eq{51B})$$
(as a function of $d$), where
$$X=-\detmat{\matrix3{
    y
az
a1\cr
    y
bz
b1\cr
    y
cz
c1\cr}},$$
$$Y=+\detmat{\matrix3{
    x
az
a1\cr
    x
bz
b1\cr
    x
cz
c1\cr}},$$
$$Z=-\detmat{\matrix3{
    x
ay
a1\cr
    x
by
b1\cr
    x
cy
c1\cr}},$$
and
$$W=+\detmat{\matrix3{
    x
ay
az
a\cr
    x
by
bz
b\cr
    x
cy
cz
c\cr}}.$$

This plane is such that the triangle $abc$ is seen as counterclockwise orietned to an observer anywhere on its left side.

 \section {\Sec3. Affine transformations}

 % Begin

Intuitively speaking, we can define a {\it geometric transformation} as a mapping from one space into another that takes geometric objects into other geometric objects. Such transformations have been studied quite extensively by generations of mathematicians, and F. Klein's school regarded them as the true foundation of geometry. Isometries of the plane (rotations, reflections and translations) were taken for granted by Euclid himself, and the concepts of scaling and shearing transformations were clearly familiar to him.

For lack of time and space, a satisfactory introduction to geometric transformations will be left to some future chapter; for now, we will restrict ourselves to the definitions and notation strictly necessary for the rest of this chapter.

The simplest transformation is the identity $I$, that maps every point into itself. A {\it translation} by a vector $v$, of course, is the map that takes every point $x$ of the plane to the point $x+v$. A translation is a special case of an  {\it isometric transformation}, or {\it congruence}, a geometric map that preserves the distances between all pairs of points. Rotations and reflections around a line are also isometric transformations. It is easy to see that isometries must map straight lines into straight lines, and preserve the angles between them. Indeed, in classical geometry two figures related by a congruence are usually considered to be the same figure.

A slightly more general kind of geometrical mapping is a {\it similarity transformation} that is basically an isometry followed by a change of scale. A similarity will map straight lines into straight lines, angles into equal angles, and in general figures into similar figures (hence its name). Generalizing in a different way, we get a class of transformations that preserve straight lines and areas but not necessarily angles and distances; we may call them {\it unimodular transformations}. The ``vertical shearing'' that maps a point $(x, y)$ to the point $(x, y+\alpha x)$ (for some nonzero constant $\alpha$) is an element of this class.

The {\it affine transformations} constitute a more general class of mappings, including all of the above as proper subclasses. General affine maps take straight lines into straight lines, but do not in general preserve angles, distances or areas (they preserve {\it ratios} of areas, however). The affine maps that leave the origin fixed are the well-known {\it linear transformations} of $\reals^2$. A general affine transformation consists of a linear map followed by a translation.

An affine transformation $T$ is {\it degenerate} if it is not one-to-one; this happens if and only if two distinct points have the same image under $T$. Given a pair of non-degenerate triangles $abc$ and $a\pr b\pr c\pr$, there is exactly one (non-degenerate) affine transformation that maps $a$ to $a\pr$, $b$ to $b\pr$, and $c$ to $c\pr$.
\figspace 3cm
Conversely, any non-degenerate affine map of the plane will take the points $(0, 0)$, $(0, 1)$ and $(1, 0)$ to the vertices of a non-degenerate triangle. In this chapter, all affine maps will be assumed one-to-one unless stated otherwise.

We will denote by $p^T$ the image of a point $p$ by the affine transformation $T$. If $X$ is a set of points, $X^T$ is the set $\rset{p^T\relv p\in X}$. The image of a line $\lscr$ is written $\lscr^T$; its orientation is such that a point $p$ is on $\lscr$ (resp. to the left of $\lscr$) if and only if $p^T$ is on $\lscr^T$ (resp. to the left of $\lscr^T$).
\figspace 4cm

Note that if $\lscr$ is oriented from $a$ towards $b$, then depending on the map $T$ the image $\lscr^T$ may be oriented from from $a^T$ to $b^T$ or from $b^T$ to $a^T$. It can be shown that if this ``orientation reversal'' happens for one line, it happens for all of them. The mapping $T$ is said to be {\it odd} if that occurs, and {\it even} otherwise. An affine transformation is odd if and only if it maps a counterclockwise triangle into a clockwise one.

We define the image of a state $s$ under a mapping $T$ as the state $s^T$ with position $\po s^T$ and tangent line $(\ta s)^T$.
\figspace 4cm

The image of a turn of move $[r\to s]$ under an affine map $T$ will be precisely the turn or move $[r^T\to s^T]$. This is not entirely obvious at first sight; it follows from the fact that affine transformations preserve the ``betweeness'' properties of points and oriented lines, i.e. they map segments into segments and proper angles into proper angles. More precisely, a point $x$ belongs to the segment $(p\sp q)$ if and only if $x^T$ is in $(p^T\sp q^T)$. Similarly, if the three lines $r, s$ and $t$ are such that $\di t$ is in the proper arc $(\di r\sp \di s)$, then the same relationship holds for their images under $T$.
\figspace 3cm

The image $S^T$ of a tracing $S$ under an affine map is then defined quite naturally as the result of applying $T$ to every turn and move of $S$. For example, if $T$ is translation by a vector $v$, then $S^T$ will be what we would expect.
\figspace 3cm

Note that if $T$ is an odd affine map, then the move $[r\to s]^T$ will be backwards if $[r\to s]$ is forward, and vice-versa. In the same way, an odd map will change clockwise turns into counterclockwise ones, and conversely. (If you are beginning to feel confused, don't worry: all maps we will use in this chapter are even).

We will denote by $-I$ the {\it sign reversal} transformation that maps every point $(x, y)$ to its opposite $(-x, -y)$ across the origin. This transformation corresponds to a $180\deg$ turn around the origin, or to two successive reflections, one about each coordinate axis. In spite of the fact that it maps every line to one with opposite orientation, it is an even mapping (can you see why?). One of its properties is that any tracing which is centrally symmetric (e.g., a circle) is identical to its image under $-I$, up to orientations and directions of traversal.
\figspace 3cm

The affine maps are closed under composition, and the same is true of the other classes of transformations defined above. In other words, if $R$ and $S$ are arbitrary affine maps, then there is a third affine map $R S$ such that $x^{R S}=(x^{S})^R$ for all $x$ in the plane. We denote the translation through a vector $v$ by just $v$, so $x^{v\,-I}$ is what we obtain by applying the sign reversal transformation $-I$ to $x$, and then translating the result by $v$\foot\dag{Do not try to read $v\,-I$ as the difference between $v$ and $I$; the similarity of notation is just an unlucky coincidence.}. This particular transformation will play an important role in the next section.

It is interesting to consider the interaction between affine maps and convolution of polygonal tracings. If $T$ is a linear map, then $A^T\ast B^T=(A\ast B)^T$. This is not true for general affine maps, in particular for translations; however, it is the case that $A^v\ast B^w=(A\ast B)^{(v+w)}$, for any vectors $v$ and $w$. Since sign reversal is a linear map, we have $A^{v\,-I}\ast B^{w\,-I}=(A\ast B)^{(v+w)\,-I}$.
\figspace 4cm

 \section{\Sec0. Basics}

 \subsection{\Sec0.2. Cartesian spaces}

 \subsection{\Sec0.3. Dot product}

We denote by $u\cdot v$ the scalar product $u
1v
1+u
2v
2+\cdots+u
nv
n$ of two vectors $u=(u
1,u
2,\ldots,u
n)$ and $v=(v
1,v
2,\ldots,v
n)$ of $\reals^n$. For $i=1,2,\ldots, n$, we define the {\it $i$-th standard basis vector} $\bv{i}$ as having components $(\bv{i1}, \bv{i2}, \ldots, \bv{in})$, where $\bv{i\,j}$ is $1$ if $i=j$ and $0$ otherwise. Then, for any vector $v=(v
1,v
2,\ldots,v
n)\in\reals^n$ and any $j\in [1\isp n]$ we have $v\cdot \bv{j}=v
j$, and 
$$v=\sum
{j\in[1\isp n]}v
j\,\bv{j}
   =\sum
{j\in[1\isp n]}(v\cdot \bv{j})\,\bv{j}.\eqno(\Eq2)$$ 

 \subsection{\Sec0.4. Linear maps}

A map $M\in \reals^n\mapsto\reals^n$ is {\it linear} if $(u+v)^M=u^M+v^M$ and $(\alpha v)^M =\alpha(v^M)$ for all $u,v\in\reals^n$ and all $\alpha\in \reals$. In fact, for any $v=(v
1,v
2,\ldots,v
n)\in\reals^n$ we have
$$\eqalign{
  v^M=\biglp\sum
{j\in[1\isp n]}v
j\bv{j}\bigrp^M\cr
  \null=\sum
{j\in[1\isp n]}v
j(\bv{j}^M).\cr
  \null=\sum
{k\in[1\isp n]}v
k(\bv{k}^M).\cr
  \null=\sum
{k\in[1\isp n]}v
k\sum
{j\in[1\isp n]}(\bv{k}^M\cdot\bv{j})\,\bv{j}\cr
  \null=\sum
{j\in[1\isp n]}\bigglp \sum
{k\in[1\isp n]}v
k (\bv{k}^M\cdot\bv{j})\biggrp\,\bv{j}.\cr}$$
That is, the $j$-th coordinate of $v^M$ is given by
$$\sum
{k\in[1\isp n]}v
k (\bv{k}^M\cdot\bv{j}).$$
If we consider a vector of $\reals^n$ as a $1\times n$ array, then $v^M$ is obtained by post-multiplying the $1\times n$ array of $v$ by the $n\times n$ array
$$\left[\;\matrix4{
  \bv1^M\cdot\bv1  \bv1^M\cdot\bv2  \cdotsm  \bv1^M\cdot\bv3 \cr
  \bv2^M\cdot\bv1  \bv2^M\cdot\bv2  \cdotsm  \bv2^M\cdot\bv3 \cr
       \vdots          \vdots                    \vdots      \cr
  \bv3^M\cdot\bv1  \bv3^M\cdot\bv2  \cdotsm  \bv3^M\cdot\bv3 \cr
    }\;\right]$$
by the usual row-times-column rule. This array is unique and specifies $M$ completely; it is called the the {\it matrix of $M$}.
  
The {\it determinant} $\det M$ of $M$ is by definition that of its matrix. The determinant is zero if and only if $M$ is not one-to-one ({\it singular}). Otherwise $M$ is said to be {\it positive} or {\it negative} depending on whether $\det M>0$ or $\det M <0$, respectively. The inverse $M^{-1}$ of a non-singular linear map is also linear, and its determinant is $1/(\det M)$.

 \subsection{\Sec0.5. The dual space}

\par\vfill\eject\end


�ʘJš
œ:˜:š
œ<˜<š
œ
˜
Jš
œM˜MJ˜J˜“
—Jš
œ˜—
procš
œ˜š
œ˜Kš
œ˜—š
œ˜Kš
œ˜—š
œ˜KšœÞ
Ïfœþ
˜ô——š
œ3˜3š
œ0˜0J˜ÉJ˜ËJ˜”J˜½—š
œ8˜8J˜ J˜…J˜ÄJ˜â
J˜eJ˜þ
—š
œ(˜(Kš
œÙ˜ÙKš
œœ˜œ——š
œ#˜#š
œ/˜/J˜î
˜
J˜*J˜HJ˜DJ˜C——š
œ.˜.J˜¦J˜þJ˜½J˜ŠJ˜™—Jš
œ9˜9š
œ8˜8Jš
œÒ˜ÒJš
œ¸˜¸Jš
œø˜øJš
œ²
˜²
Jš
œ¢˜¢Jš
œÆ˜ÆJš
œw˜wJš
œ¸˜¸Jš
œ˜Jš
œ±˜±Jš
œo˜oJš
œÉ˜ÉJš
œ˜Jš
œ5˜5Jš
œ¸
˜¸
Jš
œ˜Jš
œq˜qJš
œ¯˜¯Jš
œ÷˜÷Jš
œñ˜ñJš
ϖ
˜ñ
Jš
œÒ˜ÒJš
œ¡˜¡Jš
œ\˜\Jš
œ˜Jš
œ�
˜�
Jš
œ˜Jš
œˆ
˜ˆ
Jš
œ…
˜…
Jš
œÄ˜ÄJš
œ˜Jš
œm˜mJš
œ½
˜½
Jš
œ¦˜¦Jš
œÄ˜ÄJš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œç˜çJš
œ
˜
—š
œ1˜1J˜´J˜²J˜òJ˜»	J˜¼J˜ÙJ˜†——š
œ5˜5š
œ<˜<Jš
œ˜Jš
œ˜Jš
œ[˜[Jš
œV˜VJš
ϧ
˜ß
Jš
œ@˜@Jš
œ1˜1Jš
œA˜AJš
œ*˜*Jš
ϯ
˜Ø
Jš
œ~˜~Jš
œÙ
˜Ù
Jš
œÕ˜ÕJš
œÂ
˜Â
Jš
œ-˜-Jš
Ϫ
˜™
Jš
œŒ˜ŒJš
œ¸˜¸Jš
Ϣ
˜¢
——š
œ.˜.˜
J˜}J˜Â
—š
œ4˜4J˜÷J˜ÏJ˜ç—š
œ9˜9J˜ïJ˜KJ˜øJ˜‰J˜ü
J˜µJ˜ÈJ˜ÆJ˜²J˜Š
J˜#J˜‰J˜÷—š
œ/˜/J˜àJ˜òJ˜ÜJ˜ÂJ˜žJ˜�J˜´J˜qJ˜·
J˜œJ˜îJ˜€
J˜rJ˜I—š
œK˜KJ˜ÛJ˜‚J˜ä—š
œ:˜:J˜žJ˜iJ˜©J˜ñ
J˜ÍJ˜‰J˜Š
J˜å
J˜Á
J˜9J˜¦—š
œ0˜0J˜¡J˜ªJ˜œJ˜¸J˜‚
J˜xJ˜iJ˜I—š
œN˜NJ˜kJ˜üJ˜ùJ˜z——š
œ+˜+š
œ
˜
Jš
œ�˜�J˜ï
J˜¢J˜…J˜åJ˜ÒJ˜öJ˜ÍJ˜Ž
J˜„J˜ý
J˜ÇJ˜ÉJ˜©J˜²——š
œ˜Kš
œ)˜)š
œ$˜$Kš
œ¶˜¶—š
œ$˜$Kš
œø	˜ø	Kš
œü˜ü—Kš
œ'˜'—Jš
œ˜J˜—…—ãÚèä