#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
-
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_OpenMesh.cpp, Surface_mesh_shortest_path/shortest_paths_multiple_sources.cpp, Surface_mesh_shortest_path/shortest_paths_no_id.cpp, and Surface_mesh_shortest_path/shortest_paths_with_id.cpp.
|
|
typedef Traits::Triangle_mesh | Triangle_mesh |
| | The triangle mesh type which this algorithm acts on.
|
|
typedef boost::graph_traits< Triangle_mesh > | Graph_traits |
| | The BGL graph traits for this triangle mesh.
|
|
typedef Graph_traits::vertex_descriptor | vertex_descriptor |
| | Descriptors for the vertices of Triangle_mesh.
|
|
typedef Graph_traits::halfedge_descriptor | halfedge_descriptor |
| | Descriptors for the halfedges of Triangle_mesh.
|
|
typedef Graph_traits::face_descriptor | face_descriptor |
| | Descriptors of the faces of Triangle_mesh.
|
|
typedef VIM | Vertex_index_map |
| | The vertex index property map class.
|
|
typedef HIM | Halfedge_index_map |
| | The halfedge index property map class.
|
|
typedef FIM | Face_index_map |
| | The face index property map class.
|
|
typedef VPM | Vertex_point_map |
| | The vertex point property map class.
|
|
typedef Traits::FT | FT |
| | The numeric type used by this algorithm.
|
|
typedef Traits::Point_3 | Point_3 |
| | The 3-dimensional point type, which must coincide with the value type of Vertex_point_map.
|
|
typedef Traits::Barycentric_coordinates | Barycentric_coordinates |
| | An ordered triple which specifies a location inside a triangle as a convex combination of its three vertices.
|
| typedef Barycentric_coordinates | Barycentric_coordinate |
| typedef std::pair< face_descriptor, Barycentric_coordinates > | Face_location |
| | An ordered pair specifying a location on the surface of the Triangle_mesh.
|
| typedef std::pair< FT, Source_point_iterator > | Shortest_path_result |
| | The return type from shortest path distance queries.
|
|
| void | build_sequence_tree () |
| | Computes all pending changes to the internal sequence tree.
|
| void | clear () |
| | removes all data, the class is as if it was constructed.
|
◆ Barycentric_coordinate
template<class Traits, class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
◆ 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 correspondence 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 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_point() [2/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_points()
template<class Traits, class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
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>
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 a location along the given edge as a Face_location.
The following static overload is also available:
- Parameters
-
| he | A halfedge of the input face graph |
| t | Parametric distance of the desired point along he |
◆ face_location() [2/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:
- Parameters
-
| vertex | A vertex of the input face graph |
◆ locate() [1/4]
template<class Traits, class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
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:
- 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>
returns the face location nearest to the given point.
The following static overload is also available:
- 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>
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:
- 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>
returns the face location along ray nearest to its source point.
The following static overload is also available:
- 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:
- 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:
- 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
-
| v | 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. Behavior 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 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_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 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_path_points_to_source_points() [1/2]
template<class Traits, class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
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_points_to_source_points() [2/2]
template<class Traits, class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
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_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 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().
◆ 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 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().
◆ 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.17.0