CGAL 5.3 - Polygon Mesh Processing
Intersection Detection Functions

Functions to detect intersections.

Note that those functions will be exact as long as the underlying do-intersect predicates used are exact. In practice, it means that the 3D point type used must come from a CGAL kernel with exact predicates.

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 , class NamedParameters2 >
bool CGAL::Polygon_mesh_processing::do_intersect (const TriangleMesh &tm1, const TriangleMesh &tm2, const NamedParameters1 &np1, const NamedParameters2 &np2)
 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 >
bool CGAL::Polygon_mesh_processing::do_intersect (const TriangleMesh &tm, const PolylineRange &polylines, const NamedParameters &np)
 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 >
bool CGAL::Polygon_mesh_processing::do_intersect (const TriangleMesh &tm, const Polyline &polyline, const NamedParameters &np)
 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...
 

Function Documentation

◆ 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
PolylineRangea 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
polylines1the first range of polylines to check for intersections.
polylines2the 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
Polylinea 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
polyline1the first polyline to check for intersections.
polyline2the second polyline to check for intersections.

◆ do_intersect() [3/5]

template<class TriangleMesh , class NamedParameters1 , class NamedParameters2 >
bool CGAL::Polygon_mesh_processing::do_intersect ( const TriangleMesh &  tm1,
const TriangleMesh &  tm2,
const NamedParameters1 &  np1,
const NamedParameters2 &  np2 
)

#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
TriangleMesha model of FaceListGraph
NamedParameters1a sequence of Named Parameters for tm1
NamedParameters2a sequence of Named Parameters for tm2
Parameters
tm1the first triangulated surface mesh to check for intersections
tm2the second triangulated surface mesh to check for intersections
np1an optional sequence of Named Parameters among the ones listed below
np2an 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

◆ do_intersect() [4/5]

template<class TriangleMesh , class PolylineRange , class NamedParameters >
bool CGAL::Polygon_mesh_processing::do_intersect ( const TriangleMesh &  tm,
const PolylineRange &  polylines,
const NamedParameters &  np 
)

#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
TriangleMesha model of FaceListGraph
PolylineRangea 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.
NamedParametersa sequence of Named Parameters
Parameters
tmthe triangulated surface mesh to check for intersections
polylinesthe range of polylines to check for intersections.
npan 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.

◆ do_intersect() [5/5]

template<class TriangleMesh , class Polyline , class NamedParameters >
bool CGAL::Polygon_mesh_processing::do_intersect ( const TriangleMesh &  tm,
const Polyline &  polyline,
const NamedParameters &  np 
)

#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
TriangleMesha model of FaceListGraph
Polylinea 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.
NamedParametersa sequence of Named Parameters
Parameters
tmthe triangulated surface mesh to check for intersections
polylinethe polyline to check for intersections.
npan 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.

◆ 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
TriangleMeshRangea model of RandomAccessRange of triangulated surface meshes model of FaceListGraph.
OutputIteratoran output iterator in which std::pair<std::size_t, std::size_t> can be put.
NamedParametersa sequence of Named Parameters for the algorithm
NamedParametersRangea range of Named Parameters for the meshes.
Parameters
rangethe range of triangulated surface meshes to be checked for intersections.
outoutput iterator used to collect pairs of intersecting meshes.
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters

  • 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
npsan 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