CGAL 5.5.1 - Triangulated Surface Mesh Shortest Paths
SurfaceMeshShortestPathTraits Concept Reference

## Definition

The concept SurfaceMeshShortestPathTraits describes the types, predicates, and constructions required by the traits class parameter of CGAL::Surface_mesh_shortest_path.

Refines:
CopyConstructible and Assignable
Has Models:
CGAL::Surface_mesh_shortest_path_traits<K,P>

## Types

typedef unspecified_type Triangle_mesh
A model of the concept FaceListGraph

typedef unspecified_type FT
A model of the concept FieldWithSqrt or a model of both Field and RealEmbeddable.

typedef unspecified_type Point_2
The 2-dimensional point type.

typedef unspecified_type Vector_2
The 2-dimensional vector type.

typedef unspecified_type Ray_2
The 2-dimensional ray type.

typedef unspecified_type Line_2
The 2-dimensional line type.

typedef unspecified_type Segment_2
The 2-dimensional segment type.

typedef unspecified_type Triangle_2
The 2-dimensional triangle type.

typedef unspecified_type Barycentric_coordinates
An ordered triple to specify barycentric coordinates in triangles.

typedef unspecified_type Point_3
The 3-dimensional point type.

typedef unspecified_type Vector_3
The 3-dimensional vector type.

typedef unspecified_type Ray_3
The 3-dimensional ray type.

typedef unspecified_type Triangle_3
The 3-dimensional triangle type.

## Constructions

typedef unspecified_type Construct_point_2
Function object type that provides Point_2 operator()(FT x, FT y) and Point_2 operator()(CGAL::ORIGIN) to construct points with cartesian coordinates (x,y) and (0,0) respectively.

typedef unspecified_type Construct_vector_2
Function object type that provides Vector_2 operator()(Point_2 a, Point_2 b) to construct the vector b - a

typedef unspecified_type Construct_ray_2
Function object type that provides Ray_2 operator()(Point_2 a, Point_2 b) to construct the ray originating from a and passing through b

typedef unspecified_type Construct_line_2
Function object type that provides Line_2 operator()(Segment_2 s) and Line_2 operator()(Ray_2 r) to construct the supporting line to s and r respectively.

typedef unspecified_type Construct_segment_2
Function object type that provides Segment_2 operator()(Point_2 a, Point_2 b) to construct the segment (a,b)

typedef unspecified_type Construct_triangle_2
Function object type that provides Triangle_2 operator()(Point_2 a, Point_2 b, Point_2 c) to construct the triangle (a,b,c)

typedef unspecified_type Construct_vertex_2
Function object type that provides Point_2 operator()(Segment_2 s, int i) to return the source or target of s, depending on whether i is 0 or 1 respectively, and Point_2 operator()(Triangle_2 t, int i) to return the ith vertex of t.

typedef unspecified_type Construct_source_2
Function object type that provides Point_2 operator()(Segment_2 s) to return the source of s.

typedef unspecified_type Construct_target_2
Function object type that provides Point_2 operator()(Segment_2 s) to return the target of s.

typedef unspecified_type Construct_barycenter_2
Function object type that provides Point_2 operator()(Point_2 p1, FT w1, Point_2 p2, FT w2) to compute the barycenter of the points p1 and p2 with corresponding weights w1 and w2, and Point_2 operator()(Point_2 p1, FT w1, Point_2 p2, FT w2, Point_2 p3, FT w3) to compute the barycenter of the points p1, p2, and p3 with corresponding weights w1, w2, and w3.

typedef unspecified_type Compute_squared_distance_2
Function object type that provides FT operator()(A obj1, B obj2) to compute the squared distance between obj1 and obj2, A and B can be any one of Point_2, Segment_2, type objects.

typedef unspecified_type Intersect_2
Function object type. More...

typedef unspecified_type Construct_point_on_2
Function object type that provides Point_2 operator()(Ray_2 r, int i) to construct a point on r, such that i = 0 is the source, and any i > 0 is not the source.

typedef unspecified_type Construct_vector_3
Function object type that provides Vector_3 operator()(Point_3 a, Point_3 b) to construct the vector b - a

typedef unspecified_type Construct_triangle_3
Function object type that provides Triangle_3 operator()(Point_3 a, Point_3 b, Point_3 c) to construct the triangle (a,b,c)

typedef unspecified_type Construct_vertex_3
Function object type that provides Point_3 operator()(Segment_3 s, int i) to return the source or target of s, depending on whether i is 0 or 1 respectively, and Point_3 operator()(Triangle_3 t, int i) to return the ith vertex of t.

typedef unspecified_type Construct_source_3
Function object type that provides Point_3 operator()(Segment_3 s) to return the source of s.

typedef unspecified_type Construct_target_3
Function object type that provides Point_3 operator()(Segment_3 s) to return the target of s.

typedef unspecified_type Construct_barycenter_3
Function object type that provides Point_3 operator()(Point_3 p1, FT w1, Point_3 p2) to compute the barycenter of the points p1 and p2 with corresponding weights w1 and 1-w1, and Point_3 operator()(Point_3 p1, FT w1, Point_3 p2, FT w2, Point_3 p3, FT w3) to compute the barycenter of the points p1, p2, and p3 with corresponding weights w1, w2, and w3.

typedef unspecified_type Compute_squared_distance_3
Function object type that provides FT operator()(Point_3 p1, Point_3 p2) to compute the squared distance between p1 and p2.

typedef unspecified_type Construct_triangle_3_to_triangle_2_projection
Function object type that provides Triangle_2 operator()(Triangle_3 t) which computes a 2-dimensional projection of t that preserves edge lengths.

