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

Detailed Description

compute Shortest-Paths-Tree on a polygon

Given a Polygon, a Triangulation and a set of points: find all shortest paths from one point to all other points.

This is a slight extension of an algorithm by Guibas, Hershberger et al. Based on a "funnel" algorithm by Lee and Preparata.

Search structure is not a finger tree, but a specialized double-ended-queue (because it is much easier to implement).

The class provides some abstract functions that derived classes can override to implement custom activities. (this is where the Free-Space will be updated)

Author
Peter Schäfer

Definition at line 32 of file shortest_paths.h.

#include <shortest_paths.h>

Inherited by frechet::poly::PolygonShortestPathsFS.

Public Types

typedef Triangulation::Vertex_handle Vertex_handle
 
typedef Triangulation::Face_handle Face_handle
 
typedef Triangulation::Face_circulator Face_circulator
 
typedef Triangulation::Edge Edge
 
typedef DoubleEndedQueue< Vertex_handleFunnel
 

Public Member Functions

 PolygonShortestPaths (Triangulation &atri)
 default constructor More...
 
Triangulationtriangulation () const
 
void findShortestPaths (Vertex_handle start_point)
 traverse the polygon and report found paths More...
 
Curve find1ShortestPath (double p1, double p2)
 compute the shortest path between two points on the boundary of the polygon More...
 
virtual void shortestPath ()
 callback-function when a new shortest-path has been found. derived classes hook in to perform additional computations More...
 
virtual void undo ()
 callback-function when backtrcking derived classes hook in to perform additional computations More...
 
void assertFunnel () const
 assertion for unit testing: is the Funnel in a consistent state? More...
 
const FunnelgetFunnel () const
 for debugging only: access to funnel More...
 

Static Public Member Functions

template<typename Float >
static int halfplaneTest (Vertex_handle a, Vertex_handle b, Vertex_handle p)
 half-plane test. More...
 

Protected Member Functions

void search (Vertex_handle start_point, Face_handle f)
 compute the shortest-paths tree More...
 
void search (Edge e)
 compute the shortest-paths tree More...
 
virtual bool updateSPSegment (Vertex_handle prev, Vertex_handle v)
 called whenever a ne segment is added to the shortest path tree; hook for derived classes More...
 
int findTangent (Vertex_handle v) const
 find a tangent from a point to the funnel More...
 
int findTangentLeft (int t1, int t2, Vertex_handle v) const
 find a tangent from a point to the left part of the funnel More...
 
int findTangentRight (int t1, int t2, Vertex_handle v) const
 find a tangent from a point to the right part of the funnel More...
 
bool isTangent (int t, Vertex_handle v) const
 tangent test More...
 

Protected Attributes

Triangulationtri
 the Triangulation More...
 
Funnel funnel
 the Funnel More...
 

Member Typedef Documentation

◆ Edge

◆ Face_circulator

◆ Face_handle

◆ Funnel

◆ Vertex_handle

Constructor & Destructor Documentation

◆ PolygonShortestPaths()

PolygonShortestPaths::PolygonShortestPaths ( Triangulation atri)

default constructor

Parameters
atria triangulation of a polygon

Definition at line 15 of file shortest_paths.cpp.

Member Function Documentation

◆ assertFunnel()

void PolygonShortestPaths::assertFunnel ( ) const

assertion for unit testing: is the Funnel in a consistent state?

both parts of the funnel should be convex and linked with prev pointers

Definition at line 445 of file shortest_paths.cpp.

◆ find1ShortestPath()

frechet::Curve PolygonShortestPaths::find1ShortestPath ( double  p1,
double  p2 
)

compute the shortest path between two points on the boundary of the polygon

Parameters
p1offset of first point
p2offset of first point
Returns
the curve representing the shortest path between p1 and p2

Definition at line 41 of file shortest_paths.cpp.

◆ findShortestPaths()

void PolygonShortestPaths::findShortestPaths ( Vertex_handle  start_point)

traverse the polygon and report found paths

Parameters
start_pointstarting point of the algorithm

Perform a Depth-First-Search of the Dual Tree i.e. we follow the faces of the triangulation and update our funnel as we go.

Definition at line 66 of file shortest_paths.cpp.

◆ findTangent()

