Red & Blue
Line Segment Intersections
(Applet written by Andrea Mantler)
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.
-
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.