typedef unspecified_type Construct_triangle_3_along_segment_2_flattening
Function object type that provides Triangle_2 operator()(Triangle_3 t, std::size_t i, Segment_2 base) which computes a 2-dimensional projection of t that preserves edge lengths, such that the ith edge of the projection of t is incident to base. More...

typedef unspecified_type Compute_parametric_distance_along_segment_2
Function object type that provides FT operator()(Point_2 x0, Point_2 x1, Point_2 p) which computes the parametric distance of p along the segment [x0,x1]. More...

typedef unspecified_type Construct_barycentric_coordinates
Function object type that provides Barycentric_coordinates operator()(FT a, FT b, FT c) to introduce new triangular barycentric coordinates.

typedef unspecified_type Construct_barycentric_coordinates_weight
Function object type that provides FT operator(Barycentric_coordinates b, std::size_t i) to get the ith weight of barycentric coordinates b.

typedef unspecified_type Construct_barycentric_coordinates_in_triangle_2
Function object type that provides Barycentric_coordinates operator()(Triangle_2 t, Point_2 p) which computes the Barycentric location of p in t.

typedef unspecified_type Construct_barycentric_coordinates_in_triangle_3
Function object type that provides Barycentric_coordinates operator()(Triangle_3 t, Point_3 p) which computes the Barycentric location of p in t.

## Predicates

typedef unspecified_type Classify_barycentric_coordinates
Function object type that provides std::pair<CGAL::Surface_mesh_shortest_paths_3::Barycentric_coordinates_type,std::size_t> operator()(Barycentric_coordinates b), which computes the classification and the associated edge (if applicable) of the coordinates b More...

typedef unspecified_type Orientation_2
Function object type that provides CGAL::Orientation operator()(Point_2 s1, Point_2 s2, Point_2 s3), which performs an orientation test for the given points.

typedef unspecified_type Compare_distance_2
Function object type that provides CGAL::Comparison_result operator()(Point_2 p1, Point_2 p2, Point_2 p3, Point_2 p4), which compares the squared distance between p1 and p2 with the squared distance between p3 and p4.

typedef unspecified_type Compare_relative_intersection_along_segment_2
Function object type that provides CGAL::Comparison_result operator()(Segment_2 s1, Line_2 l1, Segment_2 s2, Line_2 l2). More...

Function object type that provides template <class VertexPointMap> bool operator()(boost::graph_traits<Triangle_mesh>::vertex_descriptor v, Triangle_mesh& tm, VertexPointMap vpm) that returns true if the vertex is a saddle vertex (more than $$2 \pi$$ surface area over all adjacent faces), and false otherwise. More...

## Operations

For all of the above predicate and construction types, e.g.

Func_obj_type, a function must exist with the name func_obj_type_object() that creates an instance of the construction or predicate object type. For example:

Construct_point_2 construct_point_2_object ()
returns the point construction functor.

## ◆ Classify_barycentric_coordinates

Function object type that provides std::pair<CGAL::Surface_mesh_shortest_paths_3::Barycentric_coordinates_type,std::size_t> operator()(Barycentric_coordinates b), which computes the classification and the associated edge (if applicable) of the coordinates b

Returns the pair (type, i), such that type is one of the values of CGAL::Surface_mesh_shortest_paths_3::Barycentric_coordinates_type

• If type is CGAL::Surface_mesh_shortest_paths_3::BARYCENTRIC_COORDINATES_ON_VERTEX, i is the index of that vertex
• If type is CGAL::Surface_mesh_shortest_paths_3::BARYCENTRIC_COORDINATES_ON_BOUNDARY, i is the index of the non-zero edge
• 0 if (0,1) are the non-zero coordinates
• 1 if (1,2) are the non-zero coordinates
• 2 if (2,0) are the non-zero coordinates
• Otherwise, the value of i is undefined.

## ◆ Compare_relative_intersection_along_segment_2

Function object type that provides CGAL::Comparison_result operator()(Segment_2 s1, Line_2 l1, Segment_2 s2, Line_2 l2).

This compares the relative parametric intersections of s1 with l1 against s2 with l2. That is, compare the distance of the intersection of s1 with l1 from the source of s1, scaled by the length of s1, to the distance of the intersection of s2 with l2 from the source of s2, scaled by the length of s2.

Precondition
the intersection of s1 and l1 is a point
the intersection of s2 and l2 is a point

## ◆ Compute_parametric_distance_along_segment_2

Function object type that provides FT operator()(Point_2 x0, Point_2 x1, Point_2 p) which computes the parametric distance of p along the segment [x0,x1].

That is, it computes t, such that p = (1.0 - t)*x0 + t*x1

Precondition
p is a point in the segment [x0,x1]

## ◆ Construct_triangle_3_along_segment_2_flattening

Function object type that provides Triangle_2 operator()(Triangle_3 t, std::size_t i, Segment_2 base) which computes a 2-dimensional projection of t that preserves edge lengths, such that the ith edge of the projection of t is incident to base.

Precondition
The length of the ith edge of t is equal to the length of base

## ◆ Intersect_2

Function object type.

Must provide boost::optional< boost::variant< T... > > operator()(A obj1, B obj2) to compute the intersection between obj1 and obj2, where A and B can be any type amongst Line_2, Ray_2, Segment_2.

Function object type that provides template <class VertexPointMap> bool operator()(boost::graph_traits<Triangle_mesh>::vertex_descriptor v, Triangle_mesh& tm, VertexPointMap vpm) that returns true if the vertex is a saddle vertex (more than $$2 \pi$$ surface area over all adjacent faces), and false otherwise.
vpm must be a model of concept ReadablePropertyMap that maps from vertex_descriptor to Point_3 objects.