CGAL 5.1.2 - 2D Intersection of Curves
|
This chapter describes three functions implemented using the sweep-line algorithm: given a collection \( {\mathcal C}\) of planar curves, compute all intersection points among them, obtain the set of maximal pairwise interior-disjoint subcurves of the curves in \( {\mathcal C}\), or check whether there is at least one pair of curves in \( {\mathcal C}\) that intersect in their interior.
The first two operations are performed in an output-sensitive manner.
Functions | |
template<class InputIterator , class OutputIterator > | |
OutputIterator | CGAL::compute_intersection_points (InputIterator curves_begin, InputIterator curves_end, OutputIterator points, bool report_endpoints=false) |
Given a range of curves, compute all intersection points between two (or more) input curves. More... | |
template<class InputIterator , class OutputIterator , class Traits > | |
OutputIterator | CGAL::compute_intersection_points (InputIterator curves_begin, InputIterator curves_end, OutputIterator points, bool report_endpoints=false, Traits traits) |
Given a range of curves, compute all intersection points between two (or more) input curves. More... | |
template<class InputIterator , class OutputIterator > | |
OutputIterator | CGAL::compute_subcurves (InputIterator curves_begin, InputIterator curves_end, OutputIterator subcurves, bool multiple_overlaps=false) |
Given a range of curves, compute all \( x\)-monotone subcurves that are pairwise disjoint in their interior, as induced by the input curves. More... | |
template<class InputIterator , class OutputIterator , class Traits > | |
OutputIterator | CGAL::compute_subcurves (InputIterator curves_begin, InputIterator curves_end, OutputIterator subcurves, bool multiple_overlaps=false, Traits traits=Default_traits()) |
Given a range of curves, compute all \( x\)-monotone subcurves that are pairwise disjoint in their interior, as induced by the input curves. More... | |
template<class InputIterator > | |
bool | CGAL::do_curves_intersect (InputIterator curves_begin, InputIterator curves_end) |
Given a range of curves, check whether there is at least one pair of curves that intersect in their interior. More... | |
template<class InputIterator , class Traits > | |
bool | CGAL::do_curves_intersect (InputIterator curves_begin, InputIterator curves_end, Traits traits=Default_traits()) |
Given a range of curves, check whether there is at least one pair of curves that intersect in their interior. More... | |
OutputIterator CGAL::compute_intersection_points | ( | InputIterator | curves_begin, |
InputIterator | curves_end, | ||
OutputIterator | points, | ||
bool | report_endpoints = false |
||
) |
#include <CGAL/Surface_sweep_2_algorithms.h>
Given a range of curves, compute all intersection points between two (or more) input curves.
When the flag report_endpoints
is true
, this function reports all the curve endpoints as well. If a curve endpoint is also an intersection point, it is reported once (regardless of the value of the report_endpoints
flag). The value-type of InputIterator
is a curve type and the value-type of OutputIterator
is a point type. The output points are reported in an increasing \(xy\)-lexicographical order.
OutputIterator CGAL::compute_intersection_points | ( | InputIterator | curves_begin, |
InputIterator | curves_end, | ||
OutputIterator | points, | ||
bool | report_endpoints = false , |
||
Traits | traits | ||
) |
#include <CGAL/Surface_sweep_2_algorithms.h>
Given a range of curves, compute all intersection points between two (or more) input curves.
When the flag report_endpoints
is true
, this function reports all the curve endpoints as well. If a curve endpoint is also an intersection point, it is reported once (regardless of the value of the report_endpoints
flag). The Traits
type must be a model of the ArrangementTraits_2
concept, such that the value-type of InputIterator
is Traits::Curve_2
, and the value-type of OutputIterator
is Traits::Point_2
. The output points are reported in an increasing \( xy\)-lexicographical order.
OutputIterator CGAL::compute_subcurves | ( | InputIterator | curves_begin, |
InputIterator | curves_end, | ||
OutputIterator | subcurves, | ||
bool | multiple_overlaps = false |
||
) |
#include <CGAL/Surface_sweep_2_algorithms.h>
Given a range of curves, compute all \( x\)-monotone subcurves that are pairwise disjoint in their interior, as induced by the input curves.
If the flag multiple_overlaps
is true
, then a subcurve that represents an overlap of \( k\) input curves is reported \( k\) times; otherwise, each subcurve is reported only once. The value-type of InputIterator
is a curve type, and the value-type of OutputIterator
is an \(x\)-monotone curve type.
OutputIterator CGAL::compute_subcurves | ( | InputIterator | curves_begin, |
InputIterator | curves_end, | ||
OutputIterator | subcurves, | ||
bool | multiple_overlaps = false , |
||
Traits | traits = Default_traits() |
||
) |
#include <CGAL/Surface_sweep_2_algorithms.h>
Given a range of curves, compute all \( x\)-monotone subcurves that are pairwise disjoint in their interior, as induced by the input curves.
If the flag multiple_overlaps
is true
, then a subcurve that represents an overlap of \( k\) input curves is reported \( k\) times; otherwise, each subcurve is reported only once. The Traits
type must be a model of the ArrangementTraits_2
concept, such that the value-type of InputIterator
is Traits::Curve_2
, and the value-type of OutputIterator
is Traits::X_monotone_curve_2
.
bool CGAL::do_curves_intersect | ( | InputIterator | curves_begin, |
InputIterator | curves_end | ||
) |
#include <CGAL/Surface_sweep_2_algorithms.h>
Given a range of curves, check whether there is at least one pair of curves that intersect in their interior.
The function returns true
if such a pair is found, and false
if all curves are pairwise disjoint in their interior. The value-type of InputIterator
is a curve type.
bool CGAL::do_curves_intersect | ( | InputIterator | curves_begin, |
InputIterator | curves_end, | ||
Traits | traits = Default_traits() |
||
) |
#include <CGAL/Surface_sweep_2_algorithms.h>
Given a range of curves, check whether there is at least one pair of curves that intersect in their interior.
The function returns true
if such a pair is found, and false
if all curves are pairwise disjoint in their interior. The Traits
type must be a model of the ArrangementTraits_2
concept, such that the value-type of InputIterator
is Traits::Curve_2
.