CGAL 6.1 - Triangulated Surface Mesh Shortest Paths

Loading...
Searching...
No Matches
List of all members | Classes
CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM > Class Template Reference
Reference Manual

`#include <CGAL/Surface_mesh_shortest_path/Surface_mesh_shortest_path.h>`

## Definition

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_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.

## Classes
class | Source_point_iterator
| A model of `BidirectionalIterator` to access the source points. More...

## Types
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.

## Constructors
| Surface_mesh_shortest_path (const Triangle_mesh &tm, const Traits &traits=Traits())
| creates a shortest paths object using `tm` as input.
| Surface_mesh_shortest_path (const Triangle_mesh &tm, Vertex_index_map vertexIndexMap, Halfedge_index_map halfedgeIndexMap, Face_index_map faceIndexMap, Vertex_point_map vertexPointMap, const Traits &traits=Traits())
| creates a shortest paths object using `tm` as input.

## Addition and Removal of Source Points
Source_point_iterator | add_source_point (vertex_descriptor v)
| adds `v` as a source for the shortest path queries.
Source_point_iterator | add_source_point (const face_descriptor f, const Barycentric_coordinates &location)
| adds a point inside the face `f` as a source for the shortest path queries.
Source_point_iterator | add_source_point (const Face_location &location)
| adds a point inside a face as a source for the shortest path queries, equivalent to `Surface_mesh_shortest_path::add_source_point(location.first, location.second);`
template<class InputIterator >
Source_point_iterator | add_source_points (InputIterator begin, InputIterator end)
| adds a range of points as sources for the shortest path queries.
void | remove_source_point (Source_point_iterator it)
| removes a source point for the shortest path queries.
void | remove_all_source_points ()
| removes all source points for the shortest path queries.

## Creation and Destruction of the Shortest Paths Sequence Tree
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.

## Accessors
Source_point_iterator | source_points_begin () const
| returns an iterator to the first source point location
Source_point_iterator | source_points_end () const
| returns an iterator to one past the last source point location
std::size_t | number_of_source_points () const
| returns the total number of source points used for the shortest path queries.
bool | changed_since_last_build () const
| determines if the internal sequence tree is valid (already built and no new source point has been added).

## Shortest Distance Queries
Shortest_path_result | shortest_distance_to_source_points (const vertex_descriptor v)
| Computes the shortest surface distance from a vertex to any source point.
Shortest_path_result | shortest_distance_to_source_points (const face_descriptor f, const Barycentric_coordinates &location)
| Computes the shortest surface distance from any surface location to any source point.

## Shortest Path Sequence Queries
template<class Visitor >
Shortest_path_result | shortest_path_sequence_to_source_points (const vertex_descriptor v, Visitor &visitor)
| visits the sequence of edges, vertices and faces traversed by the shortest path from a vertex to any source point.
template<class Visitor >
Shortest_path_result | shortest_path_sequence_to_source_points (const face_descriptor f, const Barycentric_coordinates &location, Visitor &visitor)
| visits the sequence of edges, vertices and faces traversed by the shortest path from any surface location to any source point.

## Shortest Path Point Queries
template<class OutputIterator >
Shortest_path_result | shortest_path_points_to_source_points (const vertex_descriptor v, OutputIterator output)
| 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.
template<class OutputIterator >
Shortest_path_result | shortest_path_points_to_source_points (const face_descriptor f, const Barycentric_coordinates &location, OutputIterator output)
| 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.

## Surface Point Constructions
Point_3 | point (const face_descriptor f, const Barycentric_coordinates &location) const
| returns the 3-dimensional coordinates at the barycentric coordinates of the given face.
Point_3 | point (const halfedge_descriptor edge, const FT t) const
| returns the 3-dimensional coordinates at the parametric location along the given edge.
decltype(auto) | point (const vertex_descriptor v) const
| returns the 3-dimensional coordinates of the given vertex.

## Surface Face Location Constructions
Face_location | face_location (const vertex_descriptor vertex) const
| returns the location of the given vertex as a `Face_location`
Face_location | face_location (const halfedge_descriptor he, const FT t) const
| returns a location along the given edge as a `Face_location`.

## Nearest Face Location Queries
template<class AABBTraits >
Face_location | locate (const Point_3 &p) const
| returns the nearest face location to the given point.
template<class AABBTraits >
Face_location | locate (const Point_3 &p, const AABB_tree< AABBTraits > &tree) const
| returns the face location nearest to the given point.
template<class AABBTraits >
Face_location | locate (const Ray_3 &ray) const
| returns the face location along `ray` nearest to its source point.
template<class AABBTraits >
Face_location | locate (const Ray_3 &ray, const AABB_tree< AABBTraits > &tree) const
| returns the face location along `ray` nearest to its source point.
template<class AABBTraits >
void | build_aabb_tree (AABB_tree< AABBTraits > &outTree) const
| creates an `AABB_tree` suitable for use with `locate`.

## Member Typedef Documentation

## ◆ Barycentric_coordinate

template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>

typedef Barycentric_coordinates CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::Barycentric_coordinate

Deprecated:

## ◆ Face_location

template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>

typedef std::pair<face_descriptor, Barycentric_coordinates> CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::Face_location

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>

typedef std::pair<FT, Source_point_iterator> CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::Shortest_path_result

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.

