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.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.


Implementations

  • V-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)
  • CGAL: The Computational Geometry Algorithms Library (C++) (rating 7)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)

  • Recommended Books

    Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Computational Geometry in C by Joseph O'Rourke Computational Geometry: an introduction through randomized algorithms by K. Mulmuley
    Algorithms and Data Structures with applications to graphics and geometry by J. Nievergelt and K. Hinrichs Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein
    Introduction to Algorithms by U. Manber Computational Geometry by F. Preparata and M. Shamos

    Related Links

  • UNC's Collision Detection/Proximity Query Packages

    Related Problems


      
    Robust Geometric Primitives
      
    Maintaining Line Arrangements
      
    Motion Planning



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