Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
algorithm.h
Go to the documentation of this file.
1 #ifndef ALGORITHM_H
2 #define ALGORITHM_H
3 
4 #include <data/types.h>
5 #include <poly/types.h>
6 #include <poly/triangulation.h>
7 #include <freespace.h>
8 #include <fs_path.h>
9 #include <structure.h>
10 #include <graph_m4ri.h>
11 #include <boost/smart_ptr.hpp>
12 #include <boost/unordered_map.hpp>
13 #include <set>
14 #include <shortest_paths.h>
15 #include <data/numeric.h>
16 #include <tbb/concurrent_unordered_map.h>
17 
18 class TriangulationTestSuite;
19 
20 namespace frechet { namespace poly {
21 
22 class PolygonUtilities;
23 class PolygonWorkerJob;
51 class Algorithm : public QObject {
52  // Qt wiring:
53  Q_OBJECT
54 signals:
56  void statusChanged();
60  void pathUpdated(bool valid);
63  void optimisationResult(double epsilon);
64 
65 public slots:
68  void resetStatus(bool stopping=false);
69 
70 public:
76  enum Status : int8_t {
77  RUNNING = -2,
78 
85 
86  YES=0,
87  NO,
88 
113  };
114 
117 
118 protected:
119 #ifdef QT_DEBUG
120  friend class ::TriangulationTestSuite;
122 #endif
123  enum Status _status;
127 
132  struct CurveData {
149 
151  CurveData();
153  ~CurveData();
154 
156  int n() const { return curve.size()-1; }
158  int l() const { return _d_points.size(); }
160  int k() const { return _c_diagonals.size(); }
164  int d(int i) const {
165  i = (i + l()) % l();
166  return _d_points[i];
167  }
169  int partitions() const { return partition.size(); }
170 
174  int calculate_c_diagonals(Segments& result);
177  int calculate_d_points();
178  } *P, *Q;
179 
182 
183  //typedef boost::unordered_map<int,GraphPtr> GraphMap;
185  typedef tbb::concurrent_unordered_map<int,GraphPtr> PlacementMap;
187  typedef std::vector<reach::Placements> PlacementVector;
188 
193 
196 
198  typedef tbb::concurrent_unordered_map<int, reach::Graph::ptr> GraphMap;
199 
202 
210  GraphPtr getValidPlacements(int di, int dj);
217  GraphPtr calculate_RG(int i);
224  int mapKey(int di, int dj);
225 
228 
230  typedef std::vector<double> CriticalValueList;
233 
234 public:
236  typedef boost::shared_ptr<Algorithm> ptr;
237 
239  Algorithm();
241  virtual ~Algorithm();
242 
244  Status status() const { return _status; }
245 
247  bool canDecidePoly() const { return _status==SET_UP; }
249  bool canOptimisePoly() const { return _status==SET_UP || _status==YES || _status==NO; }
251  bool canOptimiseCurve() const { return _status==SET_UP || _status==YES || _status==NO || _status>=P_NOT_CLOSED; }
252 
254  const Segments& c_diagonals() const;
255 
259  bool is_c_diagonal(int di, int dj) const;
262  bool is_c_diagonal(Segment s) const;
263 
270 
272  const Curve& Pcurve() const { return P->curve; }
274  const Curve& Qcurve() const { return Q->curve; }
275 
279  return (primary ? P:Q)->utils;
280  }
281 
291  Status setup(Curve& aP, Curve& aQ, bool fixOrientation=false);
292 
298  bool decompose(bool optimal);
304  void swap();
309  virtual void triangulate();
310 
311  /*
312  * update with new epsilon & free-space
313  * @return true if there is a solution
314  *
315  * return feasible path
316  */
317  //typedef ResultPtr (*decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool);
329  reach::FSPath::ptr path,
330  double epsilon,
331  bool update_status);
332 
342  double optimisePolygon( reach::FSPath::ptr path,
343  double approximation=0.0);
344 
356  reach::FSPath::ptr path,
357  double ignored,
358  bool update_status);
359 
368  double optimiseCurve(double approximation=0.0);
369 
377  static double pickIntervalPoint(const Interval& j, int m=INT_MAX);
378 
379 // static int findFeasibleStart(GraphPtr G);
380 
381 protected:
384  virtual void calculateValidPlacements(double epsilon)=0;
387  virtual void calculateReachabilityGraphs()=0;
388 
391  virtual GraphPtr findFeasiblePath()=0;
392 
398  GraphPtr createValidPlacementGraph(int di, int dj);
406  double epsilon, int di, int dj);
407 
410  Triangulation::Edge diagonalEdge(int i) const;
411 
413  int l() const { return P->l(); }
415  int k() const { return P->k(); }
419  int d(int i) const { return P->d(i); }
420 
422  int partitions() const { return P->partitions(); }
423 
427  void calculatePlacements(int i, frechet::reach::Placements& result);
428 
437  virtual reach::Graph::ptr CRG(int i, int j, Triangulation::Edge e = Triangulation::Edge())=0;
443  virtual reach::Graph::ptr create_RG(int i)=0;
451  virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e)=0;
452 
473  virtual void COMBINE(reach::Graph::ptr A, int di, int dj)=0;
474 
480  virtual void cleanup();
481 
488  void updatePath(reach::FSPath::ptr path, GraphPtr result, double epsilon);
495  void updatePath(reach::FSPath::ptr path, reach::Pointer startPointer, double epsilon);
496 public:
505  void collectCriticalValues(bool a, bool b, bool c, bool d);
511 
512 protected:
518  void collectCriticalValues_b(const Point& p, const Curve& Q);
522  void collectCriticalValues_c(const QLineF& pseg, const Curve& Q);
525  void collectCriticalValues_d(const QLineF& diagonal);
526  // TODO only i
527 
530  virtual void collectCriticalValue(const accurate_float& x);
531 
535  virtual void collectCriticalValues_b(const Curve& P, const Curve& Q)=0;
539  virtual void collectCriticalValues_c(const Curve& P, const Curve& Q)=0;
541  virtual void collectCriticalValues_d()=0;
543  virtual void combineCriticalValues()=0;
547  void removeDuplicates(CriticalValueList& vector);
548 
561  template<typename R>
562  int binarySearch(const std::vector<double>& values, int lo, int hi,
563  R (Algorithm::* decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool),
564  R& result);
565 
578  template<typename R>
579  double intervalSearch(
580  double lower_bound, double upper_bound, double precision,
581  R (Algorithm::* decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool),
582  R& result);
583 
599  template<typename Float>
600  static Float bisector_distance(
601  const Float& p1x, const Float& p1y,
602  const Float& p2x, const Float& p2y,
603  const Float& q1x, const Float& q1y,
604  const Float& q2x, const Float& q2y,
605  const Float& tolerance);
606 
614  template<typename Float>
615  static Float segment_distance(const QLineF& segment, const Point& q1);
616 
627  template<typename Float>
628  static Float bisector_distance(
629  const Point& q1, const Point& q2,
630  const QLineF& segment,
631  Float tolerance=0.0);
632 
636  volatile bool* cancelFlag;
639  void testCancelFlag();
640 };
641 
642 
651 
652 } } // namespace frechet::poly
653 #endif // ALGORITHM_H
virtual void calculateReachabilityGraphs()=0
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map
Represents a polygon line segment from node i to j.
Definition: types.h:39
input data are faulty. Q is not a closed curve.
Definition: algorithm.h:100
std::vector< reach::Placements > PlacementVector
list of valid placements
Definition: algorithm.h:187
int mapKey(int di, int dj)
hash key for memo-ized maps
Definition: algorithm.cpp:614
virtual GraphPtr findFeasiblePath()=0
the main loop of Buchin et al's decision algorithm.
GraphPtr getValidPlacements(int di, int dj)
get valid placements for a given pair of diagonal end points; compute them, if necssary....
Definition: algorithm.cpp:620
the algorithm is currently computing the decision variant for curves
Definition: algorithm.h:82
frechet::reach::Graph::ptr GraphPtr
the result of the decision algorithm is a reachability Graph containing a feasible path
Definition: algorithm.h:116
bool canOptimiseCurve() const
check if we can execute the optimisation variant on curves (Alt and Godau's algorithm)
Definition: algorithm.h:251
initial status: the algorithm is not yet ready to execute
Definition: algorithm.h:90
bool canDecidePoly() const
check if we can execute the decision variant on simple polygons (Buchin et al.'s algorithm)
Definition: algorithm.h:247
std::vector< frechet::reach::Placement > Placements
a list of Placement objects
Definition: graph_model.h:144
virtual void COMBINE(reach::Graph::ptr A, int di, int dj)=0
perform the COMBINE operation, apply valid placements
~CurveData()
destructor; release all memory
Definition: algorithm.cpp:59
void testCancelFlag()
poll cancelFlag
Definition: algorithm.cpp:287
int binarySearch(const std::vector< double > &values, int lo, int hi, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)
perform a binary search on a list of critical values. For each step of the binary search,...
stores essential information about an input curve. This data is processed once for each input curve.
Definition: algorithm.h:132
Status setInitialStatus(Status)
set initial status (after pre-processing input data)
Definition: algorithm.cpp:398
Algorithm()
default constructor
Definition: algorithm.cpp:18
input data have been successfully processed, the algorithm is now ready to execute
Definition: algorithm.h:92
virtual void collectCriticalValues_d()=0
compute critical values for diagonals and reflex vertices
the algorithm is currently computing the approximation variant for curves
Definition: algorithm.h:84
negative result of the decision version
Definition: algorithm.h:87
Status status() const
current status of the algorithm
Definition: algorithm.h:244
Triangulation triangulation
simplified triangulation for P, complete triangulation for Q
Definition: algorithm.h:142
global definitions for all algorithms.
std::vector< double > CriticalValueList
a list of critical values
Definition: algorithm.h:230
CriticalValueList criticalValues
the list of critical values (optimisation variant)
Definition: algorithm.h:232
std::set< Segment > Segments
a set of Segment objects
Definition: types.h:115
input data are faulty. P is convex.
Definition: algorithm.h:110
Algorithm::ptr newPolyAlgorithm(bool topo)
factory method for creating a new algorithm object. Choose the appropriate implementation based on av...
Definition: parallel.cpp:11
Status
indicates the current status of the algorithm. Negative values indicate that the algorithm is current...
Definition: algorithm.h:76
int n() const
number of vertices = number of edges; start/end point is counted once (other than QPolygonF!...
Definition: algorithm.h:156
bool is_c_diagonal(int di, int dj) const
check, whether a diagonal is a c-diagonal
Definition: algorithm.cpp:47
int l() const
number of diagonal end points
Definition: algorithm.h:158
int d(int i) const
map a diagonal end-point to a polygon vertex
Definition: algorithm.h:164
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
void optimisationResult(double epsilon)
emitted when the optimisation (or approximation) algorithm finds a result
Partition partition
simplified polygon C' (containing only the end points of c-diagonals)
Definition: algorithm.h:136
positive result of the decision version
Definition: algorithm.h:86
input data are faulty. P is not a oriented counter-clockwise.
Definition: algorithm.h:106
input data are faulty. Q is not a simple polygon.
Definition: algorithm.h:104
reach::GraphModel::ptr graphModel
map free-space interval to nodes of the reachability graph
Definition: algorithm.h:195
int k() const
number of c-diagonals
Definition: algorithm.h:415
the algorithm is currently computing (decision variant, or optimisation variant)
Definition: algorithm.h:77
boost::shared_ptr< GraphModel > ptr
smart pointer to a GraphModel object
Definition: graph_model.h:307
void resetStatus(bool stopping=false)
reset the status of the algorithm
Definition: algorithm.cpp:413
volatile bool * cancelFlag
indicates user interruption
Definition: algorithm.h:636
boost::shared_ptr< Graph > GraphPtr
Definition: graph_m4ri.h:14
input data are faulty. P is not a simple polygon.
Definition: algorithm.h:102
boost::shared_ptr< Algorithm > ptr
(smart) pointer to an Algorithm object
Definition: algorithm.h:236
FreeSpace::ptr local_fs
Free-Space used during binary searches (optimisation variant)
Definition: algorithm.h:227
the algorithm is currently computing the approximation variant for simple polygons
Definition: algorithm.h:81
virtual void cleanup()
release memory (meoisation maps, etc.)
Definition: algorithm.cpp:550
Guibas' Algorithm with additional Free-Space computation.
struct frechet::poly::Algorithm::CurveData * Q
virtual void combineCriticalValues()=0
hook for post-processing of critical values
Abstract base class for executing the algorithm for simple polygons in a background thread....
Definition: jobs.h:13
void removeDuplicates(CriticalValueList &vector)
remove duplicates from a sorted list of critical values
Definition: optimise.cpp:82
void swap()
swap input curves. The algorithm by Buchin et al. chooses the smalled convex decompositioin as P.
Definition: algorithm.cpp:139
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
Definition: boundary.h:285
static Float bisector_distance(const Float &p1x, const Float &p1y, const Float &p2x, const Float &p2y, const Float &q1x, const Float &q1y, const Float &q2x, const Float &q2y, const Float &tolerance)
compute the distance between a bisector and a polygon segment
bool decompose(bool optimal)
decompose polygons into convex parts
Definition: algorithm.cpp:125
base class for algorithm for simple polygons.
Definition: algorithm.h:51
void updatePath(reach::FSPath::ptr path, GraphPtr result, double epsilon)
compute a feasible path from the result of (Buchin et al.'s) decision algorithm
Definition: algorithm.cpp:537
tbb::concurrent_unordered_map< int, GraphPtr > PlacementMap
hash map for reachability graphs
Definition: algorithm.h:185
tbb::concurrent_unordered_map< int, reach::Graph::ptr > GraphMap
used to store intermediate (memo-ized) reachability graphs
Definition: algorithm.h:198
const Segments & c_diagonals() const
the c-diagonals
Definition: algorithm.cpp:38
Curve curve
P, resp. Q. Must be a closed curve, start and endpoint are duplicated.
Definition: algorithm.h:134
GraphPtr decidePolygon(FreeSpace::ptr fs, reach::FSPath::ptr path, double epsilon, bool update_status)
execute the decision variant for simple polygons (Buchin et al.'s algorithm)
Definition: algorithm.cpp:429
Triangulation & QTriangulation()
the triangulation of Q
Definition: algorithm.h:267
void collectCriticalValues_a()
compute critical values of type (a)
Definition: optimise.cpp:111
long double accurate_float
Definition: numeric.h:42
int d(int i) const
map a diagonal end-point to a vertex in P
Definition: algorithm.h:419
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
Definition: types.h:14
struct frechet::poly::Algorithm::CurveData * P
void statusChanged()
emitted whenever the status of the algorithm changes.
enum Status _status
current status of the algorithm
Definition: algorithm.h:124
boost::shared_ptr< FSPath > ptr
smart pointer to an FSPath object
Definition: fs_path.h:65
double intervalSearch(double lower_bound, double upper_bound, double precision, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)
perform a nested interval search. For each step of the search, perform the decision variant.
void collectCriticalValues_c(const QLineF &pseg, const Curve &Q)
compute critical values of type (c)
Definition: optimise.cpp:157
virtual void triangulate()
compute triangulations of input curves
Definition: algorithm.cpp:144
GraphPtr calculate_RG(int i)
get a Reachability Graph; compute it, if necessary. Subsequent calls retrieve the memo-ized result.
Definition: algorithm.cpp:629
virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e)=0
compute a Combined Reachabilty Graph.
int partitions() const
number of convex partitions (components)
Definition: algorithm.h:422
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
Definition: types.h:20
Triangulation * display_triangulation
complete triangulation for P – only needed for visualisation; not for the algorithm as such
Definition: algorithm.h:144
void pathUpdated(bool valid)
emitted when a feasible path has been found
PlacementMap _validPlacements
map of valid placements (as adjacency matrices, for each c-diagonal)
Definition: algorithm.h:192
const Curve & Qcurve() const
the first input curve Q
Definition: algorithm.h:274
virtual reach::Graph::ptr create_RG(int i)=0
compute an initial Reachabilty Graph.
int calculate_d_points()
calculate the d-points (end points of the diagonals)
Definition: algorithm.cpp:217
std::list< Polygon > Partition
a partitioning of a polygon, that is a list of sub-sets
Definition: types.h:117
static Float segment_distance(const QLineF &segment, const Point &q1)
compute the distance between a polygon segment and a point
boost::shared_ptr< Graph > ptr
Definition: graph_boost.h:59
void calculatePlacements(int i, frechet::reach::Placements &result)
calculate free-space placements
Definition: algorithm.cpp:590
void collectCriticalValues_b(const Point &p, const Curve &Q)
compute critical values of type (b)
Definition: optimise.cpp:125
GraphMap CRG_map
a map of memo-ized Combined Reachability Graphs
Definition: algorithm.h:201
GraphPtr createValidPlacementGraph(int di, int dj)
compute an adjacancy matrix of valid placements for one pair of diagonal end points
Definition: algorithm.cpp:295
virtual reach::Graph::ptr CRG(int i, int j, Triangulation::Edge e=Triangulation::Edge())=0
get a memoised Combined Reachabilty Graph. This is one of the steps in Buchin et al....
Segments _c_diagonals
a list of c-diagonals
Definition: algorithm.h:138
PolygonUtilities * utils
helper class for polygon analysis
Definition: algorithm.h:148
const Curve & Pcurve() const
the first input curve P
Definition: algorithm.h:272
reach::Pointer decideCurve(FreeSpace::ptr fs, reach::FSPath::ptr path, double ignored, bool update_status)
execute the decision variant for curves. (Alt and Godau's algorithm)
Definition: algorithm.cpp:238
PlacementVector _placements
list of placements (for each end point of diagonals)
Definition: algorithm.h:190
double optimiseCurve(double approximation=0.0)
execute the optimisation variant for curves. (Alt and Godau's algorithm)
Definition: optimise.cpp:355
int l() const
number of diagonal end points
Definition: algorithm.h:413
PolygonUtilities * polygonUtilities(bool primary)
helper object for polygon analysis
Definition: algorithm.h:278
input data are faulty. Q is an empty curve.
Definition: algorithm.h:96
Triangulation & displayPTriangulation()
a complete triangulation for P (only needed for visualisation
Definition: algorithm.h:269
Polygon reflex
reflex vertices (for Q only)
Definition: algorithm.h:146
void collectCriticalValues(bool a, bool b, bool c, bool d)
compute a set of critical values for the optimisation variant
Definition: optimise.cpp:37
int calculate_c_diagonals(Segments &result)
calculate the c-diagonals
Definition: algorithm.cpp:198
input data are faulty. Q is not a oriented counter-clockwise.
Definition: algorithm.h:108
virtual ~Algorithm()
destructor; releases all memory
Definition: algorithm.cpp:32
input data are faulty. P is an empty curve.
Definition: algorithm.h:94
virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr A, const reach::Graph::ptr B)=0
perform the final MERGE operation on two Reachability Graphs
Status setup(Curve &aP, Curve &aQ, bool fixOrientation=false)
Initialize input curves and perform some basic sanity checks.
Definition: algorithm.cpp:66
Status setStatus(Status)
set current status
Definition: algorithm.cpp:404
input data are faulty. P is not a closed curve.
Definition: algorithm.h:98
enum Status initial_status
initial status of the algorithm (before or after processing input data)
Definition: algorithm.h:126
FreeSpace::ptr fs
current Free-Space diagram (passed to the decision variant)
Definition: algorithm.h:181
double optimisePolygon(reach::FSPath::ptr path, double approximation=0.0)
execute the optimisaion variant for simple polygons. (Buchin et al.'s algorithm) The result value is ...
Definition: optimise.cpp:252
std::vector< int > Polygon
Polygon a sub-set of vertex indexes.
Definition: types.h:113
input data are faulty. Q is convex.
Definition: algorithm.h:112
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
int k() const
number of c-diagonals
Definition: algorithm.h:160
virtual CriticalValueList & currentCriticalValueList()
get the set of current critical values
Definition: optimise.cpp:29
a helper class for polygon analysis.
Definition: poly_utils.h:121
an interval of two double values.
Definition: interval.h:31
Polygon _d_points
all end points of diagonals
Definition: algorithm.h:140
virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr A, const reach::Graph::ptr B)=0
perform the MERGE operation on two Reachability Graphs
static double pickIntervalPoint(const Interval &j, int m=INT_MAX)
pick a point from a free-space interval. Helper function for creating feasible paths.
Definition: algorithm.cpp:572
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
Definition: freespace.h:92
the algorithm is currently computing the optimisation variant for simple polygons
Definition: algorithm.h:80
the algorithm is currently computing the optimisation variant for curves
Definition: algorithm.h:83
the algorithm is currently computing the decision variant for simple polygons
Definition: algorithm.h:79
virtual void collectCriticalValue(const accurate_float &x)
store a critical value. Duplicates are accepted but removed later.
Definition: optimise.cpp:20
bool canOptimisePoly() const
check if we can execute the optimisation variant on simple polygons (Buchin et al....
Definition: algorithm.h:249
Triangulation::Edge diagonalEdge(int i) const
a diagonal edge of the triangulation of P
Definition: algorithm.cpp:371
Triangulation & PTriangulation()
the triangulation of P
Definition: algorithm.h:265
virtual void calculateValidPlacements(double epsilon)=0
calculate all valid placements