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. By default the curves are considered closed.
The first two operations are performed in an output-sensitive manner.
Classified Reference Pages
Functions
Functions | |
| template<typename InputIterator, typename 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. | |
| template<typename InputIterator, typename 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. | |
| template<typename InputIterator, typename 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. | |
| template<typename InputIterator, typename OutputIterator, typename 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. | |
| template<typename InputIterator> | |
| bool | CGAL::do_curves_intersect (InputIterator curves_begin, InputIterator curves_end) |
| template<typename InputIterator, typename Traits> | |
| bool | CGAL::do_curves_intersect (InputIterator curves_begin, InputIterator curves_end, Traits traits=Default_traits()) |
| template<typename InputIterator> | |
| bool | CGAL::Surface_sweep_2::do_intersect (InputIterator curves_begin, InputIterator curves_end, bool consider_common_endpoints=true) |
| Given a range of curves, check whether there is at least one pair of curves that intersect. | |
| template<typename InputIterator, typename Traits> | |
| bool | CGAL::Surface_sweep_2::do_intersect (InputIterator curves_begin, InputIterator curves_end, bool consider_common_endpoints=true, Traits traits=Default_traits()) |
| Given a range of curves, check whether there is at least one pair of curves that intersect. | |
Function Documentation
◆ compute_intersection_points() [1/2]
| 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.
- Examples
- Surface_sweep_2/plane_sweep.cpp.
◆ compute_intersection_points() [2/2]
| 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 AosTraits_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.
◆ compute_subcurves() [1/2]
| 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.
- Examples
- Surface_sweep_2/plane_sweep.cpp.
◆ compute_subcurves() [2/2]
| 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 AosTraits_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.
◆ do_curves_intersect() [1/2]
| bool CGAL::do_curves_intersect | ( | InputIterator | curves_begin, |
| InputIterator | curves_end ) |
#include <CGAL/Surface_sweep_2_algorithms.h>
- Deprecated
- Call Surface_sweep_2::do_intersect(curves_begin, curves_end, false) instead
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.
The call CGAL::do_curves_intersect(begin, end, traits) should be replaced by the call CGAL::Surface_sweep_2::do_intersect(begin, end, false, traits)
◆ do_curves_intersect() [2/2]
| bool CGAL::do_curves_intersect | ( | InputIterator | curves_begin, |
| InputIterator | curves_end, | ||
| Traits | traits = Default_traits() ) |
#include <CGAL/Surface_sweep_2_algorithms.h>
- Deprecated
- Call Surface_sweep_2::do_intersect(curves_begin, curves_end, false, traits) instead
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 AosTraits_2 concept, such that the value-type of InputIterator is Traits::Curve_2.
The call CGAL::do_curves_intersect(begin, end) should be replaced by the call CGAL::Surface_sweep_2::do_intersect(begin, end, false)
◆ do_intersect() [1/2]
| bool CGAL::Surface_sweep_2::do_intersect | ( | InputIterator | curves_begin, |
| InputIterator | curves_end, | ||
| bool | consider_common_endpoints = true ) |
#include <CGAL/Surface_sweep_2_algorithms.h>
Given a range of curves, check whether there is at least one pair of curves that intersect.
The value-type of InputIterator is a curve type. If consider_common_endpoints is true, common endpoints are considered. Otherwise, common endpoints are not counted as intersections.
- Examples
- Surface_sweep_2/plane_sweep.cpp.
◆ do_intersect() [2/2]
| bool CGAL::Surface_sweep_2::do_intersect | ( | InputIterator | curves_begin, |
| InputIterator | curves_end, | ||
| bool | consider_common_endpoints = true, | ||
| 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.
The value-type of InputIterator is a curve type. If consider_common_endpoints is true, common endpoints are considered. Otherwise, common endpoints are not counted as intersections. The Traits type must be a model of the AosTraits_2 concept, such that the value-type of InputIterator is either Traits::Curve_2 or Traits::X_monotone_curve_2.
