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

Detailed Description

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.

Author
Peter Schäfer

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 *)
 
- Public Types inherited from frechet::poly::PolygonShortestPaths
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

 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)
 
- Public Member Functions inherited from frechet::poly::PolygonShortestPaths
 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 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...
 
- Protected Member Functions inherited from frechet::poly::PolygonShortestPaths
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::Placementsource
 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

- Static Public Member Functions inherited from frechet::poly::PolygonShortestPaths
template<typename Float >
static int halfplaneTest (Vertex_handle a, Vertex_handle b, Vertex_handle p)
 half-plane test. More...
 
- Protected Attributes inherited from frechet::poly::PolygonShortestPaths
Triangulationtri
 the Triangulation More...
 
Funnel funnel
 the Funnel More...
 

Member Typedef Documentation

◆ assert_hook1

typedef void(* frechet::poly::PolygonShortestPathsFS::assert_hook1) (PolygonShortestPathsFS *, Vertex_handle v, bool reachable)

Definition at line 237 of file shortest_paths.h.

◆ assert_hook2

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.

Constructor & Destructor Documentation

◆ PolygonShortestPathsFS()

PolygonShortestPathsFS::PolygonShortestPathsFS ( Triangulation atri)

default constructor

Parameters
atrithe underlying triangulation

Definition at line 19 of file shortest_paths.cpp.

Member Function Documentation

◆ findShortestPaths()

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.

◆ initReachability()

void PolygonShortestPathsFS::initReachability ( Vertex_handle  v)
protected

set up reachability info for a triangulation vertex

Parameters
va vertex in the triangulation

Definition at line 178 of file shortest_paths.cpp.

◆ propagateReachability()

void PolygonShortestPathsFS::propagateReachability ( Vertex_handle  v)
protected

update free-space and reachability info, called when a vertex is updated in the shortest-paths tree

Parameters
va vertex in the triangulation

Assumes v->L,B,R is already. calculated Calculate reachable intervals.

Definition at line 223 of file shortest_paths.cpp.

◆ updateSPSegment()

bool PolygonShortestPathsFS::updateSPSegment ( Vertex_handle  prev,
Vertex_handle  v 
)
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.

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

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.

Member Data Documentation

◆ after_placement_added

PolygonShortestPathsFS::assert_hook2 PolygonShortestPathsFS::after_placement_added = nullptr
static

unit test and debugging hook function; called when a valid placement is updated

Definition at line 242 of file shortest_paths.h.

◆ after_target_found

PolygonShortestPathsFS::assert_hook1 PolygonShortestPathsFS::after_target_found = nullptr
static

unit test and debugging hook function; called when a target vertex is found

Definition at line 240 of file shortest_paths.h.

◆ d

QLineF frechet::poly::PolygonShortestPathsFS::d
private

diagonal

Definition at line 190 of file shortest_paths.h.

◆ epsilon

double frechet::poly::PolygonShortestPathsFS::epsilon
private

free-space parameter epsilon

Definition at line 192 of file shortest_paths.h.

◆ source

const frechet::reach::Placement* frechet::poly::PolygonShortestPathsFS::source
private

source placement and

Definition at line 188 of file shortest_paths.h.

◆ validPlacements

frechet::reach::Graph::ptr frechet::poly::PolygonShortestPathsFS::validPlacements
private

result: holds the valid placements on return

Definition at line 194 of file shortest_paths.h.


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