Close this search box.

Sweep Line


Sweep Line

Let \(C:=\{c_1,c_2,\ldots,c_n\}\) be a set of curves for which we want to compute all intersections. We want to avoid testing pairs of curves that are far apart. To find the intersecting pairs we imagine sweeping a line \(l\) from left to right over the plane, starting from a position left to all curves. While we sweep the plane, we keep track of all curves intersecting it.

This type of algorithm is called a plane sweep algorithm and the line \(l\) is called the sweep line. The status of the sweep line is the set of curves intersecting it. The status changes while the sweep line moves to the right, but not continuously. The sweep line status is updated at specific points called the event points. These points are actually the endpoints of all curves and their intersection points. The initial set of event points are only the endpoints of the curves. More event points are added as intersection points are calculated.

The Sweep_line_2 class implements the plane sweep algorithm, and can be used to compute the intersection points of a given collection curves, the disjoint-interior subcurves induced by such a collection, and a few other related tasks.

In particular, we take advantage of the implemented sweep line algorithm to construct a Planar Map of intersecting curves efficiently. See CGAL::Pm_with_intersection for more details.



Baruch Zukerman
Ron Wein
Tali Zvi
Esther Ezra

Yair Oz - Webcreator


Skip to content