#include <CGAL/Surface_mesh_shortest_path/Surface_mesh_shortest_path.h>
template<class Traits, class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
class CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >
Computes shortest surface paths from one or more source points on a surface mesh.
Uses an optimized variation of Chen and Han's \( O(n^2) \) algorithm by Xin and Wang. Refer to those respective papers for the details of the implementation.
- Template Parameters
-
| Traits | a model of SurfaceMeshShortestPathTraits. |
| VIM | a model of ReadablePropertyMap with vertex_descriptor as key and unsigned int as value type. The default is boost::property_map<HG, boost::vertex_index_t>::const_type. |
| HIM | a model of ReadablePropertyMap with halfedge_descriptor as key and unsigned int as value type. The default is boost::property_map<HG, boost::halfedge_index_t>::const_type. |
| FIM | a model of ReadablePropertyMap with face_descriptor as key and unsigned int as value type. The default is boost::property_map<HG, boost::face_index_t>::const_type. |
| VPM | a model of ReadablePropertyMap with vertex_descriptor as key and Traits::Point_3 as value type. The default is boost::property_map<HG, CGAL::vertex_point_t>::const_type. |
If index property maps are not provided through the constructor of the class, internal property maps must be available and initialized.
- See also
CGAL::set_halfedgeds_items_id()
- Examples:
- Surface_mesh_shortest_path/shortest_path_sequence.cpp, Surface_mesh_shortest_path/shortest_path_with_locate.cpp, Surface_mesh_shortest_path/shortest_paths.cpp, Surface_mesh_shortest_path/shortest_paths_multiple_sources.cpp, Surface_mesh_shortest_path/shortest_paths_no_id.cpp, Surface_mesh_shortest_path/shortest_paths_OpenMesh.cpp, and Surface_mesh_shortest_path/shortest_paths_with_id.cpp.
◆ Barycentric_coordinate
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
◆ Barycentric_coordinates
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
An ordered triple which specifies a location inside a triangle as a convex combination of its three vertices.
◆ Face_location
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
An ordered pair specifying a location on the surface of the Triangle_mesh.
If tm is the input graph and given the pair (f, bc) such that bc is (w0, w1, w2), the correspondance with the weights in bc and the vertices of the face f is the following:
w0 = source(halfedge(f,tm),tm)w1 = target(halfedge(f,tm),tm)w2 = target(next(halfedge(f,tm),tm),tm)
◆ Shortest_path_result
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
The return type from shortest path distance queries.
Stores the distance to the nearest source point, and a Source_point_iterator to the source point itself.
◆ Surface_mesh_shortest_path() [1/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
creates a shortest paths object using tm as input.
Equivalent to Surface_mesh_shortest_path(tm, get(boost::vertex_index, tm), get(boost::halfedge_index, tm), get(boost::face_index, tm), get(CGAL::vertex_point, tm), traits).
Internal property maps must be available and initialized.
- See also
CGAL::set_halfedgeds_items_id()
◆ Surface_mesh_shortest_path() [2/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
creates a shortest paths object using tm as input.
No copy of the Triangle_mesh is made, only a reference to the tm is held.
- Parameters
-
| tm | The surface mesh to compute shortest paths on. Note that it must be triangulated. |
| vertexIndexMap | Property map associating an id to each vertex, from 0 to num_vertices(tm) - 1. |
| halfedgeIndexMap | Property map associating an id to each halfedge, from 0 to num_halfedges(tm) - 1. |
| faceIndexMap | Property map associating an id to each face, from 0 to num_faces(tm) - 1. |
| vertexPointMap | Property map used to access the points associated to each vertex of the graph. |
| traits | Optional instance of the traits class to use. |
◆ add_source_point() [1/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
adds v as a source for the shortest path queries.
No change to the internal shortest paths data structure occurs until either Surface_mesh_shortest_path::build_sequence_tree() or the first shortest path query is done.
- Returns
- An iterator to the source point added
◆ add_source_point() [2/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
adds a point inside the face f as a source for the shortest path queries.
No change to the internal shortest paths data structure occurs until either Surface_mesh_shortest_path::build_sequence_tree() or the first shortest path query is done.
- Parameters
-
| f | A face of the input face graph |
| location | Barycentric coordinates in face f specifying the source point. |
- Returns
- An iterator to the source point added
◆ add_source_points()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class InputIterator >
adds a range of points as sources for the shortest path queries.
No change to the internal shortest paths data structure occurs until either Surface_mesh_shortest_path::build_sequence_tree() or the first shortest path query is done.
- Template Parameters
-
- Parameters
-
| begin | iterator to the first in the list of source point locations. |
| end | iterator to one past the end of the list of source point locations. |
- Returns
- An iterator to the first source point added.
◆ build_aabb_tree()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class AABBTraits >
creates an AABB_tree suitable for use with locate.
The following static overload is also available:
- Template Parameters
-
- Parameters
-
| outTree | Output parameter to store the computed AABB_tree |
◆ build_sequence_tree()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
Computes all pending changes to the internal sequence tree.
A call to this method will only trigger a computation only if some change to the set of source points occurred since the last time the sequence tree was computed.
◆ changed_since_last_build()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
determines if the internal sequence tree is valid (already built and no new source point has been added).
- Returns
- true if the structure needs to be rebuilt, false otherwise
◆ clear()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
◆ face_location() [1/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
returns the location of the given vertex as a Face_location
The following static overload is also available:
static Face_location face_location(vertex_descriptor vertex, const Triangle_mesh& tm, const Traits& traits = Traits())
- Parameters
-
| vertex | A vertex of the input face graph |
◆ face_location() [2/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
returns a location along the given edge as a Face_location.
The following static overload is also available:
static Face_location face_location(halfedge_descriptor he, FT t, const Triangle_mesh& tm, const Traits& traits = Traits())
- Parameters
-
| he | A halfedge of the input face graph |
| t | Parametric distance of the desired point along he |
◆ locate() [1/4]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class AABBTraits >
returns the nearest face location to the given point.
Note that this will (re-)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.
The following static overload is also available:
static Face_location locate(const Point_3& p, const Triangle_mesh& tm, Vertex_point_map vertexPointMap, const Traits& traits = Traits())
- Template Parameters
-
- Parameters
-
| p | Point to locate on the input face graph |
◆ locate() [2/4]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class AABBTraits >
returns the face location nearest to the given point.
The following static overload is also available:
- static Face_location locate(const Point_3& p, const AABB_tree<AABBTraits>& tree, const Triangle_mesh& tm, Vertex_point_map vertexPointMap, const Traits& traits = Traits())
- Template Parameters
-
- Parameters
-
| p | Point to locate on the input face graph |
| tree | A AABB_tree containing the triangular faces of the input surface mesh to perform the point location with |
◆ locate() [3/4]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class AABBTraits >
returns the face location along ray nearest to its source point.
Note that this will (re-)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.
The following static overload is also available:
static Face_location locate(const Ray_3& ray, const Triangle_mesh& tm, Vertex_point_map vertexPointMap, const Traits& traits = Traits())
- Template Parameters
-
- Parameters
-
| ray | Ray to intersect with the input face graph |
◆ locate() [4/4]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class AABBTraits >
returns the face location along ray nearest to its source point.
The following static overload is also available:
- static Face_location locate(const Ray_3& ray, const AABB_tree<AABBTraits>& tree, const Triangle_mesh& tm, Vertex_point_map vertexPointMap, const Traits& traits = Traits())
- Template Parameters
-
- Parameters
-
| ray | Ray to intersect with the input face graph |
| tree | A AABB_tree containing the triangular faces of the input surface mesh to perform the point location with |
◆ point() [1/3]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
returns the 3-dimensional coordinates at the barycentric coordinates of the given face.
The following static overloads are also available:
static Point_3 point(face_descriptor f, Barycentric_coordinates location, const Triangle_mesh& tm, const Traits& traits = Traits())static Point_3 point(face_descriptor f, Barycentric_coordinates location, const Triangle_mesh& tm, Vertex_point_map vertexPointMap, const Traits& traits = Traits())
- Parameters
-
| f | A face of on the input face graph |
| location | The barycentric coordinates of the query point on face f |
◆ point() [2/3]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
returns the 3-dimensional coordinates at the parametric location along the given edge.
The following static overloads are also available:
static Point_3 point(halfedge_descriptor edge, FT t, const Triangle_mesh& tm, const Traits& traits = Traits())static Point_3 point(halfedge_descriptor edge, FT t, const Triangle_mesh& tm, Vertex_point_map vertexPointMap, const Traits& traits = Traits())
- Parameters
-
| edge | An edge of the input face graph |
| t | The parametric distance along edge of the desired point |
◆ point() [3/3]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
returns the 3-dimensional coordinates of the given vertex.
- Parameters
-
| vertex | A vertex of the input face graph |
◆ remove_all_source_points()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
removes all source points for the shortest path queries.
No change to the internal shortest paths data structure occurs until either Surface_mesh_shortest_path::build_sequence_tree() or the first shortest path query is done. For a version which deletes all data immediately, use clear() instead.
◆ remove_source_point()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
removes a source point for the shortest path queries.
No change to the internal shortest paths data structure occurs until either Surface_mesh_shortest_path::build_sequence_tree() or the first shortest path query is done. Behaviour is undefined if the source point it was already removed.
- Parameters
-
| it | iterator to the source point to be removed |
◆ shortest_distance_to_source_points() [1/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
Computes the shortest surface distance from a vertex to any source point.
- Parameters
-
| v | A vertex of the input face graph |
- Returns
- A pair, containing the distance to the source point, and an iterator to the source point. If no source point was reachable (can occur when the graph is disconnected), the distance will be a negative value and the source point iterator will be equal to
source_points_end().
◆ shortest_distance_to_source_points() [2/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
Computes the shortest surface distance from any surface location to any source point.
- Parameters
-
| f | A face of the input face graph |
| location | Barycentric coordinates of the query point on face f |
- Returns
- A pair, containing the distance to the source point, and an iterator to the source point. If no source point was reachable (can occur when the graph is disconnected), the distance will be a negative value and the source point iterator will be equal to
source_points_end().
◆ shortest_path_points_to_source_points() [1/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class OutputIterator >
Computes the sequence of points in the shortest path along the surface of the input face graph from the given vertex to the closest source point.
- Parameters
-
| v | A vertex of the input face graph |
| output | An OutputIterator to receive the shortest path points as Point_3 objects |
- Returns
- A pair, containing the distance to the source point, and an iterator to the source point. If no source point was reachable (can occur when the graph is disconnected), the distance will be a negative value and the source point iterator will be equal to
source_points_end().
◆ shortest_path_points_to_source_points() [2/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class OutputIterator >
Computes the sequence of points in the shortest path along the surface of the input face graph from the given query location to the closest source point.
- Parameters
-
| f | A face of on the input face graph |
| location | The barycentric coordinates of the query point on face f |
| output | An OutputIterator to receive the shortest path points as Point_3 objects |
- Returns
- A pair, containing the distance to the source point, and an iterator to the source point. If no source point was reachable (can occur when the graph is disconnected), the distance will be a negative value and the source point iterator will be equal to
source_points_end().
◆ shortest_path_sequence_to_source_points() [1/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class Visitor >
visits the sequence of edges, vertices and faces traversed by the shortest path from a vertex to any source point.
Visits simplices, starting from the query vertex, back to the nearest source point. If no shortest path could be found (for example, the surface is disconnected), then no calls to the visitor will be made (not even for the query vertex).
- Parameters
-
- Returns
- A pair, containing the distance to the source point, and an iterator to the source point. If no source point was reachable (can occur when the graph is disconnected), the distance will be a negative value and the source point iterator will be equal to
source_points_end().
◆ shortest_path_sequence_to_source_points() [2/2]
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class Visitor >
visits the sequence of edges, vertices and faces traversed by the shortest path from any surface location to any source point.
Visits simplices, starting from the query point, back to the nearest source point. If no shortest path could be found (for example, the surface is disconnected), then no calls to the visitor will be made (not even for the query point).
- Parameters
-
| f | A face of the input face graph |
| location | Barycentric coordinates of the query point on face f |
| visitor | A model of SurfaceMeshShortestPathVisitor to receive the shortest path |
- Returns
- A pair, containing the distance to the source point, and an iterator to the source point. If no source point was reachable (can occur when the graph is disconnected), the distance will be a negative value and the source point iterator will be equal to
source_points_end().
◆ source_points_begin()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
returns an iterator to the first source point location
The elements will appear in the order they were inserted to the structure by calls to add_source_point() or add_source_points(). Deleted points will not appear in the sequence.
- Returns
- An iterator to the first of the stored source points.
◆ source_points_end()
template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
returns an iterator to one past the last source point location
- Returns
- An iterator to one past-the-end in the list of stored source points.
1.8.13