Polygonal Intersection

From Progteam

Revision as of 23:08, 23 October 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Tests for two polygons intersection.

Find all intersections

The input for the Bentley-Ottmann algorithm is a collection W = {Li} of line segments Li, and its output will be a set L = {Ij} of intersection points. This algorithm is referred to as a "sweep line algorithm" because it's operation can be visualized as having another "sweep line" SL sweeping over the collection W and collecting information as it passes over the individual segments Li. The information collected is basically an ordered list of all segments in W that are currently intersected by SL. The data structure maintaining this information is often also called the "sweep line". It also detects and outputs intersections as it discovers them. The process by which it discovers intersections is the heart of the algorithm and its efficiency.

To implement the sweep logic, we must first linearly order the segments of W to determine the sequence in which SL encounters them. Actually, we need to order the endpoints {Ei0, Ei1} of all segments Li so we can detect when SL starts and stops to intersecting each Li. Traditionally, endpoints are ordered by increasing x and then increasing y-coordinate values, but any linear order will do (some authors prefer a decreasing y and then increasing x value). With the traditional ordering, the sweep line is vertical and moves from left to right as it encounters each segment, as shown in the diagram:

At any point in the algorithm, the sweep line SL intersects those segments with one endpoint to the left of it and the other endpoint to the right. The SL data structure keeps track of these segments by: (1) adding a segment when its left endpoint is encountered, and (2) deleting a segment when its right endpoint is encountered. The SL also maintains the segments in a list ordered by an "above-below" relation. So, to add or delete a segment, its position in the list must be determined, and this can be done by a worst-case O(log n) binary search of the current SL segments. But, besides adding or deleting segments, there is another event that changes the structure of the SL; namely, whenever two current segments intersect, then their positions in the ordered list are swapped. Given the two segments, which must be neighbors in the list, this swap is an O(log n) operation.

To organize all this, the algorithm has an ordered "event queue" x whose elements cause a change in the SL segment list. Initially, x is set to the sweep-ordered list of all segment endpoints. But as intersections between segments are found, then they are also added to x in the same sweep-order as used for the endpoints One must test, though, to avoid inserting duplicate intersections onto the event queue. The example in the above diagram shows how this can happen. At event 2, segments s1 and s2 cause intersection I12 to be computed and put on the queue. Then, at event 3, segment s3 comes between and separates s1 and s2. Next, at event 4, s1 and s3 swap places on the sweep line, and s1 is brought next to s2 again causing I12 to be computed again. But, there can only be one event for each intersection, and I12 cannot be put on the queue again. So, when an intersection is being put on the queue, we must find its potential x-sorted location in the queue, and check that it is not already there. Since there is at most one intersect point for any two segments, labeling an intersection with identifiers for the segments is sufficient to uniquely identify it. As a result of all this, the maximum size of the event queue = 2n + k £ 2n + n2, and an insertion into it can be done with at worst an O(log (2n + n2)) = O(log n) binary search.

But, what does all this have to do with efficiently finding the complete set of segment intersections? Well, as segments are sequentially updated on the SL list, their possible intersection with other eligible segments is determined. When a valid intersection is found, then it is inserted into the event queue. Further, when an intersection-event on x is processed during the sweep, then it causes a re-ordering of the SL list, and is also added to the output list L. In the end, when all events have been processed, L will contain the complete set of all intersections.

However, there is one critical detail, the heart of the algorithm, that we still need to describe; namely, how does one compute a valid intersection? Clearly, two segments can only intersect if they occur simultaneously on the sweep-line at some time. But this by itself is not enough to make the algorithm efficient. The important observation is that two intersecting segments must be immediate above-below neighbors on the sweep-line. Thus, there are just a few restricted cases for which possible intersections must be computed:

  1. When a segment is added to the SL, determine if it intersects with its above and below neighbors.
  2. When a segment is deleted from the SL, its previous above and below neighbors are brought together as new neighbors. So, their possible intersection needs to be determined.
  3. At an intersection event, two segments switch positions in the SL, and their intersection with their new neighbors must be determined.

This means that for the processing of any one event (endpoint or intersection) of x, there are at most 2 intersection determinations that need to be made. One detail remains, namely the time needed to add, find, swap, and remove segments from the SL structure. To do this, implement SL as a balanced binary tree (such as an AVL, a 2-3, or a red-black tree) which guarantees that these operations take at most O(log n) time since n is the maximum size of SL. Thus, each of the (2n+k) events has at worst O(log n) processing to do. Adding everything up, the efficiency of the algorithm = O(initial-sort) + O(event-processing) = O(n log n) + O((2n+k) log n) = O((n+k) log n).

    Initialize event queue x = all segment endpoints;
    Sort x by increasing x and y;
    Initialize sweep line SL to be empty;
    Initialize output intersection list L to be empty;

    While (x is nonempty) {
        Let E = the next event from x;
        If (E is a left endpoint) {
            Let segE = E's segment;
            Add segE to SL;
            Let segA = the segment above segE in SL;
            Let segB = the segment below segE in SL;
            If (I = Intersect( segE with segA) exists)
                Insert I into x;
            If (I = Intersect( segE with segB) exists)
                Insert I into x;
        }
        Else If (E is a right endpoint) {
            Let segE = E's segment;
            Let segA = the segment above segE in SL;
            Let segB = the segment below segE in SL;
            Remove segE from SL;
            If (I = Intersect( segA with segB) exists)
                If (I is not in x already) Insert I into x;
        }
        Else {  // E is an intersection event
            Add E to the output list L;
            Let segE1 above segE2 be E's intersecting segments in SL;
            Swap their positions so that segE2 is now above segE1;
            Let segA = the segment above segE2 in SL;
            Let segB = the segment below segE1 in SL;
            If (I = Intersect(segE2 with segA) exists)
                If (I is not in x already) Insert I into x;
            If (I = Intersect(segE1 with segB) exists)
                If (I is not in x already) Insert I into x;
        }
        remove E from x;
    }
    return L;
}

Yes/no test

If one only wants to know if an intersection exists, then as soon as any intersection is detected, the routine can terminate immediately. This results in a simplified algorithm. Intersections don't ever have to be put on the event queue, and so its size is just 2n for the endpoints of every segment. Further, code for processing this non-existent event can be removed. Also, the event (priority) queue can be implemented as a simple ordered array since it never changes. Additionally, no output list needs to be built since the algorithm terminates as soon as any intersection is found. Thus, this algorithm needs only O(n) space and runs in O(n log n) time. This is the original algorithm of [Shamos & Hoey, 1976]. The pseudo-code for this simplified routine is:

    Initialize event queue x = all segment endpoints;
    Sort x by increasing x and y;
    Initialize sweep line SL to be empty;

    While (x is nonempty) {
        Let E = the next event from x;
        If (E is a left endpoint) {
            Let segE = E's segment;
            Add segE to SL;
            Let segA = the segment above segE in SL;
            Let segB = the segment below segE in SL;
            If (I = Intersect( segE with segA) exists)
                return TRUE;   // an Intersect Exists
            If (I = Intersect( segE with segB) exists)
                return TRUE;   // an Intersect Exists
        }
        Else {  // E is a right endpoint
            Let segE = E's segment;
            Let segA = the segment above segE in SL;
            Let segB = the segment below segE in SL;
            Delete segE from SL;
            If (I = Intersect( segA with segB) exists)
                return TRUE;   // an Intersect Exists
        }
        remove E from x;
    }
    return FALSE;      // No Intersections
}
Personal tools