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?

Excerpt from The Algorithm Design Manual: Intersection detection is a fundamental geometric primitive that arises in many applications. Picture a virtual-reality simulation of an architectural model for a building. The illusion of reality vanishes the instant the virtual person walks through a virtual wall. To enforce such physical constraints, any such intersection between polyhedral models must be immediately detected and the operator notified or constrained.

Another application of intersection detection is design rule checking for VLSI layouts. A minor design mistake resulting in two crossing metal strips can short out the chip, but such errors can be detected before fabrication using programs to find all intersections between line segments.

The best books available for this problem are Computational Geometry in C by Joseph O'Rourke and Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf.


Implementations

  • -CLIP - Collision detection algorithm for polyhedral objects (C++) (rating 9)
  • V-COLLIDE- The Collision detection library (Binary) (rating 8)
  • RAPID - Robust and Accurate Polygon Interface detection (Binary) (rating 8)
  • SOLID- a library for interface detection (C++) (rating 7)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Qhull - higher dimensional convex hull program (C) (rating 5)
  • 3D Convex Hull algorithm in Java (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


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .