1.6.8 Intersection Detection

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A set S of lines and line segments l_1,...,l_n , or a pair of polygons or polyhedra P_1 and P_2 .

Problem: Which pairs of line segments intersect each other? What is the intersection of P_1 and P_2 ?

Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Joseph O'Rourke's Computational Geometry (C) (rating 5)
  • Qhull - higher dimensional convex hull program (C) (rating 5)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 1)

    Related Problems

  • Robust Geometric Primitives
  • Maintaining Line Arrangements
  • Motion Planning

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .