namespace CGAL {
/*!

\mainpage User Manual
\anchor Chapter_2D_Intersection_of_Curves
\anchor I1_ChapterSurfaceSweep

\cgalAutoToc
\authors Baruch Zukerman, Ron Wein, and Efi Fogel

\section Surface_sweep_2Introduction Introduction

Let \f$ {\mathcal C} = \{C_1, C_2, \ldots, C_n\}\f$ be a set of
curves.  We wish to compute all intersection points between two curves
in the set in an output-sensitive manner, without having to go over
all \f$ O(n^2)\f$ curve pairs. To this end, we sweep an imaginary line
\f$ l\f$ from \f$ x = -\infty\f$ to \f$ x = \infty\f$ over the
plane. While sweeping the plane, we keep track of the order of curves
intersecting it.  This order changes at a finite number of <I>event
points</I>, such that we only have to calculate the intersection
points between two curves when they become contiguous. For more
details on the <I>surface-sweep algorithm</I> see, for example,
\cgalCite{bkos-cgaa-00}, Chapter 2.

This chapter describes three functions implemented using the
surface-sweep algorithm: given a collection of input curves, compute all
intersection points, compute the set of subcurves that are pairwise
interior-disjoint induced by them, and checking whether there is at
least one pair of curves among them that intersect in their interior.

The implementation is robust. It supports general curves and handles
all degenerate cases, including overlapping curves, vertical segments,
and tangency between curves. The robustness of the algorithm is
guaranteed if the functions are instantiated with a traits class that
employs certified computations. This traits class must be a model of
the `ArrangementTraits_2` concept - see the Chapter \ref
chapterArrangement_on_surface_2 "2D Arrangements" for more details.

The complexity of the surface-sweep algorithm is \f$ O((n +
k)\log{n})\f$ where \f$ n\f$ is the number of the input curves and \f$
k\f$ is the number of intersection points induced by these curves.

\section Surface_sweep_2Example Example

The simple program listed below computes intersection points induced by
a set of four input segments illustrated in \cgalFigureRef{SL_secsimple}.

\cgalFigureBegin{SL_secsimple,sl_simple.png}
Four input segments
\cgalFigureEnd

\cgalExample{Surface_sweep_2/plane_sweep.cpp}

\section Surface_sweep_2Design Design and Implementation History

The current version of the surface-sweep algorithm was written by Efi
Fogel, based on previous implementations by Baruch Ester Ezra, Tali
Zvi, and Baruch Zukerman.

*/
} /* namespace CGAL */
