Chapter 26
Sweep line

Introduction

Given a collection $$C of possibly intersecting (not necessarily $$x-monotone) curves in the plane, the Sweep_line_2 class can calculate the intersection points between the curves of $$C. It can also calculate the disjoint-interior subcurves induced by $$C, or rather return an indication whether any two curves in $$C intersect.

In order to use the sweep line algorithm, an instance of the Sweep_line_2 class is to be constructed.

The sweep line algorithm is also used in Planar_map_with_intersections_2<Planar_map>.

• Sweep_line_2<CurveInputIterator, SweepLineTraits_2>

• SweepLineTraits_2