CGAL 5.5.1 - Polygon Mesh Processing
Intersection Functions

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

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

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. More...

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. More...

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. More...

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. More...

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. More...

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. More...

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. More...

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. More...

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. More...

## ◆ do_intersect() [1/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() [2/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() [3/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::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
intersecting_meshes()

## ◆ 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::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 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::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.

## ◆ 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(tmesh)
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::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
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::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
self_intersections()

## ◆ 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 refering 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 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::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
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 not 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::face_descriptor. TriangleMesh a model of FaceListGraph FacePairOutputIterator a model of OutputIterator holding objects of type std::pair::face_descriptor, boost::graph_traits::face_descriptor> 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::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
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 not 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::face_descriptor, boost::graph_traits::face_descriptor> 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. 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::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
does_self_intersect()