Red & Blue Line Segment Intersections

Brief Description

The following geometric problem arises in computer graphics and geographic information systems (GIS): compute the arrangement of a set of n segments that can be colored red and blue so that there are no red/red or blue/blue crossings. Some important geometric problems can be abstracted as red/blue segment intersection: polygon clipping in computer graphics, boolean operations in 2D computer-aided design (CAD/CAM), and map overlay in GIS.

The above applet uses a sweep algorithm which runs in O(nlogn+k) time to compute and report an arrangement with k intersections. The predicates used require only twice the input precision (the lower limit), and degenerate cases are easy to handle.

The algorithm can be modified so that it only counts the intersections, or computes the arrangement in compact form, reducing the running time to O(nlogn).

More information can be found in our publications.

Instructions

Select a file to use for both the red and blue line segments from the choice boxes.
Click "Run". The number of intersections will appear in the text box.
The current segment and the segments it intersects will be highlighted. To iterate through the segments, (shift) click the mouse button in the drawing area. Clicking iterates from left to right, first in one colour and then in the other. Shift clicking iterates in reverse.

Notes

You must choose data for both the red and blue line segments before running the algorithm.
If red and blue segments overlap, the overlapping section will be drawn in purple.
When multiple segments share the same endpoint, we count the intersections between every pair of segments. (This does not affect the running time of the code.)
If one segment ends on a second segment, the second segment is broken. This reduces the number of different kinds of degenerate cases to handle, without increasing the precision of the data.
The intersection counts reported have changed because we have fixed some small bugs in the code.

Related Publications, Etc.

"Intersecting Red and Blue Line Segments in Optimal Time and Precision", Andrea Mantler and Jack Snoeyink.
- Two page abstract accepted at the Japan Conference on Discrete and Computational Geometry 2000, November 22-25, 2000.
- Full paper, accepted for publication in the Proceedings of Jcdcg2000, Lecture Notes in Computer Science, © Springer Verlag.
Andrea Mantler's Comp 258 course project, Fall 1999.

Support

This material is based upon work supported by the National Science Foundation under Grant No. 9988742.

Please report any problems to Andrea Mantler at mantler@cs.unc.edu.

Back to Jack's Computational Geometry Demo page.