Chapter 26
Sweep line

Ester Ezra and Tali Zvi

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>.