## Constructor & Destructor Documentation

## ◆ Surface_mesh_shortest_path() [1/2]

template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>

CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::Surface_mesh_shortest_path | ( | const Triangle_mesh & | tm,
|  | const Traits & | traits = `Traits()`
| ) |  |

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>

CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::Surface_mesh_shortest_path | ( | const Triangle_mesh & | tm,
|  | Vertex_index_map | vertexIndexMap,
|  | Halfedge_index_map | halfedgeIndexMap,
|  | Face_index_map | faceIndexMap,
|  | Vertex_point_map | vertexPointMap,
|  | const Traits & | traits = `Traits()`
| ) |  |

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.

## Member Function Documentation

## ◆ add_source_point() [1/2]

template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>

Source_point_iterator CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::add_source_point | ( | const face_descriptor | f,
|  | const Barycentric_coordinates & | location
| ) |  |

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>

Source_point_iterator CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::add_source_point | ( | vertex_descriptor | v | ) |

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>
template<class InputIterator >

Source_point_iterator CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::add_source_points | ( | InputIterator | begin,
|  | InputIterator | end
| ) |  |

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

  InputIterator | A `ForwardIterator` which dereferences to either `Surface_mesh_shortest_path::Face_location`, or `Surface_mesh_shortest_path::vertex_descriptor`.

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 >

void CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::build_aabb_tree | ( | AABB_tree< AABBTraits > & | outTree | ) | const

creates an `AABB_tree` suitable for use with `locate`.

The following static overload is also available:

- `static void build_aabb_tree(const Triangle_mesh& tm, AABB_tree<AABBTraits>& outTree)`

Template Parameters

  AABBTraits | A model of `AABBTraits` used to define a CGAL `AABB_tree`.

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>

void CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::build_sequence_tree | ( |  | ) |

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>

bool CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::changed_since_last_build | ( |  | ) | const

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>

void CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::clear | ( |  | ) |

removes all data, the class is as if it was constructed.

All internal containers are cleared and the internal sequence tree is also cleared. For a version which defers deletion until it is necessary, use `Surface_mesh_shortest_path::remove_all_source_points()`.

## ◆ face_location() [1/2]

template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>

Face_location CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::face_location | ( | const halfedge_descriptor | he,
|  | const FT | t
| ) |  | const

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`

## ◆ face_location() [2/2]

template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>

Face_location CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::face_location | ( | const vertex_descriptor | vertex | ) | const

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

## ◆ locate() [1/4]

template<class Traits , class VIM = Default, class HIM = Default, class FIM = Default, class VPM = Default>
template<class AABBTraits >

Face_location CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::locate | ( | const Point_3 & | p | ) | const

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

  AABBTraits | A model of `AABBTraits` used to define a CGAL `AABB_tree`.

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 >

Face_location CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::locate | ( | const Point_3 & | p,
|  | const AABB_tree< AABBTraits > & | tree
| ) |  | const

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

  AABBTraits | A model of `AABBTraits` used to define a CGAL `AABB_tree`.

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 >

Face_location CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::locate | ( | const Ray_3 & | ray | ) | const

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

  AABBTraits | A model of `AABBTraits` used to define an `AABB_tree`.

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 >

Face_location CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::locate | ( | const Ray_3 & | ray,
|  | const AABB_tree< AABBTraits > & | tree
| ) |  | const

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

  AABBTraits | A model of `AABBTraits` used to define a CGAL `AABB_tree`.

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>

Point_3 CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::point | ( | const face_descriptor | f,
|  | const Barycentric_coordinates & | location
| ) |  | const

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>

Point_3 CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::point | ( | const halfedge_descriptor | edge,
|  | const FT | t
| ) |  | const

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>

decltype(auto) CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::point | ( | const vertex_descriptor | v | ) | const

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>

void CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::remove_all_source_points | ( |  | ) |

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>

void CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::remove_source_point | ( | Source_point_iterator | it | ) |

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>

Shortest_path_result CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::shortest_distance_to_source_points | ( | const face_descriptor | f,
|  | const Barycentric_coordinates & | location
| ) |  |

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>

Shortest_path_result CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::shortest_distance_to_source_points | ( | const vertex_descriptor | v | ) |

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>
template<class OutputIterator >

Shortest_path_result CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::shortest_path_points_to_source_points | ( | const face_descriptor | f,
|  | const Barycentric_coordinates & | location,
|  | OutputIterator | output
| ) |  |

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>
template<class OutputIterator >

Shortest_path_result CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::shortest_path_points_to_source_points | ( | const vertex_descriptor | v,
|  | OutputIterator | output
| ) |  |

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 >

Shortest_path_result CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::shortest_path_sequence_to_source_points | ( | const face_descriptor | f,
|  | const Barycentric_coordinates & | location,
|  | Visitor & | 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 >

Shortest_path_result CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::shortest_path_sequence_to_source_points | ( | const vertex_descriptor | v,
|  | Visitor & | 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

  v | A vertex of the input face graph
  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>

Source_point_iterator CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::source_points_begin | ( |  | ) | const

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>

Source_point_iterator CGAL::Surface_mesh_shortest_path< Traits, VIM, HIM, FIM, VPM >::source_points_end | ( |  | ) | const

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.