next up previous contents index CD CD Algorithms
Next: Convex Hull Up: Computational Geometry Previous: Computational Geometry

Robust Geometric Primitives



Input description: A point p and a line segment l, or two line segments tex2html_wrap_inline29806 and tex2html_wrap_inline29808 .

Problem description: Does p lie over, under, or on l? Does tex2html_wrap_inline29810 intersect tex2html_wrap_inline29812 ?

Discussion: Implementing basic geometric primitives is a task fraught with peril, even for such simple tasks as returning the intersection point of two lines.    What should you return if the two lines are parallel, meaning they don't intersect at all? What if the lines are identical, so the intersection is not a point but the entire line? What if one of the lines is horizontal, so that in the course of solving the equations for the intersection point you are likely to divide by zero? What if the two lines are almost parallel, so that the intersection point is so far from the origin as to cause arithmetic overflows? These issues become even more complicated for intersecting line segments, since there are a bunch of other special cases that must be watched for and treated specially.

If you are new to implementing geometric algorithms, I suggest that you study O'Rourke's Computational Geometry in C [O'R94] for practical advice and complete implementations of basic geometric algorithms and data structures. You are likely to avoid many headaches by following in his footsteps.

There are two different issues at work here: geometric degeneracy and numerical stability. Degeneracy refers to annoying special cases that must be treated in substantially different ways, such as when two lines intersect in more or less than a single point. There are three primary approaches to dealing with degeneracy:   

Geometric computations often involve floating-point arithmetic, which leads to problems with overflows and numerical precision.    There are three basic approaches to the issue of numerical stability:

The difficulties associated with producing robust geometric software are still under attack by researchers. The best practical technique is to base your applications on a small set of geometric primitives that handle as much of the low-level geometry as possible. These primitives include:

Check out the implementations described below before you attempt to build your own.

Implementations: LEDA (see Section gif) provides a very complete set of geometric primitives for planar geometry, written in C++.   If you are writing a significant geometric application, you should consider basing it on LEDA. At least check them out before you try to write your own.  

O'Rourke [O'R94] provides implementations in C of most of the primitives discussed in this section. See Section gif. These primitives were implemented primarily for exposition rather than production use, but they should be quite reliable and might be more appropriate than LEDA for small applications.

A robust implementation of the basic geometric primitives in C++ using exact arithmetic, by Jonathan Shewchuk, is available at tex2html_wrap_inline29838 quake/robust.html. Don't expect them to be very fast.

Pascal implementations of basic geometric primitives appear in [MS91]. Sedgewick [Sed92] provides fragments of the basic primitives in C++. See Section gif for both of them.

An alternative C++ library of geometric algorithms and data structures (although you are almost certainly better off sticking to LEDA) is Geolab,   written by Pedro J. de Rezende, Welson R. Jacometti, Cesar N. Gon, and Laerte F. Morgado, Universidade Estadual de Campinas, Brazil. Geolab requires the SUN C++ compiler, but a Sparc binary and visualization environment is included along with all source code. Geolab appears to be primarily for the brave, since its robustness is uncertain and it contains little documentation, but it does provide 40 algorithms, including such advanced topics as farthest point Voronoi diagrams, nearest neighbor search, and ray shooting.    

Notes: O'Rourke [O'R94] provides an implementation-oriented introduction to computational geometry, which stresses robust geometric primitives and is recommended reading.

Shewchuk [She96] and Fortune and van Wyk [FvW93] present careful studies on the costs of using arbitrary-precision arithmetic for geometric computation. By being careful about when to use it, reasonable efficiency can be maintained while achieving complete robustness. Other approaches to achieving robustness include [DS88, Hof89, Mil89].

Related Problems: Intersection detection (see page gif), maintaining arrangements (see page gif).    

next up previous contents index CD CD Algorithms
Next: Convex Hull Up: Computational Geometry Previous: Computational Geometry

Mon Jun 2 23:33:50 EDT 1997