\( \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 5.0 - Polygon Mesh Processing

Functions to locate points on a mesh, and manipulate such locations.

Classes

class  CGAL::Polygon_mesh_processing::Location_traits< TriangleMesh, NamedParameters >
 Helper class whose sole purpose is to make it easier to access some useful types. More...
 

Functions

template<typename K , typename Point >
std::array< typename K::FT, 3 > CGAL::Polygon_mesh_processing::barycentric_coordinates (const Point &p, const Point &q, const Point &r, const Point &query, const K &k)
 Given a set of three points and a query point, computes the barycentric coordinates of the query point with respect to the first three points. More...
 
template<typename TriangleMesh >
Location_traits< TriangleMesh >::descriptor_variant CGAL::Polygon_mesh_processing::get_descriptor_from_location (const typename Location_traits< TriangleMesh >::Face_location &loc, const TriangleMesh &tm)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns a descriptor to the simplex of smallest dimension on which the point corresponding to the location lies. More...
 
template<typename TriangleMesh , typename NamedParameters >
Location_traits< TriangleMesh, NamedParameters >::Point CGAL::Polygon_mesh_processing::construct_point (const typename Location_traits< TriangleMesh >::Face_location &loc, const TriangleMesh &tm, const NamedParameters &np)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns the geometric position described by these coordinates, as a point. More...
 

Random Location Generation

template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::random_location_on_halfedge (typename boost::graph_traits< TriangleMesh >::halfedge_descriptor hd, const TriangleMesh &tm, CGAL::Random &rnd=get_default_random())
 Returns a random point over the halfedge hd, as a location. More...
 
template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::random_location_on_face (typename boost::graph_traits< TriangleMesh >::face_descriptor fd, const TriangleMesh &tm, CGAL::Random &rnd=get_default_random())
 Returns a random point over the face fd, as a location. More...
 
template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::random_location_on_mesh (const TriangleMesh &tm, CGAL::Random &rnd=get_default_random())
 Returns a random point over the mesh tm. More...
 

Location Predicates

template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_vertex (const typename Location_traits< TriangleMesh >::Face_location &loc, const typename boost::graph_traits< TriangleMesh >::vertex_descriptor vd, const TriangleMesh &tm)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the vertex vd or not. More...
 
template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_halfedge (const typename Location_traits< TriangleMesh >::Face_location &loc, const typename boost::graph_traits< TriangleMesh >::halfedge_descriptor hd, const TriangleMesh &tm)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the halfedge hd or not. More...
 
template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_in_face (const typename Location_traits< TriangleMesh >::Barycentric_coordinates &bar, const TriangleMesh &tm)
 Given a set of barycentric coordinates, returns whether those barycentric coordinates correspond to a point within the face (boundary included), that is, if all the barycentric coordinates are positive. More...
 
template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_in_face (const typename Location_traits< TriangleMesh >::Face_location &loc, const TriangleMesh &tm)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is in the face (boundary included) or not. More...
 
template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_face_border (const typename Location_traits< TriangleMesh >::Face_location &loc, const TriangleMesh &tm)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the boundary of the face or not. More...
 
template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_mesh_border (const typename Location_traits< TriangleMesh >::Face_location &loc, const TriangleMesh &tm)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the border of the mesh or not. More...
 

Point Location

template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_in_face (typename boost::graph_traits< TriangleMesh >::vertex_descriptor vd, const TriangleMesh &tm)
 Returns the location of the given vertex vd as a location, that is an ordered pair specifying a face incident to vd and the barycentric coordinates of the vertex vd in that face. More...
 
template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_in_face (const typename boost::graph_traits< TriangleMesh >::vertex_descriptor vd, const typename boost::graph_traits< TriangleMesh >::face_descriptor fd, const TriangleMesh &tm)
 Returns the location of a given vertex as a location in fd, that is an ordered pair composed of fd and of the barycentric coordinates of the vertex in fd. More...
 
template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_in_face (const typename boost::graph_traits< TriangleMesh >::halfedge_descriptor he, const typename Location_traits< TriangleMesh >::FT t, const TriangleMesh &tm)
 Given a point described by a halfedge he and a scalar t as p = (1 - t) * source(he, tm) + t * target(he, tm), returns this location along the given edge as a location, that is an ordered pair specifying a face containing the location and the barycentric coordinates of that location in that face. More...
 
template<typename TriangleMesh , typename NamedParameters >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_in_face (const typename Location_traits< TriangleMesh, NamedParameters >::Point &query, const typename boost::graph_traits< TriangleMesh >::face_descriptor fd, const TriangleMesh &tm, const NamedParameters &np)
 Given a point query and a face fd of a triangulated surface mesh, returns this location as a location, that is an ordered pair composed of fd and of the barycentric coordinates of query with respect to the vertices of fd. More...
 
template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_in_adjacent_face (const typename Location_traits< TriangleMesh >::Face_location &loc, const typename boost::graph_traits< TriangleMesh >::face_descriptor fd, const TriangleMesh &tm)
 Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, and a second face adjacent to the first, return the location of the point in the second face. More...
 

Nearest Face Location Queries

The following functions can be used to find the closest point on a triangle mesh, given either a point or a ray.

This closest point is computed using a CGAL::AABB_tree. Users intending to call location functions on more than a single point (or ray) should first compute an AABB tree to store it (otherwise, it will be recomputed every time). Note that since the AABB tree class is a 3D structure, it might be required to wrap your point property map to convert your point type to the 3D point type (i.e., your kernel's Point_3) if you are working with a 2D triangle structure.

template<typename TriangleMesh , typename Point3VPM , typename NamedParameters >
void CGAL::Polygon_mesh_processing::build_AABB_tree (const TriangleMesh &tm, AABB_tree< CGAL::AABB_traits< typename Location_traits< TriangleMesh, NamedParameters >::Geom_traits, CGAL::AABB_face_graph_triangle_primitive< TriangleMesh, Point3VPM > > > &outTree, const NamedParameters &np)
 creates an AABB tree suitable for use with locate_with_AABB_tree(). More...
 
template<typename TriangleMesh , typename Point3VPM , typename NamedParameters >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_with_AABB_tree (const typename Location_traits< TriangleMesh, NamedParameters >::Point &p, const AABB_tree< CGAL::AABB_traits< typename Location_traits< TriangleMesh, NamedParameters >::Geom_traits, CGAL::AABB_face_graph_triangle_primitive< TriangleMesh, Point3VPM > > > &tree, const TriangleMesh &tm, const NamedParameters &np)
 returns the face location nearest to the given point, as a location. More...
 
template<typename TriangleMesh , typename NamedParameters >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate (const typename Location_traits< TriangleMesh, NamedParameters >::Point &p, const TriangleMesh &tm, const NamedParameters &np)
 returns the nearest face location to the given point. More...
 
template<typename TriangleMesh , typename Point3VPM , typename NamedParameters >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_with_AABB_tree (const typename Location_traits< TriangleMesh, NamedParameters >::Ray &ray, const AABB_tree< CGAL::AABB_traits< typename Location_traits< TriangleMesh, NamedParameters >::Geom_traits, CGAL::AABB_face_graph_triangle_primitive< TriangleMesh, Point3VPM > > > &tree, const TriangleMesh &tm, const NamedParameters &np)
 Returns the face location along ray nearest to its source point. More...
 
template<typename TriangleMesh , typename NamedParameters >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate (const typename Location_traits< TriangleMesh, NamedParameters >::Ray &ray, const TriangleMesh &tm, const NamedParameters &np)
 Returns the face location along ray nearest to its source point. More...
 

Function Documentation

◆ barycentric_coordinates()

template<typename K , typename Point >
std::array<typename K::FT, 3> CGAL::Polygon_mesh_processing::barycentric_coordinates ( const Point &  p,
const Point &  q,
const Point &  r,
const Point &  query,
const K &  k 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a set of three points and a query point, computes the barycentric coordinates of the query point with respect to the first three points.

Template Parameters
Pointthe type of a geometric 2D or 3D point
Kthe type of a geometric traits. Must be a model of Kernel.
Parameters
p,q,rthree points with respect to whom the barycentric coordinates of query will be computed
querythe query point whose barycentric coordinates will be computed
kan instance of the geometric traits
Precondition
p, q, and r are not collinear.
It must be possible to extract a kernel type model of Kernel, using CGAL::Kernel_traits<P> (this is the case for all standard CGAL point types and classes inheriting such point types).
query lies on the plane defined by p, q, and r.

◆ build_AABB_tree()

template<typename TriangleMesh , typename Point3VPM , typename NamedParameters >
void CGAL::Polygon_mesh_processing::build_AABB_tree ( const TriangleMesh &  tm,
AABB_tree< CGAL::AABB_traits< typename Location_traits< TriangleMesh, NamedParameters >::Geom_traits, CGAL::AABB_face_graph_triangle_primitive< TriangleMesh, Point3VPM > > > &  outTree,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

creates an AABB tree suitable for use with locate_with_AABB_tree().

This function should first be called by users who intend to locate multiple points: in this case, it is better to first build an AABB tree, and use the function locate_with_AABB_tree() that takes as parameter an AABB tree, instead of calling locate() multiple times, which will build a new AABB tree on every call.

Template Parameters
TriangleMesha model of FaceListGraph
Point3VPMa class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and the CGAL 3D point type (your kernel's Point_3) as value type.
NamedParametersa sequence of Named Parameters
Parameters
tma triangulated surface mesh
outTreeoutput parameter that stores the computed AABB_tree
npan optional sequence of Named Parameters among the ones listed below:
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. If this parameter is omitted, an internal property map for boost::vertex_point_t must be available in TriangleMesh.

◆ construct_point()

template<typename TriangleMesh , typename NamedParameters >
Location_traits<TriangleMesh, NamedParameters>::Point CGAL::Polygon_mesh_processing::construct_point ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const TriangleMesh &  tm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns the geometric position described by these coordinates, as a point.

Template Parameters
TriangleMesha model of FaceGraph
NamedParametersa sequence of Named Parameters
Parameters
locthe location to transform into a point
tma triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below:
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. If this parameter is omitted, an internal property map for boost::vertex_point_t must be available in TriangleMesh.
geom_traitsa geometric traits class instance, model of Kernel.
Precondition
loc.first is a face descriptor corresponding to a face of tm.

◆ get_descriptor_from_location()

template<typename TriangleMesh >
Location_traits< TriangleMesh >::descriptor_variant CGAL::Polygon_mesh_processing::get_descriptor_from_location ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns a descriptor to the simplex of smallest dimension on which the point corresponding to the location lies.

In other words:

  • if the point lies on a vertex, this function returns a boost::graph_traits<TriangleMesh>::vertex_descriptor v;
  • if the point lies on a halfedge, this function returns a boost::graph_traits<TriangleMesh>::halfedge_descriptor hd (note that in that case, loc.first == face(hd, tm) holds).
  • otherwise, this function returns a boost::graph_traits<TriangleMesh>::face_descriptor fd (equal to loc.first).
Template Parameters
TriangleMesha model of FaceGraph
Parameters
loca location with loc.first a face of tm
tma triangulated surface mesh
Precondition
the location corresponds to a point that is within a face of tm.
loc describes the barycentric coordinates of a point that lives on the face (boundary included), meaning the barycentric coordinates are all positive.

◆ is_in_face() [1/2]

template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_in_face ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is in the face (boundary included) or not.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
loca location with loc.first a face of tm
tma triangulated surface mesh
Precondition
loc.first is a face descriptor corresponding to a face of tm.

◆ is_in_face() [2/2]

template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_in_face ( const typename Location_traits< TriangleMesh >::Barycentric_coordinates &  bar,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a set of barycentric coordinates, returns whether those barycentric coordinates correspond to a point within the face (boundary included), that is, if all the barycentric coordinates are positive.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
baran array of barycentric coordinates
tma triangulated surface mesh

◆ is_on_face_border()

template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_face_border ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the boundary of the face or not.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
loca location with loc.first a face of tm
tma triangulated surface mesh
Precondition
loc.first is a face descriptor corresponding to a face of tm.

◆ is_on_halfedge()

template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_halfedge ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const typename boost::graph_traits< TriangleMesh >::halfedge_descriptor  hd,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the halfedge hd or not.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
loca location with loc.first a face of tm
hda halfedge of tm
tma triangulated surface mesh
Precondition
loc.first is a face descriptor corresponding to a face of tm.

◆ is_on_mesh_border()

template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_mesh_border ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the border of the mesh or not.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
loca location with loc.first a face of tm
tma triangulated surface mesh
Precondition
loc.first is a face descriptor corresponding to a face of tm.

◆ is_on_vertex()

template<typename TriangleMesh >
bool CGAL::Polygon_mesh_processing::is_on_vertex ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const typename boost::graph_traits< TriangleMesh >::vertex_descriptor  vd,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, returns whether the location is on the vertex vd or not.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
loca location with loc.first a face of tm
vda vertex of tm
tma triangulated surface mesh
Precondition
loc.first is a face descriptor corresponding to a face of tm.

◆ locate() [1/2]

template<typename TriangleMesh , typename NamedParameters >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate ( const typename Location_traits< TriangleMesh, NamedParameters >::Point &  p,
const TriangleMesh &  tm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

returns the nearest face location to the given point.

Note that this function will build an AABB tree on each call. If you need to call this function more than once, first use build_AABB_tree() to create a an AABB tree that you can store and use the function locate_with_AABB_tree().

Template Parameters
TriangleMesha model of FaceListGraph.
NamedParametersa sequence of Named Parameters
Parameters
pthe point to locate on the input triangulated surface mesh
tma triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below:
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. If this parameter is omitted, an internal property map for boost::vertex_point_t must be available in TriangleMesh.
geom_traitsa geometric traits class instance, model of Kernel.
snapping_tolerancea tolerance value used to snap barycentric coordinates. Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1. By default, the tolerance is 0.

◆ locate() [2/2]

template<typename TriangleMesh , typename NamedParameters >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate ( const typename Location_traits< TriangleMesh, NamedParameters >::Ray &  ray,
const TriangleMesh &  tm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Returns the face location along ray nearest to its source point.

If the ray does not intersect the mesh, a default constructed location is returned.

Note that this function will build an AABB tree on each call. If you need to call this function more than once, use build_AABB_tree() to cache a copy of the AABB_tree, and use the overloads of this function that accept a reference to an AABB tree as input.

Template Parameters
TriangleMesha model of FaceListGraph.
NamedParametersa sequence of Named Parameters
Parameters
raya ray to intersect with the input triangulated surface mesh
tmthe input triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below:
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. If this parameter is omitted, an internal property map for boost::vertex_point_t must be available in TriangleMesh.
geom_traitsa geometric traits class instance, model of Kernel.
snapping_tolerancea tolerance value used to snap barycentric coordinates. Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1. By default, the tolerance is 0.

◆ locate_in_adjacent_face()

template<typename TriangleMesh >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate_in_adjacent_face ( const typename Location_traits< TriangleMesh >::Face_location &  loc,
const typename boost::graph_traits< TriangleMesh >::face_descriptor  fd,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a location, that is an ordered pair composed of a boost::graph_traits<TriangleMesh>::face_descriptor and an array of barycentric coordinates, and a second face adjacent to the first, return the location of the point in the second face.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
locthe first location, with loc.first being a face of tm
fdthe second face, adjacent to loc.first
tmthe triangle mesh to which he belongs
Precondition
loc corresponds to a point that lies on a face incident to both loc.first and fd.

◆ locate_in_face() [1/4]

template<typename TriangleMesh >
Location_traits< TriangleMesh >::Face_location CGAL::Polygon_mesh_processing::locate_in_face ( const typename boost::graph_traits< TriangleMesh >::halfedge_descriptor  he,
const typename Location_traits< TriangleMesh >::FT  t,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a point described by a halfedge he and a scalar t as p = (1 - t) * source(he, tm) + t * target(he, tm), returns this location along the given edge as a location, that is an ordered pair specifying a face containing the location and the barycentric coordinates of that location in that face.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
hea halfedge of tm
tthe parametric distance of the desired point along he
tma triangulated surface mesh

◆ locate_in_face() [2/4]

template<typename TriangleMesh >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate_in_face ( typename boost::graph_traits< TriangleMesh >::vertex_descriptor  vd,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Returns the location of the given vertex vd as a location, that is an ordered pair specifying a face incident to vd and the barycentric coordinates of the vertex vd in that face.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
vda vertex of tm
tma triangulated surface mesh
Precondition
vd is not an isolated vertex

◆ locate_in_face() [3/4]

template<typename TriangleMesh >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate_in_face ( const typename boost::graph_traits< TriangleMesh >::vertex_descriptor  vd,
const typename boost::graph_traits< TriangleMesh >::face_descriptor  fd,
const TriangleMesh &  tm 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Returns the location of a given vertex as a location in fd, that is an ordered pair composed of fd and of the barycentric coordinates of the vertex in fd.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
Parameters
vda vertex of tm and a vertex of the face fd
fda face of tm
tma triangulated surface mesh
Precondition
fd is not the null face

◆ locate_in_face() [4/4]

template<typename TriangleMesh , typename NamedParameters >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate_in_face ( const typename Location_traits< TriangleMesh, NamedParameters >::Point &  query,
const typename boost::graph_traits< TriangleMesh >::face_descriptor  fd,
const TriangleMesh &  tm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Given a point query and a face fd of a triangulated surface mesh, returns this location as a location, that is an ordered pair composed of fd and of the barycentric coordinates of query with respect to the vertices of fd.

If tm is the input triangulated surface mesh and given the pair (f, bc) such that bc is the triplet of barycentric coordinates (w0, w1, w2), the correspondance between the coordinates in bc and the vertices of the face f is the following:

  • w0 corresponds to source(halfedge(f, tm), tm)
  • w1 corresponds to target(halfedge(f, tm), tm)
  • w2 corresponds to target(next(halfedge(f, tm), tm), tm)
Template Parameters
TriangleMesha model of FaceGraph
NamedParametersa sequence of Named Parameters
Parameters
querya point
fda face of tm
tma triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below:
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. If this parameter is omitted, an internal property map for boost::vertex_point_t must be available in TriangleMesh.
geom_traitsa geometric traits class instance, model of Kernel.
snapping_tolerancea tolerance value used to snap barycentric coordinates. Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1. By default, the tolerance is 0.
Precondition
fd is not the null face

◆ locate_with_AABB_tree() [1/2]

template<typename TriangleMesh , typename Point3VPM , typename NamedParameters >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate_with_AABB_tree ( const typename Location_traits< TriangleMesh, NamedParameters >::Point &  p,
const AABB_tree< CGAL::AABB_traits< typename Location_traits< TriangleMesh, NamedParameters >::Geom_traits, CGAL::AABB_face_graph_triangle_primitive< TriangleMesh, Point3VPM > > > &  tree,
const TriangleMesh &  tm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

returns the face location nearest to the given point, as a location.

Note that it is possible for the triangle mesh to have ambiant dimension 2 (e.g. the mesh is a 2D triangulation, or a CGAL::Surface_mesh<CGAL::Point_2<Kernel> >), as long as an appropriate vertex point property map is passed in the AABB tree, which will convert from 2D to 3D.

Template Parameters
TriangleMesha model of FaceListGraph
Point3VPMa class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and the CGAL 3D point type (your kernel's Point_3) as value type.
NamedParametersa sequence of Named Parameters
Parameters
pthe point to locate on the input triangulated surface mesh
treean AABB tree containing the triangular faces of the input surface mesh to perform the point location with
tma triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below:
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. If this parameter is omitted, an internal property map for boost::vertex_point_t must be available in TriangleMesh.
geom_traitsa geometric traits class instance, model of Kernel.
snapping_tolerancea tolerance value used to snap barycentric coordinates. Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1. By default, the tolerance is 0.

◆ locate_with_AABB_tree() [2/2]

template<typename TriangleMesh , typename Point3VPM , typename NamedParameters >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::locate_with_AABB_tree ( const typename Location_traits< TriangleMesh, NamedParameters >::Ray &  ray,
const AABB_tree< CGAL::AABB_traits< typename Location_traits< TriangleMesh, NamedParameters >::Geom_traits, CGAL::AABB_face_graph_triangle_primitive< TriangleMesh, Point3VPM > > > &  tree,
const TriangleMesh &  tm,
const NamedParameters &  np 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Returns the face location along ray nearest to its source point.

If the ray does not intersect the mesh, a default constructed location is returned.

Template Parameters
TriangleMesha model of FaceListGraph.
Point3VPMa class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and the CGAL 3D point type (your kernel's Point_3) as value type.
NamedParametersa sequence of Named Parameters
Parameters
raya ray to intersect with the input triangulated surface mesh
treean AABB tree containing the triangular faces of the input surface mesh to perform the point location with
tma triangulated surface mesh
npan optional sequence of Named Parameters among the ones listed below:
Named Parameters
vertex_point_mapthe property map with the points associated to the vertices of tm. If this parameter is omitted, an internal property map for boost::vertex_point_t must be available in TriangleMesh.
geom_traitsa geometric traits class instance, model of Kernel.
snapping_tolerancea tolerance value used to snap barycentric coordinates. Depending on the geometric traits used, the computation of the barycentric coordinates might be an inexact construction, thus leading to sometimes surprising values (e.g. a triplet [0.5, 0.5, -1-e17] for a point at the middle of an edge). The coordinates will be snapped towards 0 and 1 if the difference is smaller than the tolerance value, while still ensuring that the total sum of the coordinates is 1. By default, the tolerance is 0.

◆ random_location_on_face()

template<typename TriangleMesh >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::random_location_on_face ( typename boost::graph_traits< TriangleMesh >::face_descriptor  fd,
const TriangleMesh &  tm,
CGAL::Random rnd = get_default_random() 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Returns a random point over the face fd, as a location.

The random point is on the face, meaning that all its barycentric coordinates are positive. It is constructed by uniformly picking a value u between 0 and 1, a value v between 1-u, and setting the barycentric coordinates to u, v, and 1-u-v for respectively the source and target of halfedge(fd, tm), and the third point.

Template Parameters
TriangleMesha model of FaceGraph
Parameters
fda face of tm
tma triangulated surface mesh
rndoptional random number generator

◆ random_location_on_halfedge()

template<typename TriangleMesh >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::random_location_on_halfedge ( typename boost::graph_traits< TriangleMesh >::halfedge_descriptor  hd,
const TriangleMesh &  tm,
CGAL::Random rnd = get_default_random() 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Returns a random point over the halfedge hd, as a location.

The random point is chosen on the halfedge, meaning that all its barycentric coordinates are positive. It is constructed by uniformly generating a value t between 0 and 1 and setting the barycentric coordinates to t, 1-t, and 0 for respetively the source and target of hd, and the third vertex.

Template Parameters
TriangleMesha model of FaceGraph
Parameters
hda halfedge of tm
tma triangulated surface mesh
rndoptional random number generator

◆ random_location_on_mesh()

template<typename TriangleMesh >
Location_traits<TriangleMesh>::Face_location CGAL::Polygon_mesh_processing::random_location_on_mesh ( const TriangleMesh &  tm,
CGAL::Random rnd = get_default_random() 
)

#include <CGAL/Polygon_mesh_processing/locate.h>

Returns a random point over the mesh tm.

The returned location is obtained by choosing a random face of the mesh and a random point on that face. The barycentric coordinates of the point in the face are thus all positive. Note that all faces have the same probability to be chosen.

Template Parameters
TriangleMesha model of FaceGraph
Parameters
tma triangulated surface mesh
rndoptional random number generator
See also
random_location_on_face()