# Sweep Line

### Abstract

Let*C:={c*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

_{1},c_{2}, ...c_{n}}*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
retaled 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.

### Links

- CGAL package: 2D Intersection of Curves

### Contact

Baruch Zukerman | ||

Ron Wein | ||

Tali Zvi | ||

Eti Ezra |