CGAL 6.2 - Polygon Mesh Processing

Loading...
Searching...
No Matches
Classes | Functions
Intersection Functions
Reference Manual

##

Functions to test if there are self intersections, and to report faces that do intersect.

## Classes
class | CGAL::Rigid_triangle_mesh_collision_detection< TriangleMesh, VertexPointMap, Kernel, AABBTree, Has_rotation >
| This class provides methods to perform some intersection tests between triangle meshes that undergo affine transformations (rotation, translation, and scaling). More...

## Functions
template<class PolylineRange >
bool | CGAL::Polygon_mesh_processing::do_intersect (const PolylineRange &polylines1, const PolylineRange &polylines2)
| returns `true` if there exists a segment of a polyline of `polylines1` and a segment of a polyline of `polylines2` which intersect, and `false` otherwise.
template<class Polyline >
bool | CGAL::Polygon_mesh_processing::do_intersect (const Polyline &polyline1, const Polyline &polyline2)
| returns `true` if there exists a segment of `polyline1` and a segment of `polyline2` which intersect, and `false` otherwise.
template<class TriangleMesh , class NamedParameters1 = CGAL::parameters::Default_named_parameter, class NamedParameters2 = CGAL::parameters::Default_named_parameter>
bool | CGAL::Polygon_mesh_processing::do_intersect (const TriangleMesh &tm1, const TriangleMesh &tm2, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
| returns `true` if there exists a face of `tm1` and a face of `tm2` which intersect, and `false` otherwise.
template<class TriangleMesh , class PolylineRange , class NamedParameters = parameters::Default_named_parameters>
bool | CGAL::Polygon_mesh_processing::do_intersect (const TriangleMesh &tm, const PolylineRange &polylines, const NamedParameters &np=parameters::default_values())
| returns `true` if there exists a face of `tm` and a segment of a polyline of `polylines` which intersect, and `false` otherwise.
template<class TriangleMesh , class Polyline , class NamedParameters = CGAL::parameters::Default_named_parameters>
bool | CGAL::Polygon_mesh_processing::do_intersect (const TriangleMesh &tm, const Polyline &polyline, const NamedParameters &np=parameters::default_values())
| returns `true` if there exists a face of `tm` and a segment of `polyline` which intersect, and `false` otherwise.
template<class TriangleMeshRange , class OutputIterator , class NamedParameters , class NamedParametersRange >
OutputIterator | CGAL::Polygon_mesh_processing::intersecting_meshes (const TriangleMeshRange &range, OutputIterator out, const NamedParameters &np, const NamedParametersRange &nps)
| detects and reports all the pairs of meshes intersecting in a range of triangulated surface meshes.
template<class ConcurrencyTag = Sequential_tag, class TriangleMesh , class FaceRange , class FacePairOutputIterator , class NamedParameters = parameters::Default_named_parameters>
FacePairOutputIterator | CGAL::Polygon_mesh_processing::self_intersections (const FaceRange &face_range, const TriangleMesh &tmesh, FacePairOutputIterator out, const NamedParameters &np=parameters::default_values())
| collects intersections between a subset of faces of a triangulated surface mesh.
template<class ConcurrencyTag = Sequential_tag, class TriangleMesh , class FacePairOutputIterator , class NamedParameters = CGAL::parameters::Default_named_parameters>
FacePairOutputIterator | CGAL::Polygon_mesh_processing::self_intersections (const TriangleMesh &tmesh, FacePairOutputIterator out, const NamedParameters &np=parameters::default_values())
| collects intersections between all the faces of a triangulated surface mesh.
template<class ConcurrencyTag = Sequential_tag, class FaceRange , class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>
bool | CGAL::Polygon_mesh_processing::does_self_intersect (const FaceRange &face_range, const TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
| tests if a set of faces of a triangulated surface mesh self-intersects.
template<class ConcurrencyTag = Sequential_tag, class TriangleMesh , class NamedParameters = CGAL::parameters::Default_named_parameters>
bool | CGAL::Polygon_mesh_processing::does_self_intersect (const TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())
| tests if a triangulated surface mesh self-intersects.
template<class ConcurrencyTag = Sequential_tag, class PointRange , class TriangleRange , class TriangleIdPairOutputIterator , class NamedParameters = CGAL::parameters::Default_named_parameters>
TriangleIdPairOutputIterator | CGAL::Polygon_mesh_processing::triangle_soup_self_intersections (const PointRange &points, const TriangleRange &triangles, TriangleIdPairOutputIterator out, const NamedParameters &np=parameters::default_values())
| collects intersections between all the triangles in a triangle soup.
template<class ConcurrencyTag = Sequential_tag, class PointRange , class TriangleRange , class NamedParameters = CGAL::parameters::Default_named_parameters>
bool | CGAL::Polygon_mesh_processing::does_triangle_soup_self_intersect (const PointRange &points, const TriangleRange &triangles, const NamedParameters &np=parameters::default_values())
| tests if a triangle soup self-intersects.

## Function Documentation

## ◆ do_intersect() [1/5]

template<class Polyline >

bool CGAL::Polygon_mesh_processing::do_intersect | ( | const Polyline & | polyline1,
|  | const Polyline & | polyline2
| ) |  |

`#include <CGAL/Polygon_mesh_processing/intersection.h>`

returns `true` if there exists a segment of `polyline1` and a segment of `polyline2` which intersect, and `false` otherwise.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Template Parameters

  Polyline | a `RandomAccessRange` of points. The point type must be from a 3D point type from CGAL Kernel. A polyline is defined as a sequence of points, each pair of contiguous points defines a segment of the polyline. If the first and last points of the polyline are identical, the polyline is closed.

Parameters

  polyline1 | the first polyline to check for intersections.
  polyline2 | the second polyline to check for intersections.

## ◆ do_intersect() [2/5]

template<class PolylineRange >

bool CGAL::Polygon_mesh_processing::do_intersect | ( | const PolylineRange & | polylines1,
|  | const PolylineRange & | polylines2
| ) |  |

`#include <CGAL/Polygon_mesh_processing/intersection.h>`

returns `true` if there exists a segment of a polyline of `polylines1` and a segment of a polyline of `polylines2` which intersect, and `false` otherwise.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Template Parameters

  PolylineRange | a `RandomAccessRange` of `RandomAccessRange` of points. The point type must be from a 3D point from a CGAL Kernel. A polyline is defined as a sequence of points, each pair of contiguous points defines a segment of the polyline. If the first and last points of the polyline are identical, the polyline is closed.

Parameters

  polylines1 | the first range of polylines to check for intersections.
  polylines2 | the second range of polylines to check for intersections.

## ◆ do_intersect() [3/5]

template<class TriangleMesh , class Polyline , class NamedParameters = CGAL::parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::do_intersect | ( | const TriangleMesh & | tm,
|  | const Polyline & | polyline,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/intersection.h>`

returns `true` if there exists a face of `tm` and a segment of `polyline` which intersect, and `false` otherwise.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Precondition
  `CGAL::is_triangle_mesh(tm)`

Template Parameters

  TriangleMesh | a model of `FaceListGraph`
  Polyline | a `RandomAccessRange` of points. The point type of the range must be the same as the value type of the vertex point map. A polyline is defined as a sequence of points, each pair of contiguous points defines a segment of the polyline. If the first and last points of the polyline are identical, the polyline is closed.
  NamedParameters | a sequence of Named Parameters

Parameters

  tm | the triangulated surface mesh to check for intersections
  polyline | the polyline to check for intersections.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tm` Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tm)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tm`. |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the vertex point type. |

## ◆ do_intersect() [4/5]

template<class TriangleMesh , class PolylineRange , class NamedParameters = parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::do_intersect | ( | const TriangleMesh & | tm,
|  | const PolylineRange & | polylines,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/intersection.h>`

returns `true` if there exists a face of `tm` and a segment of a polyline of `polylines` which intersect, and `false` otherwise.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Precondition
  `CGAL::is_triangle_mesh(tm)`

Template Parameters

  TriangleMesh | a model of `FaceListGraph`
  PolylineRange | a `RandomAccessRange` of `RandomAccessRange` of points. The point type of the range must be the same as the value type of the vertex point map. A polyline is defined as a sequence of points, each pair of contiguous points defines a segment of the polyline. If the first and last points of the polyline are identical, the polyline is closed.
  NamedParameters | a sequence of Named Parameters

Parameters

  tm | the triangulated surface mesh to check for intersections
  polylines | the range of polylines to check for intersections.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tm` Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tm)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tm`. |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the vertex point type. |

## ◆ do_intersect() [5/5]

template<class TriangleMesh , class NamedParameters1 = CGAL::parameters::Default_named_parameter, class NamedParameters2 = CGAL::parameters::Default_named_parameter>

bool CGAL::Polygon_mesh_processing::do_intersect | ( | const TriangleMesh & | tm1,
|  | const TriangleMesh & | tm2,
|  | const NamedParameters1 & | np1 = `parameters::default_values()`,
|  | const NamedParameters2 & | np2 = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/intersection.h>`

returns `true` if there exists a face of `tm1` and a face of `tm2` which intersect, and `false` otherwise.

If `do_overlap_test_of_bounded_sides` is set to `true`, the overlap of bounded sides are tested as well. In that case, the meshes must be closed.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Precondition
  `CGAL::is_triangle_mesh(tm1)`
  `CGAL::is_triangle_mesh(tm2)`
  `!do_overlap_test_of_bounded_sides` || `CGAL::is_closed(tm1)`
  `!do_overlap_test_of_bounded_sides` || `CGAL::is_closed(tm2)`

Template Parameters

  TriangleMesh | a model of `FaceListGraph`
  NamedParameters1 | a sequence of Named Parameters for `tm1`
  NamedParameters2 | a sequence of Named Parameters for `tm2`

Parameters

  tm1 | the first triangulated surface mesh to check for intersections
  tm2 | the second triangulated surface mesh to check for intersections
  np1 | an optional sequence of Named Parameters among the ones listed below
  np2 | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tm1` (`tm2`) Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tm1 (tm2))` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tm1` (`tm2`) Extra: Both vertex point maps must have the same value type |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the vertex point type. Extra: np1 only |
  If `true`, also tests the overlap of the bounded sides of `tm1` and `tm2`. If `false`, only the intersection of surface triangles is tested. Type: Boolean Default: `false` |

See also
  `intersecting_meshes()`

## ◆ does_self_intersect() [1/2]

template<class ConcurrencyTag = Sequential_tag, class FaceRange , class TriangleMesh , class NamedParameters = parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::does_self_intersect | ( | const FaceRange & | face_range,
|  | const TriangleMesh & | tmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

tests if a set of faces of a triangulated surface mesh self-intersects.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Precondition
  `CGAL::is_triangle_mesh(tm)`

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
  FaceRange | a range of `face_descriptor`
  TriangleMesh | a model of `FaceListGraph`
  NamedParameters | a sequence of Named Parameters

Parameters

  face_range | the set of faces to test for self-intersection
  tmesh | the triangulated surface mesh to be tested
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tmesh` Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tmesh)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tmesh`. |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the vertex point type. |

Returns
  `true` if the faces in `face_range` self-intersect

See also
  `self_intersections()`

## ◆ does_self_intersect() [2/2]

template<class ConcurrencyTag = Sequential_tag, class TriangleMesh , class NamedParameters = CGAL::parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::does_self_intersect | ( | const TriangleMesh & | tmesh,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

tests if a triangulated surface mesh self-intersects.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Precondition
  `CGAL::is_triangle_mesh(tmesh)`

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
  TriangleMesh | a model of `FaceListGraph`
  NamedParameters | a sequence of Named Parameters

Parameters

  tmesh | the triangulated surface mesh to be tested
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tmesh` Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tmesh)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tmesh`. |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the vertex point type. |

Returns
  `true` if `tmesh` self-intersects

See also
  `self_intersections()`

## ◆ does_triangle_soup_self_intersect()

template<class ConcurrencyTag = Sequential_tag, class PointRange , class TriangleRange , class NamedParameters = CGAL::parameters::Default_named_parameters>

bool CGAL::Polygon_mesh_processing::does_triangle_soup_self_intersect | ( | const PointRange & | points,
|  | const TriangleRange & | triangles,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

tests if a triangle soup self-intersects.

A triangle soup self-intersects if at least two triangles of the soup intersect. Two triangles of the soup are said to intersect if the corresponding geometric triangles intersect and the intersection is neither an edge nor a vertex of both triangles (with the same point ids, ignoring the orientation for an edge).

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
  PointRange | a model of the concept `RandomAccessContainer` whose value type is the point type
  TriangleRange | a model of the concept `RandomAccessContainer` whose value type is a model of the concept `RandomAccessContainer` whose value type is `std::size_t`
  NamedParameters | a sequence of Named Parameters

Parameters

  points | points of the soup of triangles
  triangles | each element in the range describes a triangle using the indices of the points in `points`
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the elements of the range `points` Type: a model of `ReadablePropertyMap` whose value type is a point type from a CGAL `Kernel`. Default: `CGAL::Identity_property_map` |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the point type of the point map. |

Returns
  `true` if the triangle soup self-intersects, and `false` otherwise.

See also
  `triangle_soup_self_intersections()`
  `self_intersections()`
  `does_self_intersect()`

## ◆ intersecting_meshes()

template<class TriangleMeshRange , class OutputIterator , class NamedParameters , class NamedParametersRange >

OutputIterator CGAL::Polygon_mesh_processing::intersecting_meshes | ( | const TriangleMeshRange & | range,
|  | OutputIterator | out,
|  | const NamedParameters & | np,
|  | const NamedParametersRange & | nps
| ) |  |

`#include <CGAL/Polygon_mesh_processing/intersection.h>`

detects and reports all the pairs of meshes intersecting in a range of triangulated surface meshes.

A pair of meshes intersecting is put in the output iterator `out` as a `std::pair<std::size_t, std::size_t>`, each index referring to the index of the triangle mesh in the input range. If `do_overlap_test_of_bounded_sides` is `true`, the overlap of bounded sides are tested as well. In that case, the meshes must be closed.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Template Parameters

  TriangleMeshRange | a model of `RandomAccessRange` of triangulated surface meshes model of `FaceListGraph`.
  OutputIterator | an output iterator in which `std::pair<std::size_t, std::size_t>` can be put.
  NamedParameters | a sequence of Named Parameters for the algorithm
  NamedParametersRange | a range of Named Parameters for the meshes.

Parameters

  range | the range of triangulated surface meshes to be checked for intersections.
  out | output iterator used to collect pairs of intersecting meshes.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits`, where `Point` is the value type of the vertex point map of the meshes |
  If `true`, reports also overlap of bounded sides of meshes. If `false`, only the intersection of surface triangles are tested. Type: Boolean Default: `false` |

Parameters

  nps | an optional range of sequences of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of a mesh `tm` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tm)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tm`. Extra: All vertex point maps must have the same value type |

See also
  `do_intersect()`

## ◆ self_intersections() [1/2]

template<class ConcurrencyTag = Sequential_tag, class TriangleMesh , class FaceRange , class FacePairOutputIterator , class NamedParameters = parameters::Default_named_parameters>

FacePairOutputIterator CGAL::Polygon_mesh_processing::self_intersections | ( | const FaceRange & | face_range,
|  | const TriangleMesh & | tmesh,
|  | FacePairOutputIterator | out,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

collects intersections between a subset of faces of a triangulated surface mesh.

Two faces are said to intersect if the corresponding triangles intersect and the intersection is neither an edge nor a vertex incident to both faces.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Precondition
  `CGAL::is_triangle_mesh(tmesh)`

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
  FaceRange | a model of `ConstRange` with value type `boost::graph_traits<TriangleMesh>::face_descriptor`.
  TriangleMesh | a model of `FaceListGraph`
  FacePairOutputIterator | a model of `OutputIterator` holding objects of type `std::pair<boost::graph_traits<TriangleMesh>::face_descriptor, boost::graph_traits<TriangleMesh>::face_descriptor>`. It does not need to be thread-safe.
  NamedParameters | a sequence of Named Parameters

Parameters

  face_range | the range of faces to check for self-intersection.
  tmesh | the triangulated surface mesh to be checked
  out | output iterator to be filled with all pairs of non-adjacent faces that intersect
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tmesh` Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tmesh)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tmesh`. |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the vertex point type. |
  the maximum number of self intersections that will be detected and returned by the function. Type: unsigned int Default: No limit. Extra: In parallel mode, the number of returned self-intersections is at least `maximum_number` (and not exactly that number) as no strong synchronization is put on threads for performance reasons. |

Returns
  `out`

See also
  `does_self_intersect()`

## ◆ self_intersections() [2/2]

template<class ConcurrencyTag = Sequential_tag, class TriangleMesh , class FacePairOutputIterator , class NamedParameters = CGAL::parameters::Default_named_parameters>

FacePairOutputIterator CGAL::Polygon_mesh_processing::self_intersections | ( | const TriangleMesh & | tmesh,
|  | FacePairOutputIterator | out,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

collects intersections between all the faces of a triangulated surface mesh.

Two faces are said to intersect if the corresponding triangles intersect and the intersection is neither an edge nor a vertex incident to both faces.

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Precondition
  `CGAL::is_triangle_mesh(tmesh)`

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
  TriangleMesh | a model of `FaceListGraph`
  FacePairOutputIterator | a model of `OutputIterator` holding objects of type `std::pair<boost::graph_traits<TriangleMesh>::face_descriptor, boost::graph_traits<TriangleMesh>::face_descriptor>`. It does not need to be thread-safe.
  NamedParameters | a sequence of Named Parameters

Parameters

  tmesh | the triangulated surface mesh to be checked
  out | output iterator to be filled with all pairs of non-adjacent faces that intersect. In case `tmesh` contains some degenerate faces, for each degenerate face `f` a pair `(f,f)` will be put in `out` before any other self intersection between non-degenerate faces. Note that these are the only pairs where degenerate faces will be reported.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating points to the vertices of `tmesh` Type: a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::vertex_descriptor` as key type and `Point_3` as value type Default: `boost::get(CGAL::vertex_point, tmesh)` Extra: If this parameter is omitted, an internal property map for `CGAL::vertex_point_t` should be available for the vertices of `tmesh`. |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the vertex point type. |
  the maximum number of self intersections that will be detected and returned by the function. Type: unsigned int Default: No limit. Extra: In parallel mode, the number of returned self-intersections is at least `maximum_number` (and not exactly that number) as no strong synchronization is put on threads for performance reasons. |

Returns
  `out`

See also
  `does_self_intersect()`

## ◆ triangle_soup_self_intersections()

template<class ConcurrencyTag = Sequential_tag, class PointRange , class TriangleRange , class TriangleIdPairOutputIterator , class NamedParameters = CGAL::parameters::Default_named_parameters>

TriangleIdPairOutputIterator CGAL::Polygon_mesh_processing::triangle_soup_self_intersections | ( | const PointRange & | points,
|  | const TriangleRange & | triangles,
|  | TriangleIdPairOutputIterator | out,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/self_intersections.h>`

collects intersections between all the triangles in a triangle soup.

Two triangles of the soup are said to intersect if the corresponding geometric triangles intersect and the intersection is neither an edge nor a vertex of both triangles (with the same point ids, ignoring the orientation for an edge).

This function depends on the package Intersecting Sequences of dD Iso-oriented Boxes.

Template Parameters

  ConcurrencyTag | enables sequential versus parallel algorithm. Possible values are `Sequential_tag`, `Parallel_tag`, and `Parallel_if_available_tag`.
  PointRange | a model of the concept `RandomAccessContainer` whose value type is the point type
  TriangleRange | a model of the concept `RandomAccessContainer` whose value type is a model of the concept `RandomAccessContainer` whose value type is `std::size_t`
  TriangleIdPairOutputIterator | a model of `OutputIterator` holding objects of type `std::pair<std::size_t,std::size_t>`
  NamedParameters | a sequence of Named Parameters

Parameters

  points | points of the soup of triangles
  triangles | each element in the range describes a triangle using the indices of the points in `points`
  out | output iterator to be filled with all pairs of ids of triangles intersecting (the id of a triangle is its position in `triangles`). In case the triangle soup contains some degenerate triangles, for each degenerate triangle `t` with id `i` a pair `(i,i)` will be put in `out` before any other self intersection between non-degenerate triangles. Note that these are the only pairs where degenerate triangles will be reported.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  the maximum number of self intersections that will be detected and returned by the function. Type: unsigned int Default: No limit. Extra: In parallel mode, the number of returned self-intersections is at least `maximum_number` (and not exactly that number) as no strong synchronization is put on threads for performance reasons. |
  a property map associating points to the elements of the range `points` Type: a model of `ReadablePropertyMap` whose value type is a point type from a CGAL `Kernel`. Default: `CGAL::Identity_property_map` |
  an instance of a geometric traits class Type: a class model of `PMPSelfIntersectionTraits` Default: a CGAL Kernel deduced from the point type, using `CGAL::Kernel_traits` Extra: The geometric traits class must be compatible with the point type of the point map. |

Returns
  `out`

See also
  `does_triangle_soup_self_intersect()`
  `self_intersections()`
  `does_self_intersect()`