\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.10.1 - Polygon Mesh Processing
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Public Types | Public Member Functions
CGAL::Side_of_triangle_mesh< TriangleMesh, GeomTraits, VertexPointMap > Class Template Reference
Polygon Mesh Processing Reference

#include <CGAL/Side_of_triangle_mesh.h>

Definition

template<class TriangleMesh, class GeomTraits, class VertexPointMap = Default>
class CGAL::Side_of_triangle_mesh< TriangleMesh, GeomTraits, VertexPointMap >

This class provides an efficient point location functionality with respect to a domain bounded by one or several disjoint closed triangle meshes.

A point is said to be on the bounded side of the domain if an odd number of surfaces is crossed when walking from the point to infinity.

The input triangle mesh is expected to contain no self-intersections and to be free from self-inclusions.

In case the triangle mesh has several connected components, the same test is performed and returns correct results. In case of self-inclusions, the user should be aware that the predicate called inside every other sub-volume bounded by a nested surface will return in turns CGAL::ON_BOUNDED_SIDE and CGAL::ON_UNBOUNDED_SIDE, following the aforementioned parity criterion.

This class depends on the package 3D Fast Intersection and Distance Computation.

Template Parameters
TriangleMesha triangulated surface mesh, model of FaceListGraph
GeomTraitsa geometric traits class, model of Kernel
VertexPointMapa model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and GeomTraits::Point_3 as value type. The default is typename boost::property_map<TriangleMesh,vertex_point_t>::type.

Implementation Details
The current implementation is based on the number of triangles intersected by a ray having the query point as source. The do-intersect predicate used to detect if a triangle is intersected is able to detect if a triangle is intersected in its interior or on its boundary. In case it is intersected on its boundary, another ray is picked. In order to speed queries, the first ray used is an axis aligned one that depends on the extents of the bbox of the input mesh. In case other rays are needed to conclude, the rays are generated from a random uniform sampling of a sphere.

Examples:
Polygon_mesh_processing/point_inside_example.cpp.

Public Types

typedef unspecified_type AABB_tree
 AABB-tree accepting faces of TriangleMesh
 

Public Member Functions

 Side_of_triangle_mesh (const TriangleMesh &tmesh, VertexPointMap vpmap, const GeomTraits &gt=GeomTraits())
 Constructor with one triangulated surface mesh. More...
 
 Side_of_triangle_mesh (const TriangleMesh &tmesh, const GeomTraits &gt=GeomTraits())
 Constructor with one surface triangle mesh, using get(boost::vertex_point, tmesh) as vertex point property map. More...
 
 Side_of_triangle_mesh (const AABB_tree &tree, const GeomTraits &gt=GeomTraits())
 Constructor that takes a pre-built CGAL AABB_tree of the triangulated surface mesh primitives. More...
 
Bounded_side operator() (const Point &point) const
 returns the location of a query point More...
 

Constructor & Destructor Documentation

template<class TriangleMesh, class GeomTraits, class VertexPointMap = Default>
CGAL::Side_of_triangle_mesh< TriangleMesh, GeomTraits, VertexPointMap >::Side_of_triangle_mesh ( const TriangleMesh &  tmesh,
VertexPointMap  vpmap,
const GeomTraits &  gt = GeomTraits() 
)

Constructor with one triangulated surface mesh.

Parameters
tmeshthe triangulated surface mesh bounding the domain to be tested
vpmapthe property map with the points associated to the vertices of tmesh
gtan instance of the geometric traits class
Precondition
CGAL::is_closed(tmesh) && CGAL::is_triangle_mesh(tmesh)
template<class TriangleMesh, class GeomTraits, class VertexPointMap = Default>
CGAL::Side_of_triangle_mesh< TriangleMesh, GeomTraits, VertexPointMap >::Side_of_triangle_mesh ( const TriangleMesh &  tmesh,
const GeomTraits &  gt = GeomTraits() 
)

Constructor with one surface triangle mesh, using get(boost::vertex_point, tmesh) as vertex point property map.

Parameters
tmeshthe triangulated surface mesh bounding the domain to be tested
gtan instance of the geometric traits class
Precondition
CGAL::is_closed(tmesh) && CGAL::is_triangle_mesh(tmesh)
template<class TriangleMesh, class GeomTraits, class VertexPointMap = Default>
CGAL::Side_of_triangle_mesh< TriangleMesh, GeomTraits, VertexPointMap >::Side_of_triangle_mesh ( const AABB_tree &  tree,
const GeomTraits &  gt = GeomTraits() 
)

Constructor that takes a pre-built CGAL AABB_tree of the triangulated surface mesh primitives.

Parameters
treea CGAL AABB_tree with AABB_face_graph_triangle_primitive as Primitive type
gtan instance of the geometric traits class
Precondition
CGAL::is_closed(tmesh) && CGAL::is_triangle_mesh(tmesh)

Member Function Documentation

template<class TriangleMesh, class GeomTraits, class VertexPointMap = Default>
Bounded_side CGAL::Side_of_triangle_mesh< TriangleMesh, GeomTraits, VertexPointMap >::operator() ( const Point &  point) const

returns the location of a query point

Parameters
pointthe query point to be located with respect to the input polyhedral surface
Returns