![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index.html.
The Triangulation is a double-linked list of vertexes and faces. It allows for efficient traversal over neighboring vertexes, faces, or edges.
Edge objects are note stored but identified by a face and opposite vertexes.
We use the basic TDS structure with addition information stored on the vertexes.
TDS is spherical by concept. Our polygons are flat, of course. We introduce an artifical vertex acting as opposite to all outer edges of the triangulation.
If you think about projecting our polygons onto a sphere, this would be the south-pole. It is indicated by a special vertex identifier (polygon vertices being identified by non-negative indexes).
Additional edges connect the south pole to each vertex of the polygon.
Initially, the vertexes of the triangulation are identical to the polygon vertexes (plus the south-pole). The algorithm for computing Valid Placements adds (and removes) more vertexes.
Definition at line 185 of file triangulation.h.
#include <triangulation.h>
Classes | |
class | Edge_iterator |
edge iterator. Traverses all edges of the triangulation. Derives from TDS::Edge_iterator and supplies some additional information. More... | |
Public Types | |
typedef Vertex_base< TDS > | Vertex |
a vertex of the triangulation More... | |
typedef TDS::Vertex_handle | Vertex_handle |
handle to a vertex (handles are managed by TDS base class) More... | |
typedef TDS::Face_handle | Face_handle |
handle to a triangulation face (handles are managed by TDS base class) More... | |
typedef TDS::Edge | Edge |
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edge connected to the south-pole More... | |
typedef TDS::Face_circulator | Face_circulator |
a circulating iterator More... | |
typedef std::pair< Vertex_handle, Vertex_handle > | VertexPair |
a pair of vertexes More... | |
typedef std::pair< Edge, Edge > | EdgePair |
a pair of edges More... | |
typedef std::pair< Face_handle, Face_handle > | FacePair |
a pair of faces More... | |
typedef std::pair< Edge_iterator, Edge_iterator > | Edge_range |
a range of edges More... | |
typedef std::pair< Vertex_handle, Vertex_handle > | TwoVertices |
a pair of vertex handles More... | |
Public Member Functions | |
Triangulation (int capacity=-1) | |
default constructor More... | |
Triangulation (const Triangulation &that) | |
copy constructor More... | |
~Triangulation () | |
destructor More... | |
void | setPolygonSize (int n) |
set number of polygon vertexes More... | |
int | size () const |
void | resize (int sz) |
reset number of vertexes in triangulation More... | |
int | countVertexes () const |
int | countFaces () const |
Vertex_handle | operator[] (int i) |
const Vertex_handle | operator[] (int i) const |
Edge_iterator | edges_begin () const |
Edge_iterator | edges_end () const |
Edge_range | edges () const |
TDS::Vertex_iterator | vertices_begin () const |
TDS::Vertex_iterator | vertices_end () const |
FacePair | adjacentFaces (Segment s) const |
EdgePair | adjacentEdges (Edge e) const |
EdgePair | adjacentEdges (Edge e, int i1, int i2) const |
void | mirror (Edge &e) const |
flip the direction of an edge. Keep in mind that Edge object are desribed as a Face + opposite vertex. For each edge, there are two valid interpretations (with opposite faces). More... | |
void | mirror (EdgePair &e2) const |
flip the direction of two edges. More... | |
Face_circulator | incidentFaces (Vertex_handle v) const |
a circular (never-ending) iterator that traverses all faces incident to a given vertex. More... | |
Vertex_handle | oppositeVertex (Edge e) const |
the second vertex opposite to an edge. Keep in mind that Edge object are desribed as a Face + opposite vertex. More... | |
int | thirdVertex (int a, int b) const |
given two vertexes, find the third vertex to complement a triangle More... | |
Edge | edge (int i, int j) const |
construct an edge from two vertexes More... | |
VertexPair | incidentVertexes (Edge e) const |
TwoVertices | adjacentVertices (Segment s) const |
TwoVertices | adjacentVertices (int v) const |
adjacentVertices More... | |
Vertex_handle | createVertex (const Point &p, int i) |
create a new triangulation vertex More... | |
void | createFace (int a, int b, int c) |
insert a new face. Caller is responsible for keeping the triangulation in a consistent state. For instance, all faces must be oriented counter-clockwise. More... | |
void | complement () |
after all faces have been added, create the complementary "outer" edges (connected to the south-pole). More... | |
bool | isComplete () const |
bool | assertEquals (const Triangulation &that) const |
equality assertion for debugging More... | |
methods for computing valid placements | |
Vertex_handle | insertVertexOnEdge (double x) |
split an edge into two More... | |
void | removeVertexFromEdge (int index) |
remove a vertex More... | |
void | addTargetVertices (const frechet::reach::Placements &p) |
add vertexes for computing valid placements More... | |
Vertex_handle | addTargetVertex (const frechet::reach::Placement *p) |
add a vertex for computing valid placements More... | |
Vertex_handle | addVertex (double w) |
add a triangulation vertex on the edge of the polygon (does not correspond to a polygon vertex) More... | |
void | clearTargets () |
clear targets for shortest-path tree search More... | |
void | clearPredecessors () |
used during shortest-paths computation: reset shortest-path tree information on all vertexes More... | |
Static Public Member Functions | |
static Segment | segment (Edge e) |
static Vertex_handle | vertex1 (Edge e) |
static Vertex_handle | vertex2 (Edge e) |
Private Types | |
typedef CGAL::Triangulation_data_structure_2< Vertex_base<>, CGAL::Triangulation_ds_face_base_2<> > | TDS |
Triangulation Data Structure. Instantiates CGAL::Triangulation_data_structure_2 with our customized Vertex_base class. More... | |
typedef std::vector< TDS::Vertex_handle > | VertexMap |
Keeps track of Vertex handles. More... | |
typedef std::map< Segment, TDS::Edge > | NeighborMap |
Private Member Functions | |
void | addVertex (Vertex_handle v, double x, Point p) |
insert a new triangulation vertex into the map More... | |
void | linkNeighbors (Segment s, Edge e) |
keep track of neighboring faces during construction of the triangulation. More... | |
Vertex_handle | third_vertex (Face_handle f, Segment s) |
given two vertexes and a face, find the third vertex of the triangle More... | |
Static Private Member Functions | |
static Vertex_handle | third_vertex (Face_handle f, Vertex_handle v1, Vertex_handle v2) |
given two vertexes and a face, find the third vertex of the triangle More... | |
Private Attributes | |
int | poly_n |
polygon size, number of vertexes in polyong More... | |
TDS | tds |
CGAL Triangulation Data Structure. More... | |
VertexMap | vertices |
NeighborMap | neighbors |
Keeps track of diagonals and their neighborhood during construction. More... | |
TDS::Vertex_handle | south_pole |
a special vertex that completes the TDS structure More... | |
vertex and edge types | |
bool | is_ccw_face (Face_handle f) |
static bool | is_south_pole (Vertex_handle v) |
static bool | is_outer_face (Face_handle f) |
static bool | is_inner_face (Face_handle f) |
static bool | is_outer_edge (Edge e) |
static bool | is_polygon_edge (Edge e) |
static bool | is_diagonal (Edge e) |
typedef TDS::Edge frechet::poly::Triangulation::Edge |
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edge connected to the south-pole
Definition at line 221 of file triangulation.h.
typedef std::pair<Edge_iterator,Edge_iterator> frechet::poly::Triangulation::Edge_range |
a range of edges
Definition at line 267 of file triangulation.h.
typedef std::pair<Edge,Edge> frechet::poly::Triangulation::EdgePair |
a pair of edges
Definition at line 228 of file triangulation.h.
typedef TDS::Face_circulator frechet::poly::Triangulation::Face_circulator |
a circulating iterator
Definition at line 223 of file triangulation.h.
typedef TDS::Face_handle frechet::poly::Triangulation::Face_handle |
handle to a triangulation face (handles are managed by TDS base class)
Definition at line 218 of file triangulation.h.
typedef std::pair<Face_handle,Face_handle> frechet::poly::Triangulation::FacePair |
a pair of faces
Definition at line 230 of file triangulation.h.
|
private |
Definition at line 205 of file triangulation.h.
|
private |
Triangulation Data Structure. Instantiates CGAL::Triangulation_data_structure_2 with our customized Vertex_base class.
Definition at line 196 of file triangulation.h.
typedef std::pair<Vertex_handle,Vertex_handle> frechet::poly::Triangulation::TwoVertices |
a pair of vertex handles
Definition at line 397 of file triangulation.h.
a vertex of the triangulation
Definition at line 214 of file triangulation.h.
typedef TDS::Vertex_handle frechet::poly::Triangulation::Vertex_handle |
handle to a vertex (handles are managed by TDS base class)
Definition at line 216 of file triangulation.h.
|
private |
Keeps track of Vertex handles.
Definition at line 203 of file triangulation.h.
typedef std::pair<Vertex_handle,Vertex_handle> frechet::poly::Triangulation::VertexPair |
a pair of vertexes
Definition at line 226 of file triangulation.h.
Triangulation::Triangulation | ( | int | capacity = -1 | ) |
default constructor
capacity | initial number of vertexes (optional) |
Definition at line 9 of file triangulation.cpp.
Triangulation::Triangulation | ( | const Triangulation & | that | ) |
Triangulation::~Triangulation | ( | ) |
destructor
Definition at line 40 of file triangulation.cpp.
Triangulation::Vertex_handle Triangulation::addTargetVertex | ( | const frechet::reach::Placement * | p | ) |
add a vertex for computing valid placements
p | a valid placement |
Definition at line 108 of file triangulation.cpp.
void Triangulation::addTargetVertices | ( | const frechet::reach::Placements & | p | ) |
add vertexes for computing valid placements
p | a set of valid placements |
Definition at line 89 of file triangulation.cpp.
Triangulation::Vertex_handle Triangulation::addVertex | ( | double | w | ) |
add a triangulation vertex on the edge of the polygon (does not correspond to a polygon vertex)
w | offset on polygon |
Definition at line 95 of file triangulation.cpp.
|
private |
insert a new triangulation vertex into the map
v | handle to a newly created vertex |
x | offset on polygon |
p | point in the plane |
Definition at line 290 of file triangulation.cpp.
Triangulation::EdgePair Triangulation::adjacentEdges | ( | Triangulation::Edge | e | ) | const |
e | an edge in the triangulation |
Definition at line 315 of file triangulation.cpp.
Triangulation::EdgePair Triangulation::adjacentEdges | ( | Edge | e, |
int | i1, | ||
int | i2 | ||
) | const |
e | an edge in the triangulation |
i1 | a vertex |
i2 | a vertex |
Sort edges, so that i1 is incident to result.first and i2 is incident to result.second To put it another way: result.first is opposite i2 result.second is opposite i1
Definition at line 334 of file triangulation.cpp.
Triangulation::FacePair Triangulation::adjacentFaces | ( | Segment | s | ) | const |
Definition at line 356 of file triangulation.cpp.
Triangulation::TwoVertices Triangulation::adjacentVertices | ( | Segment | s | ) | const |
s | a segment (edge or diagonal) of the polygon |
Definition at line 435 of file triangulation.cpp.
Triangulation::TwoVertices Triangulation::adjacentVertices | ( | int | v | ) | const |
adjacentVertices
v | a polygon vertex |
Definition at line 452 of file triangulation.cpp.
bool Triangulation::assertEquals | ( | const Triangulation & | that | ) | const |
equality assertion for debugging
that | triangulation to compare with |
Definition at line 649 of file triangulation.cpp.
void Triangulation::clearPredecessors | ( | ) |
used during shortest-paths computation: reset shortest-path tree information on all vertexes
Definition at line 421 of file triangulation.cpp.
void Triangulation::clearTargets | ( | ) |
clear targets for shortest-path tree search
Definition at line 428 of file triangulation.cpp.
void Triangulation::complement | ( | ) |
after all faces have been added, create the complementary "outer" edges (connected to the south-pole).
Definition at line 486 of file triangulation.cpp.
|
inline |
Definition at line 309 of file triangulation.h.
|
inline |
Definition at line 305 of file triangulation.h.
void Triangulation::createFace | ( | int | a, |
int | b, | ||
int | c | ||
) |
insert a new face. Caller is responsible for keeping the triangulation in a consistent state. For instance, all faces must be oriented counter-clockwise.
a | first vertex |
b | second vertex |
c | third vertex |
Definition at line 457 of file triangulation.cpp.
Triangulation::Vertex_handle Triangulation::createVertex | ( | const Point & | p, |
int | i | ||
) |
create a new triangulation vertex
p | a point in the plane |
i | index of polygon vertex (optional) |
Definition at line 147 of file triangulation.cpp.
Triangulation::Edge Triangulation::edge | ( | int | i, |
int | j | ||
) | const |
construct an edge from two vertexes
i | a triangulation vertex |
j | adjacent triangulation vertex |
Definition at line 399 of file triangulation.cpp.
|
inline |
Definition at line 327 of file triangulation.h.
|
inline |
Definition at line 323 of file triangulation.h.
|
inline |
Definition at line 325 of file triangulation.h.
Triangulation::Face_circulator Triangulation::incidentFaces | ( | Vertex_handle | v | ) | const |
a circular (never-ending) iterator that traverses all faces incident to a given vertex.
v | a vertex in the triangulation |
Definition at line 376 of file triangulation.cpp.
Triangulation::VertexPair Triangulation::incidentVertexes | ( | Edge | e | ) | const |
e | an edge in the triangulation |
Definition at line 413 of file triangulation.cpp.
Triangulation::Vertex_handle Triangulation::insertVertexOnEdge | ( | double | x | ) |
split an edge into two
x | offset on polygon |
v3 + /| \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ v1 +----------+-----------+ v2 \ v| / \ | / \ f | f(2) / \ | / e | / \ | / \ | / \ | / \ | / \|/ + south pole
Definition at line 188 of file triangulation.cpp.
bool Triangulation::is_ccw_face | ( | Face_handle | f | ) |
f | a triangulation face |
Definition at line 564 of file triangulation.cpp.
|
static |
e | a triangulation edge |
Definition at line 74 of file triangulation.cpp.
|
static |
f | a triangulation face |
Definition at line 58 of file triangulation.cpp.
|
static |
e | a triangulation edge |
Definition at line 63 of file triangulation.cpp.
|
static |
f | a triangulation face |
Definition at line 53 of file triangulation.cpp.
|
static |
e | a triangulation edge |
Definition at line 68 of file triangulation.cpp.
|
static |
v | a triangulation vertex |
Definition at line 48 of file triangulation.cpp.
|
inline |
Definition at line 453 of file triangulation.h.
keep track of neighboring faces during construction of the triangulation.
s | a polygon segment (vertex indexes) |
e | a triangulation edge |
Definition at line 522 of file triangulation.cpp.
void Triangulation::mirror | ( | Edge & | e | ) | const |
flip the direction of an edge. Keep in mind that Edge object are desribed as a Face + opposite vertex. For each edge, there are two valid interpretations (with opposite faces).
e | reference to an edge object |
Definition at line 80 of file triangulation.cpp.
void Triangulation::mirror | ( | EdgePair & | e2 | ) | const |
flip the direction of two edges.
e2 | a pair of Edge objects |
Definition at line 84 of file triangulation.cpp.
Triangulation::Vertex_handle Triangulation::operator[] | ( | int | i | ) |
i | index of vertex |
Definition at line 297 of file triangulation.cpp.
const Triangulation::Vertex_handle Triangulation::operator[] | ( | int | i | ) | const |
i | index of vertex |
Definition at line 306 of file triangulation.cpp.
Triangulation::Vertex_handle Triangulation::oppositeVertex | ( | Edge | e | ) | const |
the second vertex opposite to an edge. Keep in mind that Edge object are desribed as a Face + opposite vertex.
e | an edge in the triangulation |
Definition at line 381 of file triangulation.cpp.
void Triangulation::removeVertexFromEdge | ( | int | index | ) |
remove a vertex
index | index of vertex, previously created by insertVertexOnEdge. Undefined if the vertex was not create by insertVertexOnEdge. |
v3 + /| \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ +----------+---e-------+ v2 \ v1| / \ | / \ | f / \ | / \ | / \ | / \ | / \ | / \ | / \|/ + south pole
Definition at line 262 of file triangulation.cpp.
void Triangulation::resize | ( | int | sz | ) |
reset number of vertexes in triangulation
Definition at line 128 of file triangulation.cpp.
|
static |
e | a triangulation edge |
Definition at line 226 of file triangulation.cpp.
void Triangulation::setPolygonSize | ( | int | n | ) |
set number of polygon vertexes
n | number of polygon vertexes |
Definition at line 118 of file triangulation.cpp.
int Triangulation::size | ( | ) | const |
Definition at line 123 of file triangulation.cpp.
|
staticprivate |
given two vertexes and a face, find the third vertex of the triangle
f | a triangulation face |
v1 | first vertex |
v2 | second vertex |
Definition at line 542 of file triangulation.cpp.
|
private |
given two vertexes and a face, find the third vertex of the triangle
f | a triangulation face |
s | two vertexes |
Definition at line 559 of file triangulation.cpp.
int Triangulation::thirdVertex | ( | int | a, |
int | b | ||
) | const |
given two vertexes, find the third vertex to complement a triangle
a | a triangulation vertex |
b | adjacent triangulation vertex |
Definition at line 386 of file triangulation.cpp.
|
static |
e | a triangulation edge |
Definition at line 606 of file triangulation.cpp.
|
static |
e | a triangulation edge |
Definition at line 612 of file triangulation.cpp.
|
inline |
Definition at line 330 of file triangulation.h.
|
inline |
Definition at line 332 of file triangulation.h.
|
private |
Keeps track of diagonals and their neighborhood during construction.
Definition at line 207 of file triangulation.h.
|
private |
polygon size, number of vertexes in polyong
Definition at line 199 of file triangulation.h.
|
private |
a special vertex that completes the TDS structure
Definition at line 210 of file triangulation.h.
|
private |
CGAL Triangulation Data Structure.
Definition at line 201 of file triangulation.h.
|
private |
Definition at line 204 of file triangulation.h.