next up previous contents index CD CD Algorithms
Next: Bin Packing Up: Computational Geometry Previous: Point Location

Intersection Detection



Input description: A set S of lines and line segments tex2html_wrap_inline30187 or a pair of polygons or polyhedra tex2html_wrap_inline30189 and tex2html_wrap_inline30191 .

Problem description: Which pairs of line segments intersect each other? What is the intersection of tex2html_wrap_inline30193 and tex2html_wrap_inline30195 ?

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

Issues arising in intersection detection include:

Planar sweep algorithms can be used to efficiently compute the intersections among a set of line segments, or the intersection/union of two polygons. These algorithms keep track of interesting changes as we sweep a vertical line from left to right over the data. At its leftmost position, the line intersects nothing, but as it moves to the right, it encounters a series of events:   

Keeping track of what is going on requires two data structures. The future is maintained by an event queue, a priority queue ordered by the x-coordinate of all possible future events of interest: insertion, deletion, and intersection. See Section gif for priority queue implementations. The present is represented by the horizon, an ordered list of line segments intersecting the current position of the sweepline. The horizon can be maintained using any dictionary data structure, such as a balanced tree.       

To adapt this approach to computing the intersection or union of polygons, we modify the processing of the three event types to keep track of what has occurred to the left of the sweepline. This algorithm can be considerably simplified for pairs of convex polygons, since (1) at most four polygon edges intersect the sweepline, so no horizon data structure is needed and (2) no event-queue sorting is needed, since we can start from the leftmost vertex of each polygon and proceed to the right by following the polygonal ordering.

Implementations: LEDA (see Section gif) provides a C++ implementation of the Bentley-Ottmann sweepline algorithm [BO79], finding all k intersection points between n line segments in the plane in tex2html_wrap_inline30203 time.   

O'Rourke [O'R94] provides a robust program in C to compute the intersection of two convex polygons. See Section gif.  

RAPID is a ``Rapid and Accurate Polygon Interference Detection library'' for large environments composed of polygonal models. It is free for noncommercial use and available from tex2html_wrap_inline30205 geom/OBB/OBBT.html.  

Model Pascal subroutines for convexity testing and for finding an intersection in a set of line segments appear in [MS91]. See Section gif for details. XTango (see Section gif) includes an animation of polygon clipping against a polygonal window.     

Finding the mutual intersection of a collection of half-spaces is a special case of higher-dimensional convex hulls, and Qhull [BDH97] is convex hull code of choice for general dimensions. Qhull has been widely used in scientific applications and has a well-maintained home page at  

Notes: Good expositions on line segment intersection detection [BO79, SH75] include [CLR90, Man89, NH93, PS85]. Good expositions on polygon and polyhedra intersection [HMMN84, MP78, SH76] include [PS85]. Preparata and Shamos [PS85] provide a good exposition on the special case of finding intersections and unions of axis-oriented rectangles, a problem that arises often in VLSI design.  

An optimal tex2html_wrap_inline30207 algorithm for computing line segment intersections is due to Chazelle and Edelsbrunner [CE92]. Simpler, randomized algorithms achieving the same time bound are thoroughly presented by Mulmuley [Mul94].  

Surveys on hidden-surface removal include [Dor94, SSS74].  

Related Problems: Maintaining arrangements (see page gif), motion planning (see page gif).    

next up previous contents index CD CD Algorithms
Next: Bin Packing Up: Computational Geometry Previous: Point Location

Mon Jun 2 23:33:50 EDT 1997