Line Intersection: a sweepline algorithm
only compare those segments which are "swept" together
The search for intersections of line segments can be made much faster if we only compare those line segments which are near to each other. One device for doing this is to allow a horizontal line to sweep down the area; only those line segments which the "sweepline" intersects could possibly intersect each other.
The segments which the sweepline intersect forms a "working set" of line segments, amongst which we test for intersections. If the working set is ordered from left to right, then only neighbors in the working set could intersect each other. As the sweepline moves down, segments enter and leave the working set, and the working set is maintained in left-to-right order. Every time the working set changes, we search again for possible intersections.
Movies are available for fifty (three movies), one hundred, two hundred, and five hundred (one movie each) line segments ; one of the fifty-segment movies includes pauses for questions to the viewer. Remember the guidelines for use of these movies.
|
|
|
|
|
|
|
|
|
|
|
