The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.1 Robust Geometric Primitives

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A point $p$ and a line segment $l$, or two line segments $l_1$ and $l_2$.

Problem: Does $p$ lie over, under, or on $l$? Does $l_1$ intersect $l_2$?

Excerpt from The Algorithm Design Manual: 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.


Implementations

  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 10)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 9)
  • 3D Convex Hull algorithm in Java (C) (rating 8)
  • Exact Geometric Computation (EGC) (C++,C) (rating 8)
  • Fast Robust Predicates for Computational Geometry (C) (rating 7)
  • Geolab -- Computational Geometry System (C++) (rating 4)

  • Recommended Books

    Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky Computational Geometry in C by Joseph O'Rourke Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro

    Related Problems


      
    Determinants and Permanents
      
    Intersection Detection
      
    Maintaining Line Arrangements



    This page last modified on 2008-07-10 .
    www.algorist.com