![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
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)
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_handle > | Funnel |
Public Member Functions | |
PolygonShortestPaths (Triangulation &atri) | |
default constructor More... | |
Triangulation & | triangulation () 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 Funnel & | getFunnel () 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 | |
Triangulation & | tri |
the Triangulation More... | |
Funnel | funnel |
the Funnel More... | |
Definition at line 38 of file shortest_paths.h.
Definition at line 37 of file shortest_paths.h.
Definition at line 36 of file shortest_paths.h.
Definition at line 39 of file shortest_paths.h.
Definition at line 35 of file shortest_paths.h.
PolygonShortestPaths::PolygonShortestPaths | ( | Triangulation & | atri | ) |
default constructor
atri | a triangulation of a polygon |
Definition at line 15 of file shortest_paths.cpp.
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.
frechet::Curve PolygonShortestPaths::find1ShortestPath | ( | double | p1, |
double | p2 | ||
) |
compute the shortest path between two points on the boundary of the polygon
p1 | offset of first point |
p2 | offset of first point |
Definition at line 41 of file shortest_paths.cpp.
void PolygonShortestPaths::findShortestPaths | ( | Vertex_handle | start_point | ) |
traverse the polygon and report found paths
start_point | starting 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.
|
protected |
find a tangent from a point to the funnel
binary search the funnel for a tangent segment
v | next point to consider |
Definition at line 370 of file shortest_paths.cpp.
|
protected |
find a tangent from a point to the left part of the funnel
t1 | first point in left part |
t2 | last point in left part |
v | next point to consider |
Definition at line 403 of file shortest_paths.cpp.
|
protected |
find a tangent from a point to the right part of the funnel
t1 | first point in right part |
t2 | last point in right part |
v | next point to consider |
Definition at line 423 of file shortest_paths.cpp.
|
inline |
for debugging only: access to funnel
Definition at line 94 of file shortest_paths.h.
|
static |
half-plane test.
Given a line segment [ab], is p on the left or the right of the segment?
a | first end of line segment |
b | second end of line segment |
p | point to test for |
Float | floating point type for intermediate computation (could be float,double,long double,...) |
Definition at line 249 of file shortest_paths.h.
|
protected |
tangent test
t | index in funnel |
v | next point to consider |
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.
|
protected |
compute the shortest-paths tree
start_point | start point of the algorithm |
f | start face |
Definition at line 267 of file shortest_paths.cpp.
|
protected |
compute the shortest-paths tree
e | start edge |
Definition at line 298 of file shortest_paths.cpp.
|
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.
|
inline |
Definition at line 57 of file shortest_paths.h.
|
inlinevirtual |
callback-function when backtrcking derived classes hook in to perform additional computations
Definition at line 84 of file shortest_paths.h.
|
protectedvirtual |
called whenever a ne segment is added to the shortest path tree; hook for derived classes
prev | first vertex of the segment |
v | second vertex of the segment |
Reimplemented in frechet::poly::PolygonShortestPathsFS.
Definition at line 85 of file shortest_paths.cpp.
|
protected |
the Funnel
Definition at line 45 of file shortest_paths.h.
|
protected |
the Triangulation
Definition at line 43 of file shortest_paths.h.