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.



Related Publications, Etc.


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

Please report any problems to Andrea Mantler at
Back to Jack's Computational Geometry Demo page.