\title{INTERMEZZO}{I}{More geometric tools}
\shorttitle{More geometric tools}
% Begin
% Begin
Let us now suspend for a while the discussion of geometric algorithms, and return to a topic we treated briefly in section \Sbsec{\Sec{\Ch4.2}.1}: namely, the ``primitive'' operations of computational geometry, and their proper implementation. We begin by observing 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, cannot be defined in classsical geometry, except relative to a suitable object (for example, a reference frame, or three given non-colinear points) whose ordering or handedness are 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, in computational geometry all those concepts have ``natural'' definitions, and are routinely employed in definitions, proofs and algorithms. The reason is that in computational geometry virtually all 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 not to the Euclidean plane but to the ``Cartesian space'' $\reals^2$, the set of all ordered pairs of real numbers. In this set there is a distinguished point (the {\it origin} $(0,0)$), two distingushed directions (the {\it $x$-} and {\it $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{\Ch{I}.\Sbsec{\Sec1.0}. Basic notions of Euclidean geometry}
Euclidean geometry is the standard example of an axiomatic theory, in which the basic objects of study are defined indirectly by a collection of fundamental properties, the {\it axioms} or {\it postulates}, that they are assumed to posess. All other objects studied by the theory are defined in terms these basic ones, and all its theorems can be derived from the postulates by the rules of formal logic.
The postulates of plane Euclidean geometry define in this way four basic notions: {\it point}, {\it line}, {\it betweeness} (argh!), and {\it congruence}. The postulates say that lines are particular sets of points, having specific properties such as ``there is exactly one line containing two distinct given points'', and ``two distinct lines have at most one point in common''. We will say that two lines are {\it parallel} if they are coincident or disjoint\foot\dag{This is non-standard but seems to be more convenient for computational purposes.}. The famous Fifth Postulate of Euclid, which played such an important part in the development of mathematics, states that ``for any given line and any given point, there is exactly one parallel to that line containing that point''.
The notion of``betweeness'' is embodied in the ternary predicate ``point $b$ lies between $a$ and $c$''. The Euclidean axioms restrict this predicate to be true only if $a, b, c$ are distinct and on a common line. The ({\it open}) {it segment} $ac$ is by definition the set of all $b$'s satisfying this predicate. The open segments of a line give it a topological structure, equivalent to the standadrd topology of the real numbers.
The Euclidean postulates describe ``congruence'' as an equivalence relation defined among subsets of the plane. Intuitively, two subsets (figures) are congruent if one can be superimposed on the other by a rigid motion. The notion of congruence allows us to define such concepts as perpendicular lines, equilateral triangles, circles, ratios of lengths and areas, and many others.
Euclidean geometries dealing with spaces of higer dimensions require relatively minor extensions to the postulates for the plane. For example, an {\it Euclidean three-space} can be defined as a set of points plus a system of subsets, each by itself an Euclidean plane, all satisfying additional properties such as ``there is exactly one plane containing any two distinct intersecting lines'', ``two distinct planes are either disjoint or have a single line in common'', and so forth.
\digress{Actually, there are infinitely many valid sets of ``Euclidean postulates'', each set describing its own collection of ``basic'' objects and predicates. Those axiom sets are all equivalent, in the sense that we can derive exactly the same definitions and theorems from any of them. Which set of is ``best'' is largely a matter of taste. In this book, we will not attempt to choose a standard set of postulates. We will prove a purely geometric result only if that result is not intuitively obvious, or if its proof gives valuable insight into the problem at hand. We will never carry a proof to details fine enough for the choice of postulates to be relevant.}
{\bf STOPPED HERE November 1, 1983 5:41 pm}
\note{$d$-dimensional spaces. Hyperplanes, parallelism.}
\note{ratio of lengths of segments}
\note{translations (vectors), ratios of lengths of vectors}
\note{Vector algebra: product of a vector by a real number, sum (composition) of vectors, orthogonal vectors. Linear independence.}
Junk: An {\it Euclidean space} of an arbitrary integer dimension $d>2$ can be defined as a set of points with a system of subsets (each a $k$-dimensional Euclidean space with $0\leq k<d$), all satisfying the postulates of $d$-dimensional plane geometry.
\subsection{\Ch{I}.\Sbsec{\Sec1.1}. Frames and Cartesian spaces}
\definition{\Def0}{A {\it frame} $F$ in an Euclidean space $\Sscr$ of dimension $d$ consists of a point $\forg F$ of $\Sscr$, and a sequence of $d$ vectors $\fvec F1,\fvec F1,\ldots, \fvec Fd$ of $\Sscr$.}
The frame is said to be {\it orthogonal} if its vectors are pairwise perpendicular, and {\it isometric} if they have the same length. If the vectors are not lineraly independent, the frame is said to be {\it degenerate}.
\definition{\Def{0A}}{The {\it coordinates} of a point $p$ of $\Sscr$ in a non-degenerate frame $F$ are the real numbers $\fco pF1, \fco pF2, \ldots, \fco pFd$ such that
$$p = \forg F+ \sum{i\in[1\isp d]} \fco pFi \fvec Fi\eqno(\Eq0)$$
{\bf STOPPED HERE November 1, 1983 6:02 pm}
The reader is certainly familiar with the notion of a coordinates and coordinate sytems, in which a, which is determined by an arbitrarily chosen orthonormal reference frame in the Euclidean plane. By a {\it frame} in an euclidean space $\Sscr$ of dimension $d$ we mean a point of $\Sscr$ (the origin) and an ordered $d$-tuple of vectors of $\Sccr$\foot\ddag{A Vector
The reader is certainly familiar with the notion of a coordinates and coordinate sytems, in which a, which is determined by an arbitrarily chosen orthonormal reference frame in the Euclidean plane. By a {\it frame} in an euclidean space $\Sscr$ of dimension $d$ we mean a point of $\Sscr$ (the origin) and an ordered $d$-tuple of vectors of $\Sccr$\foot\ddag{A Vector
\definition{\Def1}{The {\it Cartesian space of dimension $d$} is the set $\reals^d$ of all ordered $d$-tuples of real numbers. The elements of $\reals^d$ will also be called its {\it points}.}
Of particular interest to us will be the cases $d=2$ (the {\it Cartesian plane}) and $d=3$ (the {\it Cartesian three-space}). Following the universal practice, the components of a point $a$ of $\reals^2$ or $\reals^3$ will be called the {\it $x$-, $y$-, and $z$-coordinates} of $a$, in that order, and denoted by $xa$, $ya$, $za$\foot\dag{When $d$ is unspecified or greater than 3, the components of a point $a\in\reals^d$ will be called {\it first, second, $\ldots$, $i$-th, $\ldots$}, and denoted by $a1, a2, \ldots, ai, \ldots$.\note{Not elegant but convenient. What do you think? Would $ax$, $ay$, $az$ be too funny?}}.
The notion of paralleism
A {\it translation} can be defined as a map of the set $\Sscr$ into itself that takes every line to a parallel or coincident line. A translation is also called a {\it vector}
A closely related one is the notion of a point lying between Two notions are also of objects called {\it points}, The notions of {\it parallelis {\it vector} in {\it frame} in an euclidean space $\Sscr$ of dimension $d$ we mean a point of $\Sscr$ (the origin) and an ordered $d$-tuple of vectors of $\Sccr$\foot\ddag{A Vector
Outseide of this section, the unqualified temrs {\it plane} and {\space} will refer to the Cartesian ones.
In general,
\definition{\Def2}{The {\it Cartesian distance} between two points $p,q\in\reals^d$ is defined as
$$\dist(p,q) = \sqrt{\sum{i\in[1\isp d]}(pi-qi)^2}$$}
{\bf STOPPED HERE October 20, 1983 6:49 pm}
\section{\Ch{I}.\Sec2. 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.
\figspace 3cm
These intuitive concepts 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{
xaya1\cr
xbyb1\cr
xcyc1\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, $xa\neq xb$. The line of the motion from $a$ to $b$ will intercept the vertical line passing through $c$ at the ordinate
$$y\ast=ya + {{xa-xc}\over{xa-xb}}(yb-ya).$$\figspace3cm
For the triangle $abc$ to be counterclockwise oriented we must have $y^\ast>yc$ when $xa>xb$, and $y^\ast<yc$ when $xa<xb$. This is equivalent to the condition
$$\left(ya-yc +{{xa-xc}\over{xa-xb}}(yb-ya)\right)(xa-xb)>0,$$
that is,
$$(ya-yc)(xa-xb) + (xa-xc)(yb-ya) >0.\eqno(\Eq{36A})$$
If $ab$ is vertical, we must have $ya\neq yb$. The line $ab$ cuts the horizontal line through $c$ at the abcissa $xa=xb$. For $abc$ to be counterclockwise oriented, we must have $xa>xc$ if $yb>ya$, and $xa<xc$ if $yb<ya$; that is, $ (xa-xc)(yb-ya) >0$. Since $(xa-xb)=0$, this condition is equivalent to inequality (\Eq{36A}). But that comes out to be
$$xayb-yaxb+xbyc-ybxc+xcya-ycxa>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 collinear or coincident. From the theory of determinants we have
$$\eqalignno{\Delta(a,b,c)=\detmat{\matrix3{
xa-xcya-yc0\cr\vsk3
xb-xcyb-yc0\cr\vsk3
xcyc1\cr}}\cr\vsk6
\null=\detmat{\matrix2{
xa-xcya-yc\cr\vsk3
xb-xcyb-yc\cr}}(\Eq{37A})\cr\vsk6
\null=(xa-xc)(yb-yc)-(ya-yc)(xb-xc).(\Eq{38A})\cr}$$
Now let $u=a-c=(xa-xc,ya-yc)$ and $v=b-c=(xb-xc, ya-yc)$. From (\Eq{37A}), we see that
$$\Delta(a,b,c)=\detmat{\matrix2{
xuyu\cr
xvyy\cr}}.\eqno(\Eq{39A})$$
The points $a,b,c$ are collinear 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 collinear 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{
xbyb1\cr
xaya1\cr
xcyc1\cr}}=-\detmat{\matrix3{
xaya1\cr
xbyb1\cr
xcyc1\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)}$$}
\section{\Ch{I}.\Sec2. Oriented lines}
In the Cartesian plane $\reals^2$, we define an {\it oriented line} as a classical (non-oriented) line $l$ endowed with a {\it normal direction} $\hat l$, a unit vector perpendicular to $l$. This enables us to distinguish the {\it left side} of $l$, the half-plane of $l$ 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 $l$ is uniquely determined by its normal vector and any point on $l$. The line can also be specified by a {\it characteristic function}, a function $f$ of $\reals^2\mapsto\reals$ that is zero on $l$, positive on its left side, and negative on its right side. An important example is the {\it signed distance} from $l$ to an arbitrary point $p=(x,y)$, denoted by $\sdist(l, p)$, that is the usual Euclidean distance between the two (measured perpendicularly to $l$) taken with plus or minus sign depending on whether $p$ lies in the left or right side of $l$.
Let $l$ be the oriented line with normal vector $\hat\lscr=(X, Y)$ and passing through the point $q=(xq,yq)$. For an arbitrary point $p=(x,y)$, the signed distance $\sdist(l, p)$ is the component $\hat\lscr\cdot(p-q)$ of $p-q$ in the normal direction $\hat\lscr$.\figspace3cm
This gives
$$\eqalign{\sdist(l, p)=X(x-xq) +
Y(y-yq)\cr\vsk4
\null=Xx + Yy -
(Xxq+Yyq)\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 polynomial $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 $l$. 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
$$\lscr0=-{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(l, 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 $l$. The line $l$ 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 l=(X, Y),$$
$$l0=(-WX, -WY),$$
and
$$\sdist(l, p)=Xx+Yy+W,$$
The point $l0$ given by the formulas above is the point on $l=\hol{X,Y\hom W}$ that is closest to the origin. The distance from the origin to $l$ is
$$\sdist(l, O)={W\over{\sqrt{X^2+Y^2}}}\eqno(\Eq{95A})$$
or, if the coefficients are normalized,
$$\sdist(l, 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{\Sec2.1}}{When and where does the line $l=\hol{X, Y\hom W}$ intersect the three coordinate axes?}
\footprob{\Prob{\Sec2.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}
\section{\Ch{I}.\Sec3. 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)=Xxc+Yyc+W,\eqno(\Eq{51A})$$
where
$$X=+\detmat{\matrix2{
ya1\cr
yb1\cr}}=(ya-yb),$$
$$Y=-\detmat{\matrix2{
xa1\cr
xb1\cr}}=-(xa-xb),$$
and
$$W=+\detmat{\matrix2{
xaya\cr
xbyb\cr}}=xayb-xbya.$$
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 collinear 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.
\section{\Ch{I}.\Sec4. 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 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 $(xp, yp, xq, yq)$ 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 $a0, a1, \ldots, ak$, of $\reals^k$ (in that order) are {\it positively oriented} (denoted by $\POS(a0, a1, \ldots, ak)$) if the determinant
$$\Delta(a1, a2, \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(a0, a1, \ldots, ak)$).}
In particular, given four points $a,b,c,$ and $d$ in three-dimensional space, we have
$$\Delta(a,b,c,d)=\detmat{\matrix4{
xayaza1\cr\vsk3
xbybzb1\cr\vsk3
xcyczc1\cr\vsk3
xdydzd1\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{
xa-xdya-ydza-zd\cr\vsk3
xb-xdyb-ydzb-zd\cr\vsk3
xc-xdyc-ydzc-zd\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 collinear.
\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 $a0\pr, a1\pr, \ldots, ak\pr$ be a permutation of $a0, a1, \ldots, ak$; then $\POS(a0\pr, a1\pr, \ldots, ak\pr)$ is equivalent to $\POS(a0, a1, \ldots, ak)$ or $\NEG(a0, a1, \ldots, ak)$, 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).$$
\section{\Ch{I}.\Sec5. 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 positive, zero, or negative depending on whether the argument is on the left half-space of $\pi$, on $\pi$, 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 - (Xxq+Yyq+Zzq),\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
$$\pi0=-{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{\Sec5.1}}{When and where does the plane $\pi=\hol{X, Y, Z\hom W}$ intersect the three coordinate axes?}
\footprob{\Prob{\Sec5.2}}{What is the relationship between $\hol{X, Y, Z\hom W}$ and $\hol{X, Y, Z\hom -W}$?}
\footprob{\Prob{\Sec5.3}}{Generalize oriented plane and related concepts to higher dimensions}
\note{Develop the analogous theory for points in homogenous coordinates}
\section{\Ch{I}.\Sec6. 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-collinear 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)=Xxd+Yyd+Zzd+W,\eqno(\Eq{51B})$$
(as a function of $d$), where
$$X=-\detmat{\matrix3{
yaza1\cr
ybzb1\cr
yczc1\cr}},$$
$$Y=+\detmat{\matrix3{
xaza1\cr
xbzb1\cr
xczc1\cr}},$$
$$Z=-\detmat{\matrix3{
xaya1\cr
xbyb1\cr
xcyc1\cr}},$$
and
$$W=+\detmat{\matrix3{
xayaza\cr
xbybzb\cr
xcyczc\cr}}.$$
This plane is such that the triangle $abc$ is seen as counterclockwise orietned to an observer anywhere on its left side.
\section{\Ch{I}.\Sec7. Oriented circles}
\note{Shouldn't the orientation of circles be given iby a normal vector? Worry about this in the 2SP.}
\note{find a uniform way to define orientation of lines, planes and circles.}
The test of whether a point is inside or outside a given circle plays a central role in many geometrical algorithms. In such algorithms, it is often convenient to treat straight lines (with the addition of the point at infinity) as circles with infinite radius. Topologically, the two concepts are equivalent: like a circle, a straight line divides the inversion plane ($\reals^2$ plus the point at infinity $\omega$) in two simply connected regions. However, there is no natural criterion for calling one of these regions the ``interior'' of the line, and the other the ``exterior''. We will resolve this ambiguity by specifying an orientation for the line, and substitute the notions of ``left side'' and ``right side'' for ``interior'' and ``exterior''. Mathematical cleanliness then requires we treat circles in the same manner. This justifies the following definitions:
\definition{\Def4}{An {\it oriented circle} is a circle on the extended plane endowed with a direction of traversal. The two regions of the extended plane bounded by $C$ are called the {\it left} and {\it right sides} of $C$, with respect to the direction of traversal of $C$.}
As we said before, an oriented straight line (with the point at infinity included) is a special case of oriented circle; its left and right sides are simply its left and right half-planes. For an oriented circle $C$ of finite radius, the left side is the interior or the exterior of the circle, depending on whether $C$ is oriented counter- or clockwise, respectively.
An oriented circle $C$ can also be defined by a characteristic function, that is zero on $C$, positive on its left side, and negative on its right side.
\theorem{\Th{81}}{Every oriented circle $C$ has a characteristic function of the form
$$f(x,y)=Xx+Yy+Z(x^2+y^2)+W.\eqno(\Eq{78})$$}
\proof{If $C$ is a counterclockwise oriented circle with finite radius $r$ and center $c=(xc, yc)$, we can test whether $p=(x,y)$ lies inside or outside $C$ by comparing $\dist(c,p)=\sqrt{(xc-x)^2+(yc-y)^2}$ against $r$. Since neither quantity is negative, the same results will be obtained if we compare $[\dist(c,p)]^2$ with $r^2$. So, the expression
$$\eqalignno{\nullr^2-[(xc-x)^2+(yc-y)^2](\Eq{79})\cr
\null\null=2xcx+2ycy-(x^2+y^2)+(r2-xc^2+yc^2)(\Eq{80})\cr}$$
is a characteristic function for $C$, and the theorem then holds with $X=2xc$, $Y=2yc$, $Z=-1$, and $W=r^2-xc^2+yc^2$.
\pp If $C$ is {\it clockwise} oriented, the left side is the exterior, and the right side is the interior. The sign reversal of (\Eq{80}) will be then a characteristic function for $C$. The theorem is satisfied by taking $X=-2xc$, $Y=-2yc$, $Z=1$, and $W=-(r^2-xc^2+yc^2)$.
\pp If the radius is infinite, the circle is an oriented straight line, which as we know has a characteristic function of the form $Xx+Yy+W$. This satisfies the theorem if we take $Z=0$.}
The ``converse'' of this theorem is also true: for any quadruple of coefficients $X, Y, Z$, and $W$ such that $X^2+Y^2-4ZW >0$, there is an oriented circle whose characteristic function is (\Eq{78}). If $Z=0$, the circle is simply the oriented line $\hol{X, Y\hom W}$. Otherwise it is a finite circle whose center $c$ and radius $r$ are given by
$$c=\left(-{X\over{2Z}}, -{Y\over {2Z}}\right)\eqno(\Eq{101})$$
and
$$r=\sqrt{xc^2+yc^2+W}={1\over{\leftv 2Z\rightv}}\sqrt{X^2+Y^2-4ZW}\eqno(\Eq{102})$$
The circle will be oriented counter- or clockwise depending on whether $Z$ is negative or positive.
\digress{The condition $X^2+Y^2-4WZ>0$ is equivalent to the requirement that $f(x,y)=Xx+Yy+Z(x^2+y^2)+W$ assumes both positive and negative values. If $X^2+Y^2-4ZW <0$, $f$ has everywhere the same (non-zero) sign as $Z$: the ``circle'' it represents has no boundary, and the whole plane lies on one side of it. When $X^2+Y^2-4ZW =0$, $f$ is zero at the point $c$ (\Eq{101}) and has the sign of $Z$ everywhere else.}
\note{Should this stuff go into chapter \Ch2? A sketchier version of it is already there.}
\note{Should we accept circles of radius zero?}
\note{Remark that (\Eq{79}) is faster to compute than (\Eq{80}) if we know the center and radius. Equation (\Eq{80}) is valuable because of the $\lambda$-mapping, and it also gives a more efficient formula for the case when $C$ is determined by three given points.}
\section{\Ch{I}.\Sec8. The quadratic mapping}
These results have a very nice geometrical interpretation. Consider the function $\lambda$ that lifts every point $(x, y)$ of the plane onto the point $(x, y, x^2+y^2)$ on the paraboloid of revolution $\Lambda$ defined by the equation $z=x^2+y^2$. This mapping has an amazing property: circles and straight lines on the $(x,y)$-plane are mapped to planar sections of $\Lambda$, end vice-versa!\figspace5cm
This fact follows directly from theorems \Th{81}: if the characteristic function of $C$ is $Xx+Yy+Z(x^2+x^2)+W$, then $(x,y)$ lies on $C$ if and only if its image $(x,y,x^2+y^2)$ lies on the plane $\pi(C)=\hol{X,Y, Z\hom W}$. Furthermore, the point $p$ is to the left of $C$ if and only if its image $\lambda(p)$ is to the left of $\pi(C)$. In particular, if $C$ is a counterclockwise oriented circle of finite radius, the plane $\pi(C)$ is oriented downwards ($Z$ is negative), so $p$ is to the left of $C$ if and only if its image is below $\pi(C)$.
Conversely, if a plane $\hol{X,Y,Z\hom W}$ cuts the paraboloid $\Lambda$, Any point $(x,y,z)$ on the intersection will satisfy both $z=x^2+y^2$ and $Xx+Yy+Zz+W=0$; the projection of that point will then satisfy $f(x,y)=Xx+Yy+Z(x^2+y^2)+W=0$. Moreover, by asssmption there will be points of $\Lambda$ on both sides of $\hol{X,Y,Z\hom W}$, so $f$ takes both positive and negative values. It follows that $X^2+Y^2-4ZW>0$, and therefore $f$ is a valid characteristic function for some circle.
\digress{These results can be generalized quite easily to other algebraic curves. For example, general conic sections (which include circles, ellipses, parabolas, and hyperbolas as special cases) have characteristic functions of the form $Xx+Yy+Ax^2+By^2+Cxy+W$. Therefore, the function $\xi:(x,y)\mapsto(x,y,x^2,y^2,xy)$ maps the problem of locating a point against a conic into that of locating a point of $\reals^5$ against a four-dimensional hyperplane of $\reals^5$.
\dp One can also extend this to higher dimensions: by the mapping $\lambda:(x,y,z)\mapsto(x,y,z,x^2+y^2+z^2)$, point location against a sphere is reduced to point location against a three-dimensional hyperplane of $\reals^4$.}
\footprob{\Prob{\Sec8.1}}{Study the problem of finding the minimum spanning ellipse in this light. What if we constrain the main axes of the ellipse to be parallel to the coordinate axes?}
\section{\Ch{I}.\Sec9. The oriented circle through three points}
The quadratic mapping makes the following result almost self-evident:
\theorem{\Th{41}}{Given any three distinct points $a, b, c$ on the plane, there is a unique circle that passes through them}
\proof{Consider the images $\lambda(a), \lambda(b), \lambda(c)$ of $a,b,c$. These three points are distinct and, since $\Lambda$ is a strictly convex surface, they are also non-collinear. There exists then a unique plane $\pi=\lambda(a)\lambda(b)\lambda(c)$ passing through those three points. The intersection of this plane with $\Lambda$ is a circle that passes through $a,b,c$. Any other circle also passing through $a,b,c$ would correspond to a plane passing through $\lambda(a),\lambda(b),\lambda(c)$ but distinct from $\pi$, a contradiction.}
The circle passing through $a,b,c$ can be oriented in two distinct ways. If we go once around the circle starting from $a$, we will encounter the three points either in the order $a,b,c$ or in the order $a,c,b$, depending on which way we go. This motivates the following definition:
\definition{\Def{29}}{The {\it (oriented) circle $abc$}, where $a,b,c$ are distinct points of the plane, is the classical (unoriented) circle passing through them, with the direction of traversal from $a$ through $b$ to $c$.}
If the three points determine a counterclockwise oriented triangle, then the circle $C=abc$ is oriented the same way. Under the quadratric mapping, $C$ maps to the intersection of $\Lambda$ with the plane $\pi=\lambda(a)\lambda(b)\lambda(c)$. The left side (that is, the interior) of $C$ maps to the part of $\Lambda$ that lies below $\pi$. According to the comments we made before, that is the {\it right} side of $\pi$.\figspace5cm
The oriented circle $acb$ passes through the same points as $C$, but has the opposite orientation. In general, if $a\pr, b\pr, c\pr$ is a permutation of the points $a,b,c$, the circle $a\pr b\pr c\pr$ will be oriented the same way as $C$ if the permutation is even, and the opposite way if it is odd. The orientation of the planes $\pi\pr=\lambda(a\pr)\lambda(b\pr)\lambda(c\pr)$ and $\pi$ are realted in precisely the same way. We conclude that the observation made in the preceding paragraph is true for {\it any} three points $a,b,c$, namely the left side of the circle $abc$ maps to the part of $\Lambda$ that is in the {\it right} side of the plane $\pi$.
Note that the proof of theorem \Th{41} still carries through if the three points $a,b,c$ are collinear; in that case, the plane $\pi$ is vertical, and the circle through $a,b,c$ degenerates to the line supporting them. The discussion above also carries through: the left side of the oriented line $abc$ maps to the part of $\lambda$ that lies to the right of $\pi$.
\proof{Let $p1, p2, p3$ be three sufficiently small pigs, and $\hbox{\bi W\/}$ an wolf, assumed to be simultaneously big and bad.}
\section{\Ch{I}.\Sec{10}. The InCircle test}
We are now ready to define our geometric predicate, that applies to four points $a, b, c, d$ of the plane:
\definition{\Def5}{The predicates $\incircle(a, b, c, d)$ and $\outcircle(a,b,c,d)$ are true if the point $d$ lies respectively to the left and to the right of the oriented circle $abc$. Both predicates are false if two or more of $a,b,$ and $c$ coincide, or if $d$ is on the circle $abc$.}
In particular, when $a, b, c$ are counterclockwise oriented, $\incircle(a, b, c, d)$ is true if and only if $d$ lies inside the circle $abc$, and $\outcircle(a,b,c,d)$ is true if and only if $d$ is outside. When $a,b,c$ are clockwise oriented, these meanings are reversed: $\incircle$ is true {\it outside} the circle $abc$, and $\outcircle$ is true inside.\figspace4cm
\note{Edit this:} This predicate seems rather awkward to use in practice, since its meaning is dependent on the ordering of the points $a$, $b$ and $c$. Actually, this is not so: as for the algorithms we are going to see, in most uses of this predicate we know beforehand that $abc$ is a counterclockwise oriented triangle, so the intuitive interpretation suggested by its name is correct. However, definition \Def5 is better at handling degenerate cases situations (where $a$, $b$ and $c$ are collinear) than the simpler, intuitive interpretation.
According to what we discussed in the previous section, $\incircle(a,b,c,d)$ tests whether $\lambda(d)$ lies on the right side of the orietned plane $\lambda(a)\lambda(b)\lambda(c)$. Together with definition \Def{37B}, this proves the next lemma:
\lemma{\Th{40B}}{For any points $a,b,c,d$ on the plane,
$$\eqalign{
\incircle(a, b, c, d)
=\NEG(\lambda(a),\lambda(b), \lambda(c),\lambda(d))\cr
\outcircle(a, b, c, d)
=\POS(\lambda(a),\lambda(b), \lambda(c),\lambda(d))\cr}.\eqno(\Eq{103})$$}
From this equivalence we immediately derive a somewhat surprising fact: if the points $a,b,c,d$ are not on the same circle, then transposing any adjacent pair in the predicate $\incircle(a,b,c,d)$ will change the value of the predicate from true to false, or vice versa. In general, permuting the arguments of $\incircle(a,b,c,d)$ will either preserve or reverse its value, depending on whether the permutation has even or odd parity. The same of course is true of $\outcircle(a,b,c,d)$. In particular, we have
$$\incircle(a,b,c,d)\eqv\outcircle(b,c,d,a) \eqv\incircle(c,d,a,b)\eqv\outcircle(d,a,b,c).$$
We can see that in $\incircle(a,b,c,d)$ all four points play a symmetric role, even though from the definition $d$ seems to be special.
From theorem \Th{40B} we also conclude that
\theorem{\Th{43}}{The predicate $\incircle(a, b, c, d)$ is true if and only if
$$\Delta(\lambda(a), \lambda(b), \lambda(c), \lambda(d))=
\detmat{\matrix4{
xayaxa^2+ya^21\cr\vsk3
xbybxb^2+yb^21\cr\vsk3
xcycxc^2+yc^21\cr\vsk3
xdydxd^2+yd^21\cr}}\eqno(\Eq7)$$
is negative. The predicate $\outcircle(a, b, c, d)$ is true if and only if this determinant is positive.}
This theorem gives a reasonably efficient formula for computing the $\incircle$ predicate.
\footprob{\Prob{\Sec{10}.1}}{Find the most efficient way to compute the $\incircle$ test. {\it Hint\/}: Nine subtractions reduce the determinant of equation \Eq6 to a $3\times 3$ determinant. Note that we need only the sign of $\Delta$, not its absolute value. {\it Another hint\/}: Consider expanding (\Eq6) by the third column; who knows, it may be better.} }
\footprob{\Prob{\Sec{10}.2}}{Study the numerical stability of the determinant (\Eq7), and develop ``numerically robust'' algorithms for computing it.}
\section{\Ch{I}.\Sec{11}. Properties of the InCircle test}
The $\incircle$ property has an alternate geometrical interpretation that is in some situations easier to use:
\lemma{\Th{20C}}{Let $a,b,c,d$ be in counterclockwise order the four distinct vertices of a simple quadrilateral $Q$ (not necessarily convex). Let $\hat a, \hat b, \hat c, \hat d$ be the corresponding internal angles of $Q$. Then the following conditions are equivalent:
\tp 1. $\incircle(a,b,c,d)$;
\tp 2. $\hat a+\hat c < 180\deg$;
\tp 3. $\hat b+\hat d > 180\deg$;
\tp 4. $\hat a+\hat c < \hat b+\hat d$.}
\proof{Conditions 2, 3 and 4 are obviously equivalent, since the interior angles of any simple quadrilateral add to exactly $360\deg$. Let us show that 1 and 2 are equivalent.\figspace3cm
\pp Because of our assumptions on $Q$, the circle $C=\circle(a,b,c)$ is counterclockwise oriented. The arcs $cda$ and $abc$, respectively subtended on $C$ by the angles $\hat b$ and $\hat d$, add up to $360\deg$. As we know from elementary geometry, the measure of $\hat b$ is half of the arc $cda$. Also, the angle $\hat d$ will be more than half of the arc $abc$ if and only if $d$ is inside the circle $C$\foot\dag{Note that this holds even if $Q$ is concave at $d$, that is, if $a$ and $d$ lie on the same side of the line $bd$.}. We conclude that $\hat a+\hat c <{1\over2}360\deg=180\deg$ if and only if $d$ is to the left of $\circle(a,b,c)$, that is, if and only if $\incircle(a,b,c,d)$.}
\digress{Another way of testing whether four points are cocircular is given by Ptolemy's theorem, which states that $a,b,c,d$ lie on the same sircle (in that order) if and only if
$$\bar{ab}\times\bar{cd}+\bar{bc}\times\bar{ad} = \bar{bd}\times\bar {ac}$$
This theorem however cannot be used to decide whether $d$ is inside or outside the circle $abc$, as we always have
$$\bar{ab}\times\bar{cd}+\bar{bc}\times\bar{ad}\geq \bar{bd}\times\bar {ac},$$
with equality only when the four points are cocircular. In fact, the quantity one obtains by rendering $\bar{ab}\times\bar{cd}+\bar{bc}\times\bar{ad} -\bar{bd}\times\bar {ac}$ radical-free is exactly the square of the determinant $\Delta(\lambda(a),\lambda(b),\lambda(c),\lambda(d))$ above. \note{Check this again. Is the square really thre from the beginning, or is it introduced in the elimination of radicals?}}
\note{Historical note: augment.} The quadratic mapping as a means of transforming circles in the plane into planes in three-space is a rather old idea. The basic principles of the $\incircle$ test appear in a classic paper by Jung (do they???). However, it is not as well known as it should, and in fact it has been independently rediscovered many times.
\section{\Ch{I}.\Sec{12}. Homogeneous coordinates}
\note{This section is a slightly edited version of the comments in COGHomo2.mesa}
A point of the Two-Sided Plane (2SP) {\small (Homogeneous plane? Homoplane?)} is represented in homogeneous coordinates by a triplet of real numbers $\hop{x,y\hom w}$, not all of them zero, with the convention that two triplets $\hop{x,y\hom w}$ and $\hop{x\pr, y\pr\hom w\pr}$ represent the same point iff we have $x=\alpha x\pr$, $y=\alpha y\pr$, and $w=\alpha w\pr$ for some {\em positive} real $\alpha $. If we view each triplet $\hop{x,y\hom w}$ as a point $(x,y,w)$ in $\reals^3$, then each point of the 2SP corresponds to an open ray in $\reals^3$ emanating from the origin $(0,0,0)$, and vice-versa.
The {\it homogeneous distance} between two points $p=\hop{x,y\hom w}$ and $q=\hop{x\pr, y\pr\hom w\pr}$ of the 2SP is defined by
$$\hdist(p,q) = 1-{{xx\pr + yy\pr + ww\pr}\over
{\sqrt{x^2+y^2+w^2}\sqrt{{x\pr}^2+{y\pr}^2+{w\pr}^2}}}.$$ This is simply $1-\cos\theta{pq}$, where $\theta{pq}$ is the angle between the rays corresponding to the two points.
Each point $p$ of the 2SP has a unique {\it normalized representation}, a triplet $\hop{x,y\hom w}$ where $x^2+y^2+w^2=1$. This triplet corresponds to the point $(x,y,w)$ in $\reals^3$ where the ray corresponding to $p$ hits the surface $\sphere^2$ of the three-dimensional unit sphere. If $\hop{x,y\hom w}$ and $\hop{x\pr, y\pr\hom w\pr}$ are the normalized representations of $p$ and $q$, then $\hdist(p,q)=1-xx\pr + yy\pr + ww\pr$. Clearly, the 2SP with the topology induced by the $\hdist$ metric is homeomorphic to the surface $\sphere^2$ of the three-dimensional unit ball, with the usual topology.
An (oriented) line of the 2SP is also represented by a triplet $\hol{X, Y\hom W}$ of real coordinates, not all three zero. We say that a point $\hop{x,y\hom w}$ lies on that line, to its left, or to its right, depending on whether $Xx+Yy+Ww$ is zero, positive, or negative. We say that a line passes to the left of a point iff the point lies to the left of the line, and vice-versa. {\small Should it be the other way around?}
The {\it natural correspondence} between the 2SP and the oriented Cartesian plane is defined in the following way: to the point $\hop{x,y\hom w}$ there corresponds the point $(x/w,y/w)$; to the line $\hol{X,Y\hom W}$ there corresponds the oriented line with equation $Xx+by+W=0$ and left side defined by the normal direction vector $(X,Y)/\sqrt{X^2+Y^2}$. This correspondence is not defined for the points with $w=0$ or for the lines with $X=Y=0$. This is equivalent to the central projection of the unit sphere $\sphere^2$ onto the plane $z=1$.
The natural image $L$ of a line $\hol{X,Y\hom W}$ passes at distance $W/\sqrt{X^2+Y^2}$ from the Cartesian origin $(0,0)$. The longitudinal orientation of $L$ (that is, the direction in which we must face so that the left side of $L$ lies to our left) is the vector $(Y, -X)/\sqrt{X^2+Y^2}$. It follows that $L$ is oriented counterclockwise as seen from the origin iff $W>0$. If $W=0$, $L$ passes through $(0,0)$. The two lines $\hol{X,Y\hom W}$ and $\hol{-X,-Y\hom -W}$ map onto the same Cartesian line with opposite orientations; they are said to be the opposite of each other. Two lines $\hol{X, Y\hom W}$ and $\hol{X, Y\hom W\pr}$ are said to be parallel, while $\hol{X,Y\hom W}$ and $\hol{-X,-Y\hom W\pr}$ are antiparallel.
The points $\hop{x,y\hom w}$ with $w>0$ constitute the {\it top side} of the 2SP. The natural correspondence defines an isomorphism between the top side of the 2SP and the oriented Cartesian plane: open sets map to oppen sets, and $\hop{x,y\hom w}$ is on or to the left of $\hol{X,Y\hom W}$ if and only if the same relation holds for their natural images.
The bottom side of the 2SP, also called the "antiplane", consists of the points with $w<0$. The natural correspondence also maps the bottom side one-to-one onto the Cartesian plane, taking open sets into open sets, but it falls short of being an isomorphism: a point $\hop{x,y\hom w}$ on the bottom side lies to the left of a line $\hol{X,Y\hom W}$ if and only if the corresponding point lies to the {\it right} of the corresponding line.
The points $\hop{x,y\hom w}$ and $\hop{-x,-y\hom -w}$ of the 2SP that map onto the same Cartesian point $(x/w, y/w)$ are said to be the antipodes of each other. A line that passes through a point also passes through its antipode. The top origin of the 2SP is the point $\hop{0,0\hom 1}$ (and its positive multiples); its antipode $\hop{0,0\hom -1}$ is called the bottom origin. Under the natural correspondence, both are mapped to the Cartesian origin $(0,0)$. A line $\hol{X, Y\hom W}$ passes through the top (and bottom) origin iff $W=0$.
We can imagine that a point $\hop{x,y\hom 0}$ of the 2SP corresponds to a point at infinite distance from the origin in the in the direction (x,y). Note that $\hop{x,y\hom 0}$ is distinct from $\hop{-x,-y\hom 0}$. That point lies on all lines of the form $\hol{-y, x\hom W}$ for all $W$. The lines $\hol{0,0\hom 1}$ and $\hol{0,0\hom -1}$ are the two lines at infinity of the 2SP, and consist of exactly all the points at infinity. The left side of $\hol{0,0\hom 1}$ is the entire top side of the 2SP, whereas that of $\hol{0,0\hom -1}$ is the bottom side.
The triplets $\hop{0, 0\hom 0}$ and $\hol{0,0\hom 0}$ are called the indeterminate point and indeterminate line, respectively. They are not considered to be true elements of the 2SP, but they are returned by many operations in this interface when the latter are applied to invalid combinations of arguments. For example, the procedure that computes the intersection of two lines returns $\hop{0,0\hom 0}$ when the lines are coincident. Many operations will return $\hop{0,0\hom 0}$ or $\hol{0,0\hom 0}$ if one or more of the arguments is $\hop{0,0\hom 0}$ of $\hol{0,0\hom 0}$. However, in some cases an arithmetic trap (divide by zero, or such) will result instead, so be careful.
The set of all points on the 2SP lying on an oriented line $\hol{X, Y\hom W}$ is homeomorphic to the unit circle $S1$. The orientation of the line defines a cyclical ordering of the points lying on it: given any three points $p1,q,p2$, on $L$, we can tell whether $q$ lies on the way from $p1$ to $p2$ along $L$ (HOW?). The set of all $q$'s on $L$ on the way from $p1$ to $p2$ constitutes by definition the {\it arc of $L$ from $p1$ to $p2$}. An arc is {\it proper} if no two of its points (including the extremities) are antipodes of each other.
If $p1$, $p2$ are two distinct, non-antipodal points of the 2SP, there are exactly two lines $L1$, $L2$ passing through those two points, and they are opposite to each other. We define the {\it oriented line $p1p2$} as being the one such that its arc from $p1$ to $p2$ is proper. Informally, the line $p1p2$ as the one that goes from $p1$ to $p2$ by the shortest way. The oriented line $p2p1$ is the opposite of the line $p1p2$ (or both are undefined). The {\it line segment connecting $p1$ and $p2$}, or simply the {\it segment $p1p2$}, is the (proper) arc from $p1$ to $p2$ on the line $p1p2$.
Two lines $L1$, $L2$ of the 2SP that are not coincident or opposite of each other meet at exactly two antipodal points. Those points will be both at infinity if the lines are parallel; if not, they are both finite.
The point $\hop{x,y\hom w}$ and the line $\hol{x,y\hom w}$ are dual of each other. If the point $p$ lies on (resp. to the left of) the line $L$, then the point $L$* that is dual of $L$ lies on (resp. to the left of) the line $p*$ that is dual of $p$. Two points are antipodal of each other iff theis duals are opposite lines.
Therefore, If $L1, L2$ are not coincident or opposite of each other, their dual points $L1*$ and $L2*$ define a unique oriented line $L1*L2*$ passing through both points. The dual $(L1*L2*)*$ of this line is a point that lies on both $L1$ and $L2$, and is by definition the intersection point $L1L2$. Note that the point $L2L1$ is the antipode of the point $L1L2$
Two lines $L1$, $L2$ of the 2SP that are not coincident or opposite of each other meet at exactly two antipodal points. Those points will be both at infinity if the lines are parallel; if not, they are both finite. We define the intersection $p$ of $L1$ and $L2$ (in that order) as the one of those two points such that we can get $L2$ by rotating $L1$ counterclockwise around $p$ by less than $180$ degrees.
The homogeneous distance between two lines is defined as the homogeneous distance between their duals.