int PolygonShortestPaths::findTangent ( Vertex_handle  v) const
protected

find a tangent from a point to the funnel

binary search the funnel for a tangent segment

Parameters
vnext point to consider
Returns
index in funnel, relative to apex

Definition at line 370 of file shortest_paths.cpp.

◆ findTangentLeft()

int PolygonShortestPaths::findTangentLeft ( int  t1,
int  t2,
Vertex_handle  v 
) const
protected

find a tangent from a point to the left part of the funnel

Parameters
t1first point in left part
t2last point in left part
vnext point to consider
Returns
index in funnel, or 0

Definition at line 403 of file shortest_paths.cpp.

◆ findTangentRight()

int PolygonShortestPaths::findTangentRight ( int  t1,
int  t2,
Vertex_handle  v 
) const
protected

find a tangent from a point to the right part of the funnel

Parameters
t1first point in right part
t2last point in right part
vnext point to consider
Returns
index in funnel, or 0

Definition at line 423 of file shortest_paths.cpp.

◆ getFunnel()

const Funnel& frechet::poly::PolygonShortestPaths::getFunnel ( ) const
inline

for debugging only: access to funnel

Returns
the double-ended queue use by the algorithm

Definition at line 94 of file shortest_paths.h.

◆ halfplaneTest()

template<typename Float >
int frechet::poly::PolygonShortestPaths::halfplaneTest ( Vertex_handle  a,
Vertex_handle  b,
Vertex_handle  p 
)
static

half-plane test.

Given a line segment [ab], is p on the left or the right of the segment?

Parameters
afirst end of line segment
bsecond end of line segment
ppoint to test for
Template Parameters
Floatfloating point type for intermediate computation (could be float,double,long double,...)
Returns
< 0 if p is on the left side, > 0 if p is on the right side, 0 if p is colinear to [ab] (assuming a y-down coordinate system!)

Definition at line 249 of file shortest_paths.h.

◆ isTangent()

bool PolygonShortestPaths::isTangent ( int  t,
Vertex_handle  v 
) const
protected

tangent test

Parameters
tindex in funnel
vnext point to consider
Returns
true if the line through v and t is a tangent

Note: hpt==0 means colinear points. We do_not consider them as a tangent; we trust that the triangulator produces no such degenerated triangles.

Definition at line 343 of file shortest_paths.cpp.

◆ search() [1/2]

void PolygonShortestPaths::search ( Vertex_handle  start_point,
Face_handle  f 
)
protected

compute the shortest-paths tree

Parameters
start_pointstart point of the algorithm
fstart face

Definition at line 267 of file shortest_paths.cpp.

◆ search() [2/2]

void PolygonShortestPaths::search ( Edge  e)
protected

compute the shortest-paths tree

Parameters
estart edge

Definition at line 298 of file shortest_paths.cpp.

◆ shortestPath()

virtual void frechet::poly::PolygonShortestPaths::shortestPath ( )
inlinevirtual

callback-function when a new shortest-path has been found. derived classes hook in to perform additional computations

Definition at line 79 of file shortest_paths.h.

◆ triangulation()

Triangulation& frechet::poly::PolygonShortestPaths::triangulation ( ) const
inline
Returns
the underlying triangulation

Definition at line 57 of file shortest_paths.h.

◆ undo()

virtual void frechet::poly::PolygonShortestPaths::undo ( )
inlinevirtual

callback-function when backtrcking derived classes hook in to perform additional computations

Definition at line 84 of file shortest_paths.h.

◆ updateSPSegment()

bool PolygonShortestPaths::updateSPSegment ( Vertex_handle  prev,
Vertex_handle  v 
)
protectedvirtual

called whenever a ne segment is added to the shortest path tree; hook for derived classes

Parameters
prevfirst vertex of the segment
vsecond vertex of the segment
Returns
true if the tree segment has changed

Reimplemented in frechet::poly::PolygonShortestPathsFS.

Definition at line 85 of file shortest_paths.cpp.

Member Data Documentation

◆ funnel

Funnel frechet::poly::PolygonShortestPaths::funnel
protected

the Funnel

Definition at line 45 of file shortest_paths.h.

◆ tri

Triangulation& frechet::poly::PolygonShortestPaths::tri
protected

the Triangulation

Definition at line 43 of file shortest_paths.h.


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