CGAL 6.2 - 2D Intersection of Curves

Loading...
Searching...
No Matches
Functions
Reference Manual

##

Baruch Zukerman, Ron Wein, and Efi Fogel
This package provides three free functions implemented based on the sweep-line paradigm: given a collection of input curves, compute all intersection points, compute the set of subcurves that are pairwise interior-disjoint induced by them, and check whether there is at least one pair of curves among them that intersect in their interior.
Introduced in: CGAL 2.4
Depends on: 2D Arrangements
BibTeX: cgal:wfz-ic2-26a
License: GPL

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

- `CGAL::compute_intersection_points`
- `CGAL::compute_subcurves`
- `CGAL::do_intersect`

## 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]

template<typename InputIterator , typename OutputIterator >

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]

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

`#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]

template<typename InputIterator , typename OutputIterator >

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]

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()`
| ) |  |

`#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]

template<typename InputIterator >

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]

template<typename InputIterator , typename Traits >

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]

template<typename InputIterator >

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]

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()`
| ) |  |

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