i
i
i
i
i
i
i
i
A.5. Geometry 909
shown previously, the normal can be computed using two direction vectors,
but it can naturally also be obtained from three noncollinear points, u, v,
and w, lying on the plane, as n =(u −w) ×(v −w). Given n and a point
q on the plane, the constant is computed as d = −n · q. The half-plane
test is equally valid. By denoting f (p)=n · p + d, the same conclusions
can be drawn as for the two-dimensional line; that is,
1. f(p)=0⇐⇒ p ∈ π.
2. f(p) > 0 ⇐⇒ p lies on the same side of the plane as the point q + n.
3. f(p) < 0 ⇐⇒ p lies on the same side of the plane as the point q −n.
The signed distance from an arbitrary point p to π is obtained by
exchanging the two-dimensional parts of Equation A.49 for their three-
dimensional counterparts for the plane. Also, it is very easy to interpret
the meaning of d using the signed distance formula. This requires inserting
the origin, 0,intothatformula;f
s
(0)=d, which means that d is the
shortest (signed) distance from the origin to the plane.
A.5.3 Convex Hull
For a set of points, the convex hull is defined as the smallest set that satisfies
the condition that the straight line between any two points in the set is
totally included in the set as well. This holds for any dimension.
In two dimensions, the construction of the convex hull is intuitively
illustrated by the rubberband/nail scheme. Imagine that the points are
nails in a table, and that a rubber band is held in such a way that its
interior includes all nails. The rubber band is then released, and now the
Figure A.6. The rubberband/nail scheme in action. The left figure shows the rubber
band before it has been released and the right figure shows the result after. Then the
rubber band is a representation of the convex hull of the nails.
i
i
i
i
i
i
i
i
910 A. Some Linear Algebra
rubber band is, in fact, the convex hull of the nails. This is illustrated in
Figure A.6.
The convex hull has many areas of use; the construction of bounding
volumes is one. The convex hull is, by its definition, the smallest convex vol-
ume for a set of points, and is therefore attractive for those computations.
Algorithms for computing the convex hull in two and three dimensions can
be found in, for example, books by de Berg et al. [82] or O’Rourke [975].
A fast algorithm, called QuickHull, is presented by Barber et al. [62].
A.5.4 Miscellaneous
Area Calculation
A parallelogram defined by two vectors, u and v, starting at the origin,
has the area ||u × v|| = ||u|| ||v||sin φ, as shown in Figure A.7.
If the parallelogram is divided by a line from u to v, two triangles are
formed. This means that the area of each triangle is half the area of the
parallelogram. So, if a triangle is given by three points, say p, q,andr,
its area is
Area(pqr)=
1
2
||(p − r) × (q − r)||. (A.53)
The signed area of a general two-dimensional polygon can be computed
by [975, 1081]
Area(P )=
1
2
n−1
i=0
(x
i
y
i+1
− y
i
x
i+1
), (A.54)
Figure A.7. Left figure: a parallelogram whose area is computed by multiplying the
length of the base (||u||) with the height (||v||sin φ). Right figure: the volume of a
parallelepiped is given by (u × v) · w.
i
i
i
i
i
i
i
i
A.5. Geometry 911
where n is the number of vertices, and where i is modulo n,sothatx
n
= x
0
,
etc. This area can be computed with fewer multiplies and potentially more
accuracy (though needing a wider range of indices for each term) by the
following formula [1230]:
Area(P )=
1
2
n−1
i=0
(x
i
(y
i+1
− y
i−1
)). (A.55)
The sign of the area is related to the order in which the outline of the
polygon is traversed; positive means counterclockwise.
Volume Calculation
The scalar triple product, from Equation A.18, is sometimes also called the
volume formula. Three vectors, u, v and w, starting at the origin, form a
solid, called a parallelepiped, whose volume is given by the equation that
follows. The volume and the notation are depicted in Figure A.7:
Volume(u, v, w)=(u × v) ·w =det(u, v, w) (A.56)
This is a positive value only if the vectors form a positively oriented
basis. The formula intuitively explains why the determinant of three vec-
tors is zero if the vectors do not span the entire space R
3
:Inthatcase,
the volume is zero, meaning that the vectors must lie in the same plane (or
one or more of them may be the zero vector).
Further Reading and Resources
For a more thorough treatment of linear algebra, the reader is directed to,
for example, the books by Lawson [741] and Lax [742]. Hutson and Pym’s
book [578] gives an in-depth treatment of all kinds of spaces (and more). A
lighter read is Farin and Hansford’s Practical Linear Algebra [333], which
builds up a geometric understanding for transforms, eigenvalues, and much
else.
The 30th edition of the CRC Standard Mathematical Tables and For-
mulas [1416] is a recent major update of this classic reference. Much of the
material in this appendix is included, as well as a huge amount of other
mathematical knowledge.
i
i
i
i
i
i
i
i
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.