Geometric algorithms solve problems in *computational
geometry*. Computational geometry is an area of mathematics in which we perform
calculations related to geometric objects, such as points, lines,
polygons, and the like. One interesting characteristic of problems in
computational geometry is that many have a distinctly visual quality
about them. In fact, for many problems we can find solutions simply by
looking at visual representations of them. For example, how difficult is
it visually to determine whether two line segments intersect? On the
other hand, because computing requires more of a computational approach,
even coming up with solutions for seemingly simple problems like this
can be deceptively challenging. This chapter presents three fundamental
geometric algorithms. The first two perform basic operations that are
used frequently in solving more complicated problems in computational
geometry. The third is a relatively simple example of a
three-dimensional geometric algorithm. Example 17.1 is a header for the algorithms
presented in this chapter. This chapter covers:

- Testing whether line segments intersect
Using a simple algorithm consisting of two steps: first, we test whether the bounding boxes of the line segments intersect, and then we test whether the line segments straddle each other. If both tests are successful, the two line segments intersect.

- Convex hulls
Minimum-size convex polygons that enclose sets of points. A polygon is convex ...

Start Free Trial

No credit card required