Geometric Structures and Mathematics
Where can I get source for Voronoi/Delaunay triangulation?
For 2-d Delaunay triangulation, try Shewchuk's triangle program. It
includes options for constrained triangulation and quality mesh
generation. It uses exact arithmetic.
The Delaunay triangulation is equivalent to computing the convex hull
of the points lifted to a paraboloid. For n-d Delaunay triangulation
try Clarkson's hull program (exact arithmetic) or Barber and Huhdanpaa's
Qhull program (floating point arithmetic). The hull program also
computes Voronoi volumes and alpha shapes. The Qhull program also
computes 2-d Voronoi diagrams and n-d Voronoi vertices. The output of
both programs may be visualized with Geomview.
There are many other codes for Delaunay triangulation and Voronoi
diagrams. See Amenta's list of computational geometry software.
Especially noteworthy is the CGAL code: Subject 0.07 and
The Delaunay triangulation satisfies the following property: the
circumcircle of each triangle is empty. The Voronoi diagram is the
closest-point map, i.e., each Voronoi cell identifies the points that
are closest to an input site. The Voronoi diagram is the dual of
the Delaunay triangulation. Both structures are defined for general
dimension. Delaunay triangulation is an important part of mesh
generation.
There is a FAQ of polyhedral computation explaining how to compute
n-d Delaunay triangulation and n-d Voronoi diagram using a convex hull
code, and how to use the linear programming technique to
determine the Voronoi cells adjacent to a given Voronoi cell
efficiently for large scale or higher dimensional cases.
Avis' lrs code uses the same file formats as cdd. It
uses exact arithmetic and is useful
for problems with very large output size, since it does not
require storing the output.
On a closely related topic, see
http://www.cis.ohio-state.edu/~tamaldey/medialaxis.htm
for computation of the 3D medial axis from the Voronoi diagram.
References:
Amenta: http://www.geom.umn.edu/software/cglist
Avis: ftp://mutt.cs.mcgill.ca/pub/C/lrs.html
Barber & http://www.geom.umn.edu/locate/qhull
Huhdanpaa ftp://geom.umn.edu/pub/software/
ftp://ftp.geom.umn.edu/pub/software/
Clarkson: http://cm.bell-labs.com/netlib/voronoi/hull.html
ftp://cm.bell-labs.com/netlib/voronoi/hull.shar.Z
Geomview: http://www.geom.umn.edu/locate/geomview
ftp://geom.umn.edu/pub/software/geomview/
Polyhedral Computation FAQ:
http://www.ifor.math.ethz.ch/ifor/staff/fu...uda/fukuda.html
Shewchuk: http://www.cs.cmu.edu/~quake/triangle.html
ftp://cm.bell-labs.com/netlib/voronoi/triangle.shar.Z
[O' Rourke ©] pp. 168-204
[Preparata & Shamos] pp. 204-225
Chew, L. P. 1987. "Constrained Delaunay Triangulations," Proc. Third
Annual ACM Symposium on Computational Geometry.
Chew, L. P. 1989. "Constrained Delaunay Triangulations," Algorithmica
4:97-108. (UPDATED VERSION OF CHEW 1987.)
Fang, T-P. and L. A. Piegl. 1994. "Algorithm for Constrained Delaunay
Triangulation," The Visual Computer 10:255-265. (RECOMMENDED!)
Frey, W. H. 1987. "Selective Refinement: A New Strategy for Automatic
Node Placement in Graded Triangular Meshes," International Journal for
Numerical Methods in Engineering 24:2183-2200.
Guibas, L. and J. Stolfi. 1985. "Primitives for the Manipulation of
General Subdivisions and the Computation of Voronoi Diagrams," ACM
Transactions on Graphics 4(2):74-123.
Karasick, M., D. Lieber, and L. R. Nackman. 1991. "Efficient Delaunay
Triangulation Using Rational Arithmetic," ACM Transactions on Graphics
10(1):71-91.
Lischinski, D. 1994. "Incremental Delaunay Triangulation," Graphics
Gems IV, P. S. Heckbert, Ed. Cambridge, MA: Academic Press Professional.
(INCLUDES C++ SOURCE CODE -- THANK YOU, DANI!)
[Okabe]
Schuierer, S. 1989. "Delaunay Triangulation and the Radiosity
Approach," Proc. Eurographics '89, W. Hansmann, F. R. A. Hopgood, and
W. Strasser, Eds. Elsevier Science Publishers, 345-353.
Subramanian, G., V. V. S. Raveendra, and M. G. Kamath. 1994. "Robust
Boundary Triangulation and Delaunay Triangulation of Arbitrary
Triangular Domains," International Journal for Numerical Methods in
Engineering 37(10):1779-1789.
Watson, D. F. and G. M. Philip. 1984. "Survey: Systematic
Triangulations," Computer Vision, Graphics, and Image Processing
26:217-223.
Where do I get source for convex hull?
For n-d convex hulls, try Clarkson's hull program (exact arithmetic)
or Barber and Huhdanpaa's Qhull program (floating point arithmetic).
Qhull 3.1 includes triangulated output and improved
handling of difficult inputs. Qhull computes convex hulls,
Delaunay triangulations, Voronoi diagrams, and halfspace
intersections about a point.
Qhull handles numeric precision problems by merging facets. The output
of both programs may be visualized with Geomview.
In higher dimensions, the number of facets may be much smaller than
the number of lower-dimensional features. When this is the case,
Fukuda's cdd program is much faster than Qhull or hull.
There are many other codes for convex hulls. See Amenta's list of
computational geometry software.
References:
Amenta: http://www.geom.umn.edu/software/cglist/
Barber & http://www.geom.umn.edu/locate/qhull
Huhdanpaa
Clarkson: http://cm.bell-labs.com/netlib/voronoi/hull.html
ftp://cm.bell-labs.com/netlib/voronoi/hull.shar.Z
Geomview: http://www.geom.umn.edu/locate/geomview
ftp://geom.umn.edu/pub/software/geomview/
Fukuda: http://www.ifor.math.ethz.ch/staff/fukuda/...d_home/cdd.html
ftp://ftp.ifor.math.ethz.ch/pub/fukuda/cdd/
[O' Rourke ©] pp. 70-167
C code for Graham's algorithm on p.80-96.
Three-dimensional convex hull discussed in Chapter 4 (p.113-67).
C code for the incremental algorithm on p.130-60.
[Preparata & Shamos] pp. 95-184
Where do I get source for halfspace intersection?
For n-d halfspace intersection, try Fukuda's cdd program or Barber
and Huhdanpaa's Qhull program. Both use floating point arithmetic.
Fukuda includes code for exact arithmetic. Qhull handles numeric
precision problems by merging facets.
Qhull computes halfspace intersection by computing a convex hull.
The intersection of halfspaces about the origin is equivalent to the
convex hull of the halfspace coefficients divided by their offsets.
See Subject 6.02 for more information.
References:
Barber & http://www.geom.umn.edu/locate/qhull
Huhdanpaa
Fukuda: ftp://ifor13.ethz.ch/pub/fukuda/cdd/
[Preparata & Shamos] pp. 315-320
What are barycentric coordinates?
Let p1, p2, p3 be the three vertices (corners) of a closed
triangle T (in 2D or 3D or any dimension). Let t1, t2, t3 be real
numbers that sum to 1, with each between 0 and 1: t1 + t2 + t3 = 1,
0 <= ti <= 1. Then the point p = t1*p1 + t2*p2 + t3*p3 lies in
the plane of T and is inside T. The numbers (t1,t2,t3) are called the
barycentric coordinates of p with respect to T. They uniquely identify
p. They can be viewed as masses placed at the vertices whose
center of gravity is p.
For example, let p1=(0,0), p2=(1,0), p3=(3,2). The
barycentric coordinates (1/2,0,1/2) specify the point
p = (0,0)/2 + 0*(1,0) + (3,2)/2 = (3/2,1), the midpoint of the p1-p3
edge.
If p is joined to the three vertices, T is partitioned
into three triangles. Call them T1, T2, T3, with Ti not incident
to pi. The areas of these triangles Ti are proportional to the
barycentric coordinates ti of p.
Reference:
[Coxeter, Intro. to Geometry, p.217].
How can I generate a random point inside a triangle?
Use barycentric coordinates (see item 53) . Let A, B, C be the
three vertices of your triangle. Any point P inside can be expressed
uniquely as P = aA + bB + cC, where a+b+c=1 and a,b,c are each >= 0.
Knowing a and b permits you to calculate c=1-a-b. So if you can
generate two random numbers a and b, each in [0,1], such that
their sum <=1, you've got a random point in your triangle.
Generate random a and b independently and uniformly in [0,1]
(just divide the standard C rand() by its max value to get such a
random number.) If a+b>1, replace a by 1-a, b by 1-b. Let c=1-a-b.
Then aA + bB + cC is uniformly distributed in triangle ABC: the reflection
step a=1-a; b=1-b gives a point (a,b) uniformly distributed in the triangle
(0,0)(1,0)(0,1), which is then mapped affinely to ABC.
Now you have barycentric coordinates a,b,c. Compute your point
P = aA + bB + cC.
Reference: [Gems I], Turk, pp. 24-28, contains a similar but different
method which requires a square root.
How do I evenly distribute N points on (tesselate) a sphere?
"Evenly distributed" doesn't have a single definition. There is a
sense in which only the five Platonic solids achieve regular
tesselations, as they are the only ones whose faces are regular
and equal, with each vertex incident to the same number of faces.
But generally "even distribution" focusses not so much on the
induced tesselation, as it does on the distances and arrangement
of the points/vertices. For example, eight points can be placed
on the sphere further away from one another than is achieved by
the vertices of an inscribed cube: start with an inscribed cube,
twist the top face 45 degrees about the north pole, and then
move the top and bottom points along the surface towards the equator
a bit.
The various definitions of "evenly distributed" lead into moderately
complex mathematics. This topic happens to be a FAQ on sci.math as well
as on comp.graphics.algorithms; a much more extensive and rigorous
discussion written by Dave Rusin can be found at:
http://www.math.niu.edu/~rusin/known-math/...h/95/sphere.faq
A simple method of tesselating the sphere is repeated subdivision. An
example starts with a unit octahedron. At each stage, every triangle in
the tesselation is divided into 4 smaller triangles by creating 3 new
vertices halfway along the edges. The new vertices are normalized,
"pushing" them out to lie on the sphere. After N steps of subdivision,
there will be 8 * 4^N triangles in the tesselation.
A simple example of tesselation by subdivision is available at
ftp://ftp.cs.unc.edu/pub/users/jon/sphere.c
One frequently used definition of "evenness" is a distribution that
minimizes a 1/r potential energy function of all the points, so that in
a global sense points are as "far away" from each other as possible.
Starting from an arbitrary distribution, we can either use numerical
minimization algorithms or point repulsion, in which all the points
are considered to repel each other according to a 1/r^2 force law and
dynamics are simulated. The algorithm is run until some convergence
criterion is satisfied, and the resulting distribution is our approximation.
Jon Leech developed code to do just this. It is available at
ftp://ftp.cs.unc.edu/pub/users/jon/points.tar.gz.
See his README file for more information. His distribution includes
sample output files for various n < 300, which may be used off-the-shelf
if that is all you need.
Another method that is simpler than the above, but attains less
uniformity, is based on spacing the points along a spiral that
encircles the sphere.
Code available from links at http://cs.smith.edu/~orourke/.
What are coordinates for the vertices of an icosohedron?
Data on various polyhedra is available at
http://cm.bell-labs.com/netlib/polyhedra/index.html, or
http://netlib.bell-labs.com/netlib/polyhed...edra/index.html, or
http://www.netlib.org/polyhedra/index.html
For the icosahedron, the twelve vertices are:
(+- 1, 0, +-t), (0, +-t, +-1), and (+-t, +-1, 0)
where t = (sqrt(5)-1)/2, the golden ratio.
Reference: "Beyond the Third Dimension" by Banchoff, p.168.
How do I generate random points on the surface of a sphere?
There are several methods. Perhaps the easiest to understand is
the "rejection method": generate random points in an origin-
centered cube with opposite corners (r,r,r) and (-r,-r,-r).
Reject any point p that falls outside of the sphere of radius r.
Scale the vector to lie on the surface. Because the cube to sphere
volume ratio is pi/6, the average number of iterations before an
acceptable vector is found is 6/pi = 1.90986. This essentially
doubles the effort, and makes this method slower than the "trig
method." A timing comparison conducted by Ken Sloan showed that
the trig method runs in about 2/3's the time of the rejection method.
He found that methods based on the use of normal distributions are
twice as slow as the rejection method.
The trig method. This method works only in 3-space, but it is
very fast. It depends on the slightly counterintuitive fact (see
proof below) that each of the three coordinates is uniformly
distributed on [-1,1] (but the three are not independent,
obviously). Therefore, it suffices to choose one axis (Z, say)
and generate a uniformly distributed value on that axis. This
constrains the chosen point to lie on a circle parallel to the
X-Y plane, and the obvious trig method may be used to obtain the
remaining coordinates.
(a) Choose z uniformly distributed in [-1,1].
(b) Choose t uniformly distributed on [0, 2*pi).
© Let r = sqrt(1-z^2).
(d) Let x = r * cos(t).
(e) Let y = r * sin(t).
This method uses uniform deviates (faster to generate than normal
deviates), and no set of coordinates is ever rejected.
Here is a proof of correctness for the fact that the z-coordinate is
uniformly distributed. The proof also works for the x- and y-
coordinates, but note that this works only in 3-space.
The area of a surface of revolution in 3-space is given by
A = 2 * pi * int_a^b f(x) * sqrt(1 + [f'(x}]^2) dx
Consider a zone of a sphere of radius R. Since we are integrating in
the z direction, we have
f(z) = sqrt(R^2 - z^2)
f'(z) = -z / sqrt(R^2-z^2)
1 + [f'(z)]^2 = r^2 / (R^2-z^2)
A = 2 * pi * int_a^b sqrt(R^2-z^2) * R/sqrt(R^2-z^2) dz
= 2 * pi * R int_a^b dz
= 2 * pi * R * (b-a)
= 2 * pi * R * h,
where h = b-a is the vertical height of the zone. Notice how the integrand
reduces to a constant. The density is therefore uniform.
Here is simple C code implementing the trig method:
void SpherePoints(int n, double X[], double Y[], double Z[])
{
int i;
double x, y, z, w, t;
for( i=0; i< n; i++ ) {
z = 2.0 * drand48() - 1.0;
t = 2.0 * M_PI * drand48();
w = sqrt( 1 - z*z );
x = w * cos( t );
y = w * sin( t );
printf("i=%d: x,y,z=\t%10.5lf\t%10.5lf\t%10.5lf\n", i, x,y,z);
X[i] = x; Y[i] = y; Z[i] = z;
}
}
A complete package is available at
ftp://cs.smith.edu/pub/code/sphere.tar.gz (4K),
reachable from http://cs.smith.edu/~orourke/ .
If one wants to generate the random points in terms of longitude
and latitude in degrees, these equations suffice:
Longitude = random * 360 - 180
Latitude = [arccos( random * 2 - 1 )/pi ] * 180 - 90
References:
[Knuth, vol. 2]
[Graphics Gems IV] "Uniform Random Rotations"
What are Plucker coordinates?
A common convention is to write umlauted u as "ue", so you'll also see
"Pluecker". Lines in 3D can easily be given by listing the coordinates of
two distinct points, for a total of six numbers. Or, they can be given as
the coordinates of two distinct planes, eight numbers. What's wrong with
these? Nothing; but we can do better. Pluecker coordinates are, in a sense,
halfway between these extremes, and can trivially generate either. Neither
extreme is as efficient as Pluecker coordinates for computations.
When Pluecker coordinates generalize to Grassmann coordinates, as laid
out beautifully in [Hodge], Chapter VII, the determinant definition
is clearly the one to use. But 3D lines can use a simpler definition.
Take two distinct points on a line, say
P = (Px,Py,Pz)
Q = (Qx,Qy,Qz)
Think of these as vectors from the origin, if you like. The Pluecker
coordinates for the line are essentially
U = P - Q
V = P x Q
Except for a scale factor, which we ignore, U and V do not depend on the
specific P and Q! Cross products are perpendicular to their factors, so we
always have U.V = 0. In [Stolfi] lines have orientation, so are the same
only if their Pluecker coordinates are related by a positive scale factor.
As determinants of homogeneous coordinates, begin with the 4x2 matrix
[ Px Qx ] row x
[ Py Qy ] row y
[ Pz Qz ] row z
[ 1 1 ] row w
Define Pluecker coordinate Gij as the determinant of rows i and j, in that
order. Notice that Giw = Pi - Qi, which is Ui. Now let (i,j,k) be a cyclic
permutation of (x,y,z), namely (x,y,z) or (y,z,x) or (z,x,y), and notice
that Gij = Vk. Determinants are anti-symmetric in the rows, so Gij = -Gji.
Thus all possible Pluecker line coordinates are either zero (if i=j) or
components of U or V, perhaps with a sign change. Taking the w component
of a vector as 0, the determinant form will operate just as well on a
point P and vector U as on two points. We can also begin with a 2x4 matrix
whose rows are the coefficients of homogeneous plane equations, E.P=0,
from which come dual coordinates G'ij. Now if (h,i,j,k) is an even
permutation of (x,y,z,w), then Ghi = G'jk. (Just swap U and V!)
Got Pluecker, want points? No problem. At least one component of U is
non-zero, say Ui, which is Giw. Create homogeneous points Pj = Gjw + Gij,
and Qj = Gij. (Don't expect the P and Q that we started with, and don't
expect w=1.) Want plane equations? Let (i,j,k,w) be an even permutation of
(x,y,z,w), so G'jk = Giw. Then create Eh = G'hk, and Fh = G'jh.
Example: Begin with P = (2,4,
and Q = (2,3,5). Then U = (0,1,3) and
V = (-4,6,-2). The direct determinant forms are Gxw=0, Gyw=1, Gzw=3,
Gyz=-4, Gzx=6, Gxy=-2, and the dual forms are G'yz=0, G'zx=1, G'xy=3,
G'xw=-4, G'yw=6, G'zw=-2. Take Uz = Gzw = G'xy = 3 as a suitable non-zero
element. Then two planes meeting in the line are
(G'xy G'yy G'zy G'wy).P = 0
(G'xx G'xy G'xz G'xw).P = 0
That is, a point P is on the line if it satisfies both these equations:
3 Px + 0 Py + 0 Pz - 6 Pw = 0
0 Px + 3 Py - 1 Pz - 4 Pw = 0
We can also easily determine if two lines meet, or if not, how they pass.
If U1 and V1 are the coordinates of line 1, U2 and V2, of line 2, we look
at the sign of U1.V2 + V1.U2. If it's zero, they meet. The determinant form
reveals even permutations of (x,y,z,w):
G1xw G2yz + G1yw G2zx + G1zw G2xy + G1yz G2xw + G1zx p2yw + G1xy p2zw
Two oriented lines L1 and L2 can interact in three different ways:
L1 might intersect L2, L1 might go clockwise around L2, or L1 might go
counterclockwise around L2. Here are some examples:
| L2 | L2 | L2
L1 | L1 | L1 |
-----+-----> -----------> -----|----->
| | |
V V V
intersect counterclockwise clockwise
| L2 | L2 | L2
L1 | L1 | L1 |
<----+----- <----|------ <-----------
| | |
V V V
The first and second rows are just different views of the same lines,
once from the "front" and once from the "back." Here's what they might
look like if you look straight down line L2 (shown here as a dot).
L1 ---------->
-----o----> L1 o L1 o
---------->
intersect counterclockwise clockwise
The Pluecker coordinates of L1 and L2 give you a quick way to test
which of the three it is.
cw: U1.V2 + V1.U2 < 0
ccw: U1.V2 + V1.U2 > 0
thru: U1.V2 + V1.U2 = 0
So why is this useful? Suppose you want to test if a ray intersects
a triangle in 3-space. One way to do this is to represent the ray and
the edges of the triangle with Pluecker coordinates. The ray hits the
triangle if and only if it hits one of the triangle's edges, or it's
"clockwise" from all three edges, or it's "counterclockwise" from all
three edges. For example...
o _
| |\ ...in this picture, the ray
| \ is oriented counterclockwise
------ \ --> from all three edges, so it
| \ must intersect the triangle.
v \
o-----> o
Using Pluecker coordinates, ray shooting tests like this take only
a few lines of code.
Grassmann coordinates allow similar methods to be used for points,
lines, planes, and so on, and in a space of any dimension. In the
case of lines in 2D, only three coordinates are required:
Gxw = Px-Qx = -G'y
Gyw = Py-Qy = G'x
Gxy = PxQy-PyQx = G'w
Since P and Q are distinct, Giw is non-zero for i = x or y. Then
(Gix,Giy,Giw) is a point P1 on L
(Gxw,Gyw,Gww)+P1 is a point P2 on L
(G'x,G'y,G'w).P = 0 is an equation for L
Two lines in a 2D perspective plane always meet, perhaps in an
ideal point (meaning they're parallel in ordinary 2D). Calling
their homogeneous point of intersection P, the computation from
Grassmann coordinates nicely illustrates the convenience. (See
Subj 1.03, "How do I find intersections of 2 2D line segments?")
For i = x,y,w, set
Pi = G'j H'k ^Ư G'k H'j, where (i,j,k) is even
See [Hodge] for a thorough discussion of the theory, [Stolfi] for
a little theory with a concise implementation for low dimensions
(see Subj. 0.04), and these articles for further discussion:
J. Erickson, Pluecker Coordinates, Ray Tracing News 10(3) 1997,
http://www.acm.org/tog/resources/RTNews/ht...l/rtnv10n3.html.
Ken Shoemake, Pluecker Coordinate Tutorial,
Ray Tracing News 11(1) 1998,
http://www.acm.org/tog/resources/RTNews/ht...l/rtnv11n1.html.