Intersection Detection

  

 

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

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

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:

• Do you want to compute the intersection or just report it? - We distinguish between intersection detection and computing the actual intersection. The latter problem is obviously harder than the former and is not always necessary. In the virtual-reality application above, it might not be important to know exactly where we hit the wall, just that we hit it.
• Are you intersecting lines or line segments? - The big difference here is that any two lines with different slopes must intersect at exactly one point. By comparing each line against every other line, all points of intersections can be found in constant time per point, which is clearly optimal. Constructing the arrangement of the lines provides more information than just intersection points and is discussed in Section .   

  Finding all the intersections between n line segments is considerably more challenging. Even the basic primitive of testing whether two line segments intersect is not as trivial as it might seem, and this is discussed in Section . To find all intersections, we can explicitly test each line segment against each other line segment and thus find all intersections in time. Each segment can always intersect each other segment, yielding a quadratic number of intersections, so in the worst case, this is optimal. For many applications, however, this worst case is not very interesting.

• How many intersection points do you expect? - Sometimes, as in VLSI design rule checking, we expect the set of line segments to have few if any intersections. What we seek is an algorithm whose time is output sensitive, taking time proportional to the number of intersection points.  

  Such output-sensitive algorithms exist for line-segment intersection, with the fastest algorithm taking time, where k is the number of intersections. Such algorithms are sufficiently complicated that you should use an existing implementation if you can. These algorithms are based on the sweepline approach, discussed below.

• Can you see point x from point y? - Visibility queries ask whether vertex x can see vertex y unobstructed in a room full of obstacles. This can be phrased as the following line-segment intersection problem: does the line segment from x to y intersect any obstacle? Such visibility problems arise in robot motion planning (see Section ) and in hidden-surface elimination for computer graphics.     
• Are the intersecting objects convex? - Better intersection algorithms exist when the line segments form the boundaries of polygons. The critical issue here becomes whether the polygons are convex. Intersecting a convex n-gon with a convex m-gon can be done in O(n+m) time, using a sweepline algorithm as discussed below. This is possible because the intersection of two convex polygons must form another convex polygon using at most n+m vertices.  

  However, the intersection of two nonconvex polygons is not so well behaved. Consider the intersection of two ``combs'' generalizing the Picasso-like frontspiece to this section. As illustrated, the intersection of nonconvex polygons may be disconnected and have quadratic size in the worst case.  

  Intersecting two polyhedra is somewhat more complicated than intersecting polygons, because two polyhedra can intersect even when no edges do. Consider the example of a needle piercing the interior of a face. In general, however, the same issues arise for both polygons and polyhedra.

• Are you searching for intersections repeatedly with the same basic objects? - In the walk-through application described above, the room and the objects in it don't change between one scene and the next. Only the person moves, and, further, the intersections are rare.

  One common solution is to approximate the objects in the scene by simpler objects that enclose them, such as boxes. Whenever two enclosing boxes intersect, then the underlying objects might intersect, and so further work is necessary to decide the issue. However, it is much more efficient to test whether simple boxes intersect than more complicated objects, so we win if collisions are rare. Many variations on this theme are possible, but this idea can lead to large performance improvements for complicated environments.   

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:   

• Insertion - the leftmost point of a line segment may be encountered, and it is now available to intersect some other line segment.
• Deletion - the rightmost point of a line segment is encountered. This means that we have completely swept over the segment on our journey, and so it can be deleted from further consideration.
• Intersection - if we maintain the active line segments that intersect the sweep line as sorted from top to bottom, the next intersection must occur between neighboring line segments. After the intersection, these two line segments swap their relative order.

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 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 ) provides a C++ implementation of the Bentley-Ottmann sweepline algorithm [BO79], finding all k intersection points between n line segments in the plane in time.   

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

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 http://www.cs.unc.edu/ 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 for details. XTango (see Section ) 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 http://www.geom.umn.edu/software/qhull/.  

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 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 ), motion planning (see page ).