![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
Guibas' Algorithm with additional Free-Space computation.
Whenever a new point is added to the SP tree, we calculate (incrementally) Free-Space reachability.
For that purpose, Vertex_base contains additional data members to store free-space and reachability information.
Some points are marked as "Target" points. When they are reached, we have discovered a "valid placmenent" which is recorded in a rechability graph.
Definition at line 184 of file shortest_paths.h.
#include <shortest_paths.h>
Inherits frechet::poly::PolygonShortestPaths.
Public Types | |
typedef void(* | assert_hook1) (PolygonShortestPathsFS *, Vertex_handle v, bool reachable) |
typedef void(* | assert_hook2) (PolygonShortestPathsFS *, const frechet::reach::Placement *, const frechet::reach::Placement *) |
![]() | |
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 | |
PolygonShortestPathsFS (Triangulation &atri) | |
default constructor More... | |
void | findShortestPaths (Vertex_handle start_point, const frechet::reach::Placement *asource, QLineF d, double epsilon, frechet::reach::Graph::ptr validPlacements) |
![]() | |
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 Attributes | |
static assert_hook1 | after_target_found = nullptr |
unit test and debugging hook function; called when a target vertex is found More... | |
static assert_hook2 | after_placement_added = nullptr |
unit test and debugging hook function; called when a valid placement is updated More... | |
Protected Member Functions | |
void | initReachability (Vertex_handle v) |
set up reachability info for a triangulation vertex More... | |
void | propagateReachability (Vertex_handle v) |
update free-space and reachability info, called when a vertex is updated in the shortest-paths tree More... | |
virtual bool | updateSPSegment (Vertex_handle prev, Vertex_handle v) override |
hook function that is called by the shortest-tree search whenever a new segment is added to the tree. We test whether the new vertex is a 'target' vertex, and if so, update its free-space data. Valid placements are updated. More... | |
![]() | |
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... | |
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... | |
Private Attributes | |
const frechet::reach::Placement * | source |
source placement and More... | |
QLineF | d |
diagonal More... | |
double | epsilon |
free-space parameter epsilon More... | |
frechet::reach::Graph::ptr | validPlacements |
result: holds the valid placements on return More... | |
Additional Inherited Members | |
![]() | |
template<typename Float > | |
static int | halfplaneTest (Vertex_handle a, Vertex_handle b, Vertex_handle p) |
half-plane test. More... | |
![]() | |
Triangulation & | tri |
the Triangulation More... | |
Funnel | funnel |
the Funnel More... | |
typedef void(* frechet::poly::PolygonShortestPathsFS::assert_hook1) (PolygonShortestPathsFS *, Vertex_handle v, bool reachable) |
Definition at line 237 of file shortest_paths.h.
typedef void(* frechet::poly::PolygonShortestPathsFS::assert_hook2) (PolygonShortestPathsFS *, const frechet::reach::Placement *, const frechet::reach::Placement *) |
Definition at line 238 of file shortest_paths.h.
PolygonShortestPathsFS::PolygonShortestPathsFS | ( | Triangulation & | atri | ) |
default constructor
atri | the underlying triangulation |
Definition at line 19 of file shortest_paths.cpp.
void PolygonShortestPathsFS::findShortestPaths | ( | Vertex_handle | start_point, |
const frechet::reach::Placement * | asource, | ||
QLineF | d, | ||
double | epsilon, | ||
frechet::reach::Graph::ptr | validPlacements | ||
) |
Definition at line 24 of file shortest_paths.cpp.
|
protected |
set up reachability info for a triangulation vertex
v | a vertex in the triangulation |
Definition at line 178 of file shortest_paths.cpp.
|
protected |
update free-space and reachability info, called when a vertex is updated in the shortest-paths tree
v | a vertex in the triangulation |
Assumes v->L,B,R is already. calculated Calculate reachable intervals.
Definition at line 223 of file shortest_paths.cpp.
|
overrideprotectedvirtual |
hook function that is called by the shortest-tree search whenever a new segment is added to the tree. We test whether the new vertex is a 'target' vertex, and if so, update its free-space data. Valid placements are updated.
prev | first vertex of the segment |
v | second vertex of the segment |
TODO short-cut when the cell is unreachable i.e. when
Reimplemented from frechet::poly::PolygonShortestPaths.
Definition at line 97 of file shortest_paths.cpp.
|
static |
unit test and debugging hook function; called when a valid placement is updated
Definition at line 242 of file shortest_paths.h.
|
static |
unit test and debugging hook function; called when a target vertex is found
Definition at line 240 of file shortest_paths.h.
|
private |
diagonal
Definition at line 190 of file shortest_paths.h.
|
private |
free-space parameter epsilon
Definition at line 192 of file shortest_paths.h.
|
private |
source placement and
Definition at line 188 of file shortest_paths.h.
|
private |
result: holds the valid placements on return
Definition at line 194 of file shortest_paths.h.