Computational Geometry in C (Second Edition)

Second Edition: printed 28 September 1998. Purchasing information:

Hardback: ISBN 0521640105, $69.95 (55.00 PST)

Paperback: ISBN 0521649765, $29.95 (19.95 PST)

Cambridge University Press servers: in Cambridge; in New York; Cambridge (NY) catalog entry (includes jacket text and chapter titles). Also amazon.com.

Contents:

Some highlights:

376+xiii pages, 270 exercises, 210 figures, 259 references.
Although I've retained the title ...in C, all code has been translated to Java, and both C and Java code is available free.
Java Applet to permit interactive use of the code: CompGeom Java Applet
First Edition code improved: Postscript output, more efficient, more robust.
New code (see below).
Expanded coverage of randomized algorithms, ray-triangle intersection, and other topics (see below).

Basic statistics (in comparison to First Edition):

New code:

To compute the Delaunay triangulation from the 3D hull in O(n^2).
To intersect a ray with a triangle.
To decide if a point is inside a polyhedron.
To compute the convolution (Minkowski sum) of a convex polygon with a general polygon.
To generate regularly distributed points on the surface of a sphere (see Figure above).

Significant code improvements:

Triangulation code now O(n^2) rather than n^3. Uses lists rather than arrays.
Graham scan handles collinear points more cleanly.
Convex hull in 3D starts with double-covered triangle. Volume determinant computations much faster. Overflow handled better.
Segment-segment intersection code handles special cases cleanly.
Point-in-polygon code classifies all boundary points correctly.
Intersection of convex polygons handles special cases more uniformly.
Robot arm configuration more robust.

New coverage of these topics:

More extensive (but still partial) solutions manual available. Write me at orourke@cs.smith.edu.

Errata (in 2nd Edition):

Reviews (of 2nd Ed.):

Last Update to this page: