Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::poly::Triangulation Class Reference

Detailed Description

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.

Author
Peter Schäfer

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< TDSVertex
 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_handleVertexPair
 a pair of vertexes More...
 
typedef std::pair< Edge, EdgeEdgePair
 a pair of edges More...
 
typedef std::pair< Face_handle, Face_handleFacePair
 a pair of faces More...
 
typedef std::pair< Edge_iterator, Edge_iteratorEdge_range
 a range of edges More...
 
typedef std::pair< Vertex_handle, Vertex_handleTwoVertices
 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)
 

Member Typedef Documentation

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

◆ Edge_range

a range of edges

Definition at line 267 of file triangulation.h.

◆ EdgePair

a pair of edges

Definition at line 228 of file triangulation.h.

◆ Face_circulator

typedef TDS::Face_circulator frechet::poly::Triangulation::Face_circulator

a circulating iterator

Definition at line 223 of file triangulation.h.

◆ Face_handle

handle to a triangulation face (handles are managed by TDS base class)

Definition at line 218 of file triangulation.h.

◆ FacePair

a pair of faces

Definition at line 230 of file triangulation.h.

◆ NeighborMap

typedef std::map<Segment,TDS::Edge> frechet::poly::Triangulation::NeighborMap
private

Definition at line 205 of file triangulation.h.

◆ TDS

typedef CGAL::Triangulation_data_structure_2< Vertex_base<>, CGAL::Triangulation_ds_face_base_2<> > frechet::poly::Triangulation::TDS
private

Triangulation Data Structure. Instantiates CGAL::Triangulation_data_structure_2 with our customized Vertex_base class.

Definition at line 196 of file triangulation.h.

◆ TwoVertices

a pair of vertex handles

Definition at line 397 of file triangulation.h.

◆ Vertex

a vertex of the triangulation

Definition at line 214 of file triangulation.h.

◆ Vertex_handle

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.

◆ VertexMap

typedef std::vector<TDS::Vertex_handle> frechet::poly::Triangulation::VertexMap
private

Keeps track of Vertex handles.

Definition at line 203 of file triangulation.h.

◆ VertexPair

a pair of vertexes

Definition at line 226 of file triangulation.h.

Constructor & Destructor Documentation

◆ Triangulation() [1/2]

Triangulation::Triangulation ( int  capacity = -1)

default constructor

Parameters
capacityinitial number of vertexes (optional)

Definition at line 9 of file triangulation.cpp.

◆ Triangulation() [2/2]

Triangulation::Triangulation ( const Triangulation that)

copy constructor

Parameters
thatobjet to copy from

Definition at line 18 of file triangulation.cpp.

◆ ~Triangulation()

Triangulation::~Triangulation ( )

destructor

Definition at line 40 of file triangulation.cpp.

Member Function Documentation

◆ addTargetVertex()

Triangulation::Vertex_handle Triangulation::addTargetVertex ( const frechet::reach::Placement p)

add a vertex for computing valid placements

Parameters
pa valid placement
Returns
handle to a newly created triangulation vertex

Definition at line 108 of file triangulation.cpp.

◆ addTargetVertices()

void Triangulation::addTargetVertices ( const frechet::reach::Placements p)

add vertexes for computing valid placements

Parameters
pa set of valid placements

Definition at line 89 of file triangulation.cpp.

◆ addVertex() [1/2]

Triangulation::Vertex_handle Triangulation::addVertex ( double  w)

add a triangulation vertex on the edge of the polygon (does not correspond to a polygon vertex)

Parameters
woffset on polygon
Returns
handle to a newly created triangulation vertex

Definition at line 95 of file triangulation.cpp.

◆ addVertex() [2/2]

void Triangulation::addVertex ( Vertex_handle  v,
double  x,
Point  p 
)
private

insert a new triangulation vertex into the map

Parameters
vhandle to a newly created vertex
xoffset on polygon
ppoint in the plane

Definition at line 290 of file triangulation.cpp.

◆ adjacentEdges() [1/2]

Triangulation::EdgePair Triangulation::adjacentEdges ( Triangulation::Edge  e) const
Parameters
ean edge in the triangulation
Returns
the two edges that are adjacemt to a given egde

Definition at line 315 of file triangulation.cpp.

◆ adjacentEdges() [2/2]

Triangulation::EdgePair Triangulation::adjacentEdges ( Edge  e,
int  i1,
int  i2 
) const
Parameters
ean edge in the triangulation
i1a vertex
i2a vertex
Returns
the two edges that are adjacemt to a given egde

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.

◆ adjacentFaces()

Triangulation::FacePair Triangulation::adjacentFaces ( Segment  s) const
Returns
the two faces that are adjacent to the segment (i,j)

Definition at line 356 of file triangulation.cpp.

◆ adjacentVertices() [1/2]

Triangulation::TwoVertices Triangulation::adjacentVertices ( Segment  s) const
Parameters
sa segment (edge or diagonal) of the polygon
Returns
the two vertices that are opposite a polygon segment

Definition at line 435 of file triangulation.cpp.

◆ adjacentVertices() [2/2]

Triangulation::TwoVertices Triangulation::adjacentVertices ( int  v) const

adjacentVertices

Parameters
va polygon vertex
Returns
the two adjacent vertices

Definition at line 452 of file triangulation.cpp.

◆ assertEquals()

bool Triangulation::assertEquals ( const Triangulation that) const

equality assertion for debugging

Parameters
thattriangulation to compare with
Returns
true if both triangulations are equal

Definition at line 649 of file triangulation.cpp.

◆ clearPredecessors()

void Triangulation::clearPredecessors ( )

used during shortest-paths computation: reset shortest-path tree information on all vertexes

Definition at line 421 of file triangulation.cpp.

◆ clearTargets()

void Triangulation::clearTargets ( )

clear targets for shortest-path tree search

Definition at line 428 of file triangulation.cpp.

◆ complement()

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.

◆ countFaces()

int frechet::poly::Triangulation::countFaces ( ) const
inline
Returns
number of faces in triangulation

Definition at line 309 of file triangulation.h.

◆ countVertexes()

int frechet::poly::Triangulation::countVertexes ( ) const
inline
Returns
numer of vertexes in triangulation (including south-pole)

Definition at line 305 of file triangulation.h.

◆ createFace()

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.

Parameters
afirst vertex
bsecond vertex
cthird vertex

Definition at line 457 of file triangulation.cpp.

◆ createVertex()

Triangulation::Vertex_handle Triangulation::createVertex ( const Point p,
int  i 
)

create a new triangulation vertex

Parameters
pa point in the plane
iindex of polygon vertex (optional)
Returns
a handle to a newly created triangulation vertex

Definition at line 147 of file triangulation.cpp.

◆ edge()

Triangulation::Edge Triangulation::edge ( int  i,
int  j 
) const

construct an edge from two vertexes

Parameters
ia triangulation vertex
jadjacent triangulation vertex
Returns
an Edge of the triangulation, undefined if the vertexes are not adjacent

Definition at line 399 of file triangulation.cpp.

◆ edges()

Edge_range frechet::poly::Triangulation::edges ( ) const
inline
Returns
a pair of iterators

Definition at line 327 of file triangulation.h.

◆ edges_begin()

Edge_iterator frechet::poly::Triangulation::edges_begin ( ) const
inline
Returns
iterator to the egdes in the triangulation

Definition at line 323 of file triangulation.h.

◆ edges_end()

Edge_iterator frechet::poly::Triangulation::edges_end ( ) const
inline
Returns
iterator beyond the end of egdes in the triangulation

Definition at line 325 of file triangulation.h.

◆ incidentFaces()

Triangulation::Face_circulator Triangulation::incidentFaces ( Vertex_handle  v) const

a circular (never-ending) iterator that traverses all faces incident to a given vertex.

Parameters
va vertex in the triangulation
Returns
a circular iterator

Definition at line 376 of file triangulation.cpp.

◆ incidentVertexes()

Triangulation::VertexPair Triangulation::incidentVertexes ( Edge  e) const
Parameters
ean edge in the triangulation
Returns
the two vertexes adjacent to an edge

Definition at line 413 of file triangulation.cpp.

◆ insertVertexOnEdge()

Triangulation::Vertex_handle Triangulation::insertVertexOnEdge ( double  x)

split an edge into two

Parameters
xoffset on polygon
Returns
a handle to a newly created triangulation vertex
                      v3
                       +
                      /| \
                     / |  \
                    /  |   \
                   /   |    \
                  /    |     \
                 /     |      \
                /      |       \
               /       |        \
              /        |         \
             /         |          \
         v1 +----------+-----------+ v2
             \        v|          /
              \        |         /
               \    f  |  f(2)  /
                \      |       /
                 e     |      /
                  \    |     /
                   \   |    /
                    \  |   /
                     \ |  /
                      \|/
                       +
                  south pole

Definition at line 188 of file triangulation.cpp.

◆ is_ccw_face()

bool Triangulation::is_ccw_face ( Face_handle  f)
Parameters
fa triangulation face
Returns
true if the face is oriented counter clock-wise

Definition at line 564 of file triangulation.cpp.

◆ is_diagonal()

bool Triangulation::is_diagonal ( Edge  e)
static
Parameters
ea triangulation edge
Returns
true if e is a diagonal in the polygon

Definition at line 74 of file triangulation.cpp.

◆ is_inner_face()

bool Triangulation::is_inner_face ( Face_handle  f)
static
Parameters
fa triangulation face
Returns
true if f is an proper face of the triangulation

Definition at line 58 of file triangulation.cpp.

◆ is_outer_edge()

bool Triangulation::is_outer_edge ( Edge  e)
static
Parameters
ea triangulation edge
Returns
true if e is an artifical edge adjacent to the south-pole

Definition at line 63 of file triangulation.cpp.

◆ is_outer_face()

bool Triangulation::is_outer_face ( Face_handle  f)
static
Parameters
fa triangulation face
Returns
true if f is an artifical face adjacent to the south-pole

Definition at line 53 of file triangulation.cpp.

◆ is_polygon_edge()

bool Triangulation::is_polygon_edge ( Edge  e)
static
Parameters
ea triangulation edge
Returns
true if e is an edge of the polygon

Definition at line 68 of file triangulation.cpp.

◆ is_south_pole()

bool Triangulation::is_south_pole ( Vertex_handle  v)
static
Parameters
va triangulation vertex
Returns
true if v is the "south-pole" vertex

Definition at line 48 of file triangulation.cpp.

◆ isComplete()

bool frechet::poly::Triangulation::isComplete ( ) const
inline
Returns
true if all neighboring faces have been inserted

Definition at line 453 of file triangulation.h.

◆ linkNeighbors()

void Triangulation::linkNeighbors ( Segment  s,
Edge  e 
)
private

keep track of neighboring faces during construction of the triangulation.

Parameters
sa polygon segment (vertex indexes)
ea triangulation edge

Definition at line 522 of file triangulation.cpp.

◆ mirror() [1/2]

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

Parameters
ereference to an edge object

Definition at line 80 of file triangulation.cpp.

◆ mirror() [2/2]

void Triangulation::mirror ( EdgePair e2) const

flip the direction of two edges.

Parameters
e2a pair of Edge objects

Definition at line 84 of file triangulation.cpp.

◆ operator[]() [1/2]

Triangulation::Vertex_handle Triangulation::operator[] ( int  i)
Parameters
iindex of vertex
Returns
a handle to a triangulation vertex

Definition at line 297 of file triangulation.cpp.

◆ operator[]() [2/2]

const Triangulation::Vertex_handle Triangulation::operator[] ( int  i) const
Parameters
iindex of vertex
Returns
an immutable handle to a triangulation vertex

Definition at line 306 of file triangulation.cpp.

◆ oppositeVertex()

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.

Parameters
ean edge in the triangulation
Returns
the second vertex opposite to the given edge.

Definition at line 381 of file triangulation.cpp.

◆ removeVertexFromEdge()

void Triangulation::removeVertexFromEdge ( int  index)

remove a vertex

Parameters
indexindex 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.

◆ resize()

void Triangulation::resize ( int  sz)

reset number of vertexes in triangulation

Definition at line 128 of file triangulation.cpp.

◆ segment()

Segment Triangulation::segment ( Triangulation::Edge  e)
static
Parameters
ea triangulation edge
Returns
the associated polygon Segment (polygon vertex indexes)

Definition at line 226 of file triangulation.cpp.

◆ setPolygonSize()

void Triangulation::setPolygonSize ( int  n)

set number of polygon vertexes

Parameters
nnumber of polygon vertexes

Definition at line 118 of file triangulation.cpp.

◆ size()

int Triangulation::size ( ) const
Returns
number of vertexes in triangulation (not including south-pole)

Definition at line 123 of file triangulation.cpp.

◆ third_vertex() [1/2]

Triangulation::Vertex_handle Triangulation::third_vertex ( Face_handle  f,
Vertex_handle  v1,
Vertex_handle  v2 
)
staticprivate

given two vertexes and a face, find the third vertex of the triangle

Parameters
fa triangulation face
v1first vertex
v2second vertex
Returns
third vertex that makes up the triangle

Definition at line 542 of file triangulation.cpp.

◆ third_vertex() [2/2]

Triangulation::Vertex_handle Triangulation::third_vertex ( Face_handle  f,
Segment  s 
)
private

given two vertexes and a face, find the third vertex of the triangle

Parameters
fa triangulation face
stwo vertexes
Returns
third vertex that makes up the triangle

Definition at line 559 of file triangulation.cpp.

◆ thirdVertex()

int Triangulation::thirdVertex ( int  a,
int  b 
) const

given two vertexes, find the third vertex to complement a triangle

Parameters
aa triangulation vertex
badjacent triangulation vertex
Returns
third vertex, undefined if the vertexes are not adjacent

Definition at line 386 of file triangulation.cpp.

◆ vertex1()

Triangulation::Vertex_handle Triangulation::vertex1 ( Edge  e)
static
Parameters
ea triangulation edge
Returns
a handle to the first vertex of the edge

Definition at line 606 of file triangulation.cpp.

◆ vertex2()

Triangulation::Vertex_handle Triangulation::vertex2 ( Edge  e)
static
Parameters
ea triangulation edge
Returns
a handle to the second vertex of the edge

Definition at line 612 of file triangulation.cpp.

◆ vertices_begin()

TDS::Vertex_iterator frechet::poly::Triangulation::vertices_begin ( ) const
inline
Returns
iterator to the vertexes in the triangulation

Definition at line 330 of file triangulation.h.

◆ vertices_end()

TDS::Vertex_iterator frechet::poly::Triangulation::vertices_end ( ) const
inline
Returns
iterator beyond the end of vertexes in the triangulation

Definition at line 332 of file triangulation.h.

Member Data Documentation

◆ neighbors

NeighborMap frechet::poly::Triangulation::neighbors
private

Keeps track of diagonals and their neighborhood during construction.

Definition at line 207 of file triangulation.h.

◆ poly_n

int frechet::poly::Triangulation::poly_n
private

polygon size, number of vertexes in polyong

Definition at line 199 of file triangulation.h.

◆ south_pole

TDS::Vertex_handle frechet::poly::Triangulation::south_pole
private

a special vertex that completes the TDS structure

Definition at line 210 of file triangulation.h.

◆ tds

TDS frechet::poly::Triangulation::tds
private

CGAL Triangulation Data Structure.

Definition at line 201 of file triangulation.h.

◆ vertices

VertexMap frechet::poly::Triangulation::vertices
private

Definition at line 204 of file triangulation.h.


The documentation for this class was generated from the following files: