Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
shortest_paths.h
Go to the documentation of this file.
1 #ifndef SHORTEST_PATHS_H
2 #define SHORTEST_PATHS_H
3 
4 #include <data/types.h>
5 #include <triangulation.h>
6 #include <double_queue.h>
7 #include <graph_m4ri.h>
8 
9 #ifdef QT_DEBUG
10 class TriangulationTestSuite;
11 #endif
12 
13 namespace frechet { namespace poly {
14 
33 {
34 public:
40 
41 protected:
46 
47 public:
53 
57  Triangulation& triangulation() const { return tri; }
58 
63  void findShortestPaths(Vertex_handle start_point);
64 
73  Curve find1ShortestPath(double p1, double p2);
74 
79  virtual void shortestPath() {}
84  virtual void undo() {}
85 
89  void assertFunnel() const;
94  const Funnel& getFunnel() const { return funnel; }
95 
96 protected:
102  void search(Vertex_handle start_point, Face_handle f);
107  void search(Edge e);
108 
116  virtual bool updateSPSegment(Vertex_handle prev, Vertex_handle v);
117 
123  int findTangent(Vertex_handle v) const;
131  int findTangentLeft(int t1, int t2, Vertex_handle v) const;
139  int findTangentRight(int t1, int t2, Vertex_handle v) const;
146  bool isTangent(int t, Vertex_handle v) const;
147 
148 public:
165  template<typename Float>
167 };
168 
185 {
186 private:
190  QLineF d;
192  double epsilon;
195 
196 public:
202 
203  void findShortestPaths(Vertex_handle start_point,
204  const frechet::reach::Placement* asource,
205  QLineF d, double epsilon,
207 
208 protected:
220 
230  virtual bool updateSPSegment(Vertex_handle prev, Vertex_handle v) override;
231 
232 public:
233 #ifdef QT_DEBUG
234  friend class ::TriangulationTestSuite;
236 #endif
237  typedef void (*assert_hook1) (PolygonShortestPathsFS*, Vertex_handle v, bool reachable);
243 };
244 
245 } } // namespace frechet::poly
246 
247 
248 template<typename Float>
250 {
251  // for extra vertexes on a polygon edges, we can detect colinearity from their offset
252  double x1 = floor(a->offset);
253  double x2 = lower_floor(b->offset);
254  if ((x1==x2) && (p->offset >= x1) && (p->offset <= (x1+1)))
255  return 0;
256  // otherwise: calculate from geometry
257  Float ax = a->x();
258  Float ay = a->y();
259  Float bx = b->x();
260  Float by = b->y();
261  Float px = p->x();
262  Float py = p->y();
263 
264  Float A = (py-ay) * (bx-ax);
265  Float B = (px-ax) * (by-ay);
266  if (A < B) return -1;
267  if (A > B) return +1;
268  return 0;
269 }
270 
271 #endif // SHORTEST_PATHS_H
Triangulation & tri
the Triangulation
Triangulation::Face_handle Face_handle
static assert_hook1 after_target_found
unit test and debugging hook function; called when a target vertex is found
Triangulation::Vertex_handle Vertex_handle
virtual void undo()
callback-function when backtrcking derived classes hook in to perform additional computations
int findTangentRight(int t1, int t2, Vertex_handle v) const
find a tangent from a point to the right part of the funnel
Triangulation::Face_circulator Face_circulator
global definitions for all algorithms.
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....
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
void(* assert_hook1)(PolygonShortestPathsFS *, Vertex_handle v, bool reachable)
TDS::Face_handle Face_handle
handle to a triangulation face (handles are managed by TDS base class)
double epsilon
free-space parameter epsilon
Guibas' Algorithm with additional Free-Space computation.
virtual void shortestPath()
callback-function when a new shortest-path has been found. derived classes hook in to perform additio...
void findShortestPaths(Vertex_handle start_point)
traverse the polygon and report found paths
const frechet::reach::Placement * source
source placement and
void propagateReachability(Vertex_handle v)
update free-space and reachability info, called when a vertex is updated in the shortest-paths tree
void search(Vertex_handle start_point, Face_handle f)
compute the shortest-paths tree
bool isTangent(int t, Vertex_handle v) const
tangent test
Triangulation & triangulation() const
PolygonShortestPathsFS(Triangulation &atri)
default constructor
static int halfplaneTest(Vertex_handle a, Vertex_handle b, Vertex_handle p)
half-plane test.
Curve find1ShortestPath(double p1, double p2)
compute the shortest path between two points on the boundary of the polygon
int lower_floor(double x, int min=0)
floor function with lower limit
Definition: numeric.h:243
DoubleEndedQueue< Vertex_handle > Funnel
void findShortestPaths(Vertex_handle start_point, const frechet::reach::Placement *asource, QLineF d, double epsilon, frechet::reach::Graph::ptr validPlacements)
static assert_hook2 after_placement_added
unit test and debugging hook function; called when a valid placement is updated
int findTangentLeft(int t1, int t2, Vertex_handle v) const
find a tangent from a point to the left part of the funnel
void assertFunnel() const
assertion for unit testing: is the Funnel in a consistent state?
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
Definition: types.h:20
boost::shared_ptr< Graph > ptr
Definition: graph_boost.h:59
void(* assert_hook2)(PolygonShortestPathsFS *, const frechet::reach::Placement *, const frechet::reach::Placement *)
void initReachability(Vertex_handle v)
set up reachability info for a triangulation vertex
placement of a diagonal point in free-space diagram When calculating valid placements in [buchin06]
Definition: graph_model.h:132
compute Shortest-Paths-Tree on a polygon
PolygonShortestPaths(Triangulation &atri)
default constructor
TDS::Face_circulator Face_circulator
a circulating iterator
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
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
int findTangent(Vertex_handle v) const
find a tangent from a point to the funnel
const Funnel & getFunnel() const
for debugging only: access to funnel
frechet::reach::Graph::ptr validPlacements
result: holds the valid placements on return