Line Intersection: a "sweep line" algorithm
|
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. Click the Download button at the right to download a zipped file of all movies described on this page. |