Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
algorithm.cpp
Go to the documentation of this file.
1 
2 #include <algorithm.h>
3 #include <poly_utils.h>
4 #include <poly_path.h>
5 #include <algorithm>
6 #include <shortest_paths.h>
7 #include <structure.h>
8 #include <grid.h>
9 #include <iostream>
10 #include <app/concurrency.h>
11 #include <app/workerthread.h>
12 
13 using namespace frechet;
14 using namespace poly;
15 using namespace reach;
16 using namespace app;
17 
19  : P(new CurveData()),
20  Q(new CurveData()),
21  initial_status(NOT_SET_UP),
22  _status(NOT_SET_UP),
23  graphModel(),
24  _placements(),
25  _validPlacements(),
26  CRG_map(),
27  cancelFlag(nullptr),
28  local_fs(),
29  criticalValues()
30 { }
31 
33 {
34  delete P;
35  delete Q;
36 }
37 
39 {
40  return P->_c_diagonals;
41 }
42 
44  return c_diagonals().find(s) != c_diagonals().end();
45 }
46 
47 bool Algorithm::is_c_diagonal(int di, int dj) const {
48  return is_c_diagonal(Segment(di,dj));
49 }
50 
52  : curve(),
53  partition(),
54  _c_diagonals(),
55  _d_points(),
56  triangulation(), display_triangulation(nullptr),
57  utils(new PolygonUtilities()), reflex()
58 {}
60 {
61  delete utils;
62  delete display_triangulation;
63 }
64 
65 
67  frechet::Curve& aQ,
68  bool fixOrientation)
69 {
70  P->curve = aP;
71  Q->curve = aQ;
72 
73  /*
74  * Ein paar Voraussetzungen
75  * */
76 
77  if (P->curve.size() <= 1) return setInitialStatus(P_EMPTY);
78  if (Q->curve.size() <= 1) return setInitialStatus(Q_EMPTY);
79 
80  // (1) beide Kurven müssen geschlossen sein
81  if (!P->curve.isClosed()) return setInitialStatus(P_NOT_CLOSED);
82  if (!Q->curve.isClosed()) return setInitialStatus(Q_NOT_CLOSED);
83 
84  delete P->utils;
85  delete Q->utils;
86 
87  P->utils = new PolygonUtilities (P->curve);
88  Q->utils = new PolygonUtilities (Q->curve);
89 
90  // (2) beide Kurven müssen einfache Polygone sein
91  if (!P->utils->is_simple()) return setInitialStatus(P_NOT_SIMPLE);
92  if (!Q->utils->is_simple()) return setInitialStatus(Q_NOT_SIMPLE);
93 
94  // (3) Orientierung gegen den Uhrzeigersinn (lässt sich ggf. ändern)
95  if (!P->utils->is_counter_clockwise() && fixOrientation) {
96  std::reverse(aP.begin(),aP.end());
97  *P->utils = PolygonUtilities(P->curve = aP);
98  }
99  if (!Q->utils->is_counter_clockwise() && fixOrientation) {
100  std::reverse(aQ.begin(),aQ.end());
101  *Q->utils = PolygonUtilities(Q->curve = aQ);
102  }
103 
104  if (!P->utils->is_counter_clockwise())
106  if (!Q->utils->is_counter_clockwise())
108 
109  // (4) wenn ein Polygon konvex ist, können wir den
110  // vereinfachten Algorithmus für Kurven anwenden
111  if (P->utils->is_convex()) return setInitialStatus(P_CONVEX);
112  if (Q->utils->is_convex()) return setInitialStatus(Q_CONVEX);
113 
114  return setInitialStatus(SET_UP);
115 }
116 
117 
125 bool Algorithm::decompose(bool optimal)
126 {
127  // 1. in konvexe Teile zerlegen
128  Q_ASSERT(optimal==false);
131 
134 
135 
136  return (P->partitions() <= Q->partitions());
137 }
138 
140 {
141  std::swap(P,Q);
142 }
143 
145 {
146  // pre-calculate some stuff
148 
149  /* for P we need a triangulation of the simplified polygon
150  * (c- and t-diagonals, contracted edges)
151  * */
155 
157  int convex_parts = P->utils->simplify();
158  if (convex_parts > 0) {
160  }
161  else {
162  // degenerated triangulation consisting of just two vertexes
163  Q_ASSERT(P->_c_diagonals.size()==1);
164  int p1 = P->_c_diagonals.begin()->first;
165  int p2 = P->_c_diagonals.begin()->second;
166  P->triangulation.createVertex(P->curve[p1],p1);
167  P->triangulation.createVertex(P->curve[p2],p2);
168  }
170 #ifdef QT_DEBUG
171  // All triangulation points must be d-points
172  for(int i=0; i < P->triangulation.size(); ++i)
173  {
175  Q_ASSERT(P->triangulation[i]->dindex >= 0);
176  }
177  }
178 #endif
179 
180  /* for Q we need a complete triangulation */
183  /* Reflex vertices are used to find critical values.
184  * We allow some tolerance to find "almost" reflex vertices.
185  * Better have too many Critical Values than missing one !!
186  */
187  Q->utils->findReflexVertices(Q->reflex,1e-3);
188  // since Q is not convex, there must be reflex vertices
189  Q_ASSERT(Q->reflex.size() >= 1);
190 
191  delete P->utils;
192  P->utils = nullptr;
193 
194  delete Q->utils;
195  Q->utils = nullptr;
196 }
197 
199 {
200  result.clear();
201  for(const Polygon& p : partition)
202  {
203  // c-diagonals are [even-odd] entries
204  for(int i=0; i < p.size(); i += 2)
205  if (p[i] < p[i+1])
206  { // each diagonal appears exactly twice. we store it only once.
207  Segment seg(p[i],p[i+1]);
208  result.insert(seg);
209  Q_ASSERT(seg.is_diagonal(n()));
210  }
211  }
212  // no need to get rid of duplicates
213  //Q_ASSERT(removeDuplicates(result)==0);
214  return (int)result.size();
215 }
216 
218 {
219  std::set<int> set;
220 
221  // partitions contains all the c-diagonals
222  for(const Polygon& p : partition)
223  for(int v : p)
224  set.insert(v);
225 
226  _d_points.clear();
227  std::copy(set.begin(),set.end(), std::back_inserter(_d_points));
228 
229  for(int i=0; i < _d_points.size(); ++i) {
230  int di = _d_points[i];
231  Q_ASSERT(di >= 0 && di < n());
232  // reverse link Vertex to index into _d_points
233  triangulation[di]->dindex = i;
234  }
235  return (int) _d_points.size();
236 }
237 
239  FSPath::ptr path,
240  double,
241  bool update_status)
242 {
243  //Q_ASSERT(!update_status);
244  if (afs->n==0 || afs->m==0
246  if (update_status)
247  setStatus(NO);
248  return reach::Pointer();
249  }
250 
251  if (update_status) setStatus(RUNNING_DECIDE_CURVE);
252  this->fs = afs;
253 
254  int concurrency = ConcurrencyContext::countThreads();
255  frechet::reach::Structure rstruct(fs,concurrency,cancelFlag);
256  frechet::reach::Pointer startPointer = rstruct.calculate();
257  if (path)
258  updatePath(path,startPointer,NAN);
259 
260  this->fs.reset();
261  if (update_status)
262  setStatus(startPointer ? YES:NO);
263 
264  testCancelFlag();
265  return startPointer;
266 }
267 
275 void Algorithm::updatePath(reach::FSPath::ptr path, reach::Pointer startPointer, double epsilon)
276 {
277  if (startPointer) {
278  // find a feasible path
279  path->update(path->toPoint(startPointer),epsilon);
280  //Q_ASSERT(ok);
281  }
282  else {
283  path->clear();
284  }
285 }
286 
288  if (cancelFlag && *cancelFlag)
289  {
290  resetStatus();
291  throw InterruptedException();
292  }
293 }
294 
296 {
297  // Valid placement Graph for diagonal (di,dj)
298  GraphPtr valid = newGraph(graphModel);
299  valid->setOriginPlacement(di,dj);
300  valid->allocate(VERTICAL,VERTICAL);
301  // Note: CGraph stores only the vertical section. Horizontal is ignored.
302  _validPlacements.insert(std::make_pair(mapKey(di,dj), valid));
303  return valid;
304 }
305 
308  double epsilon, int di, int dj)
309 {
310  int i = P->triangulation[di]->dindex; // index into _d_points and placements. 0 <= i < l
311  int j = P->triangulation[dj]->dindex; // 0 <= j < l
312 
313  Q_ASSERT(i>=0);
314  Q_ASSERT(j>=0);
315 
316  GraphPtr valid = createValidPlacementGraph(di,dj);
317  //_validPlacements.find(mapKey(di,dj))->second;
318  Q_ASSERT(valid);
319 
320  Triangulation& sptri = spt.triangulation();
321  Q_ASSERT(sptri.assertEquals(Q->triangulation));
322 
323  int size_before1,size_before2;
324  size_before1 = sptri.size();
325 
326  sptri.addTargetVertices(_placements[j]);
327 
328  static const double PRECISION=1e-9;
329  auto wi = _placements[i].begin();
330  auto wiend = _placements[i].end();
331  for( ; wi!=wiend; ++wi)
332  {
333  QLineF dline (P->curve[di], P->curve [dj]);
334  // does wi coincide with on the the wj's ?
335  // (Guibas can't find it, if source==target)
336  auto wj = _placements[j].begin();
337  auto wjend = _placements[j].end();
338  for ( ; wj != wjend; ++wj)
339  if (wi->fs.intersects(wj->fs))
340  {
341  double w = (wi->fs & wj->fs).mid();
342  Point q = Grid::mapToPoint(Q->curve, w);
343  Q_ASSERT(numeric::euclidean_distance<double>(dline.p1(),q) <= epsilon+PRECISION);
344  Q_ASSERT(numeric::euclidean_distance<double>(dline.p2(),q) <= epsilon+PRECISION);
345 
346  valid->add_range(wi->gn,wj->gn);
347  //valid->add_valid_range(wi.gn,wj.gn);
349  || (PolygonShortestPathsFS::after_placement_added(&spt, &*wi, &*wj),true));
350  }
351 
352  testCancelFlag();
353 
354  // Berechne Shortest-Path-Tree + Free-Space
355  // Speichere die erreichbaren Kombinationen in validPlacements
356  size_before2 = sptri.size();
357 
358  Triangulation::Vertex_handle start = sptri.addVertex(wi->w);
359  spt.findShortestPaths(start, &*wi, dline, epsilon, valid);
360 
361  sptri.resize(size_before2);
362  }
363 
364  // release empty matrices
365  valid->finalize();
366 
367  sptri.resize(size_before1);
368  sptri.clearTargets();
369 }
370 
372 {
373  if (l() <= 2)
374  return Triangulation::Edge();
375 
376  int n = fs->n - 1;
377  int di = d(i) % n;
378  int di1 = d(i - 1) % n;
379  //Q_ASSERT(P->triangulation.countFaces()>0);
380  return P->triangulation.edge(di, di1);
381  //std::cout << e.first << " " << e.second << " " << e.first->vertex(e.second)->pindex << std::endl;
382 }
383 /*
384 int Algorithm::findFeasibleStart(GraphPtr G)
385 {
386  // Result G is confined to the HH segment (which is symmetrical)
387  // The solution is supposed to lie on the diagonal of G
388 // IndexRange r = G->hmask();
389 
390  // Note: conceptually, if the start point is at x, the end point must be at x+n,
391  // which is -through the design of G- at the same location.
392  G->searchDiagonalElement();
393  return G->foundDiagonalElement();
394 }
395 */
396 
397 
399 {
400  initial_status = st; // base status of the curve. does not change later.
401  return setStatus(st);
402 }
403 
405 {
406  Status old_stat = _status;
407  _status = st;
408  if (_status != old_stat)
409  emit statusChanged();
410  return _status;
411 }
412 
413 void Algorithm::resetStatus(bool was_interrupted) {
414  if (_status <= RUNNING && !was_interrupted) {
415  // exit from RUNNING status
416  // is only possibly after interruption
417  return;
418  }
419 
420  if (_status<=RUNNING || _status==YES || _status==NO)
421  {
422  // revert to initial state
423  Q_ASSERT(initial_status!=NOT_SET_UP);
425  cleanup();
426  }
427 }
428 
430  FSPath::ptr path, double epsilon,
431  bool update_status)
432 {
433  /* Precondition: free-space-diagram for epsilon computed
434  * */
435  switch(_status) {
436  case NOT_SET_UP:
437  default:
438  if (_status<=RUNNING)
439  { Q_ASSERT(!update_status); }
440  else
441  { Q_ASSERT(false); }
442  break;
443 
444  case P_EMPTY:
445  case Q_EMPTY:
446  case P_NOT_CLOSED:
447  case Q_NOT_CLOSED:
448  case P_NOT_SIMPLE:
449  case Q_NOT_SIMPLE:
452  //emit decidePolygonFinished();
453  return GraphPtr();
454 
455  case SET_UP:
456  case YES:
457  case NO:
458  /* expected */
459  break;
460 
461  case P_CONVEX:
462  case Q_CONVEX:
463  Q_ASSERT(false);
464  // call decideCurve() instead
465  break;
466  }
467 
468  cleanup();
469  if (update_status) setStatus(RUNNING_DECIDE_POLY);
470  //
471  this->fs = afs;
472 
473  graphModel.reset(new GraphModel());
474  graphModel->init(fs); // TODO parallel ??
475  if (graphModel->empty()) {
476  // Überhaupt keine erreichbaren Intervalle
477  if (update_status) setStatus(NO);
478  return GraphPtr();
479  }
480 
481  printDebugTimer("GraphModel");
482  if (update_status) {
483  std::cout << " Data: " << "matrix size (VV) = " << graphModel->count2(VERTICAL) << std::endl;
484  }
485 
486  /* Steps 7-11
487  * compute and store valid placements
488  */
489  calculateValidPlacements(epsilon);
490  printDebugTimer("Valid Placements");
491 
492  /* Decision algorithm
493  * Steps 1-2 are already done
494  * Step 3 - a new Free-Space diagram has just been calculated
495  */
496 
497  /* Steps 4-6
498  * RG vorberechnen (optional)
499  */
501  printTimer("RGraphs",update_status);
502 
503  // Populate the left part of the Reachability Structure
504  // The right part is identical.
505  testCancelFlag();
506 
507  /* Steps 12-16 */
508  GraphPtr result = findFeasiblePath();
509 
510  printDebugTimer("Main Loop");
511 
512  /* Update FSPath (if requested) */
513  if (path) {
514  // FSPath is very sensitive to round-off errors.
515  // Because it is only needed for visualisation, we can afford
516  // a bit of tolerance.
517  updatePath(path,result, round_up(epsilon,32));
518  }
519 
520  //FrechetViewApplication::instance()->popTimer("Decide Polygon");
521 
522  if (update_status)
523  setStatus( result ? YES:NO );
524 
525  if (path && update_status)
526  emit pathUpdated((bool)result); // only after status has changed
527 
528 #ifndef QT_DEBUG
529  // Debug mode: keep all the stuff for debug analysis
530  // Release mode: free unneeded memory.
531  // Note: that Result keeps a pointer to the solution graph, so it won't get lost.
532  cleanup();
533 #endif
534  return result;
535 }
536 
537 void Algorithm::updatePath(reach::FSPath::ptr path, GraphPtr result, double epsilon)
538 {
539  poly::PolygonFSPath* poly_path = dynamic_cast<poly::PolygonFSPath*> (path.get());
540  Q_ASSERT(poly_path);
541  if (result) {
542  poly_path->update(result, epsilon);
543  }
544  else {
545  poly_path->clear();
546  }
547 }
548 
549 
551  //Q_ASSERT(_status!=RUNNING);
552  // TODO clean up OpenCL pending jobs
553  _placements.resize(0);
554  _placements.resize(l());
555  _validPlacements.clear();
556  CRG_map.clear();
557 }
558 
572 double Algorithm::pickIntervalPoint(const Interval& j, int m)
573 {
574  // if possible, pick a vertex
575  int ci = (int)ceil(j.lower());
576  if (ci > j.upper()) {
577  // pick a non-integral point
578  return j.lower();
579  }
580  else if (ci == m) {
581  // border case: don't pick fs->m-1, could be confused with vertex 0
582  return max(j.lower(),m-1/1024.0);
583  }
584  else {
585  // pick integral point
586  return ci;
587  }
588 }
589 
591 {
592  std::list<Interval> ivals = fs->collectFreeVerticalIntervals(di);
593 
594  result.resize(ivals.size());
595  std::list<Interval>::iterator j = ivals.begin();
596 
597  for(int i=0; i < ivals.size(); ++i,++j)
598  {
599  Q_ASSERT(j->lower() >= 0);
600  Q_ASSERT(j->upper() >= j->lower());
601  Q_ASSERT(j->upper() <= fs->m);
602 
603  Placement& p = result[i];
604  p.fs = *j;
605  p.w = pickIntervalPoint(*j,fs->m-1);
606  Q_ASSERT(j->contains(p.w));
607  Q_ASSERT(p.w!=(fs->m-1));
608 
609  // map to GraphModel
610  p.gn = graphModel->map(VERTICAL,p.fs,true);
611  }
612 }
613 
614 int Algorithm::mapKey(int di, int dj)
615 {
616  return dj * P->n() + di;
617 }
618 
619 
621 {
622  int h = mapKey(di,dj);
623  auto p = _validPlacements.find(h);
624  Q_ASSERT(p != _validPlacements.end());
625  return p->second;
626  }
627 
628 
630 {
631  // calculate a reachability structure for column [i..j] (mod n)
632  int n = fs->n-1;
633  int di = d(i) % n;
634  int dj1 = d(i+1) % n;
635  int dj2 = (dj1 >= di) ? dj1 : (dj1+n);
636  // TODO right ?
637 
638  // j is exclusive
640  str.calculateColumns( di, dj2 );
641  // Turn into a Graph
642  //std::cout << "RG("<<i<<","<<(i+1)<<")" <<std::endl;
643 
644  // Graph Model boundaries
645  //int hcount1 = graphModel->count1(HORIZONTAL);
646  int h0 = graphModel->map_lower(HORIZONTAL,di);
647  int h1 = graphModel->map_lower(HORIZONTAL,dj1);
648  int h2 = graphModel->map_lower(HORIZONTAL,dj2);
649  int h3 = graphModel->lowerShiftedHorizontally(h1);
650 
651  Q_ASSERT((h1==h2) || (h2==h3));
652 
653  double s0 = str.bottom().first()->lower();
654  double s1 = str.bottom().last()->upper();
655 
656  int H0 = graphModel->map_lower(HORIZONTAL,s0);
657  int H2 = graphModel->map_lower(HORIZONTAL,s1);
658 
659  Q_ASSERT(h2==H2);
660 
661  GraphPtr result = newGraph(graphModel, str);
662 
663  Q_ASSERT(result->hmask().lower==H0);
664  Q_ASSERT(result->hmask().upper==H2);
665 
666  result->setOriginRG(i % l());
667  result->finalize();
668  return result;
669 }
670 
671 
672 std::ostream& frechet::poly::operator<< (std::ostream& out, const Segment& seg)
673 {
674  return out << "["<<seg.first<<".."<<seg.second<<"]";
675 }
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
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
void swap(gpuword **A, gpuword **B)
void setPolygonSize(int n)
set number of polygon vertexes
frechet::reach::Graph::ptr GraphPtr
the result of the decision algorithm is a reachability Graph containing a feasible path
Definition: algorithm.h:116
Edge edge(int i, int j) const
construct an edge from two vertexes
initial status: the algorithm is not yet ready to execute
Definition: algorithm.h:90
double round_up(double x, int ulps=1)
rounding function with 'units in the last place' Roughly speaking, a ulp is the smallest representabl...
Definition: numeric.h:112
time_point printTimer(std::string label, bool do_print=true)
clock benchmark
std::vector< frechet::reach::Placement > Placements
a list of Placement objects
Definition: graph_model.h:144
~CurveData()
destructor; release all memory
Definition: algorithm.cpp:59
void testCancelFlag()
poll cancelFlag
Definition: algorithm.cpp:287
int decompose(DecompositionAlgorithm algo, bool verify)
compute a convex decomposition of the polygon. Store results in the member variable 'convex'.
Definition: poly_utils.cpp:58
stores essential information about an input curve. This data is processed once for each input curve.
Definition: algorithm.h:132
static Point mapToPoint(const Curve &C, double x)
given a polygonal curve and an offset, compute the point on the curve
Definition: grid.cpp:130
int partition(Partition &partition) const
compute a list of sub-polygons, one for each convex part. This is mainly copying data to a more conve...
Definition: poly_utils.cpp:107
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
model the mapping of free-space intervals to nodes in a frechet::reach::Graph.
Definition: graph_boost.h:109
negative result of the decision version
Definition: algorithm.h:87
void findReflexVertices(Polygon &poly, double tolerance=0.0)
find all reflex (concave) vertices.
Definition: poly_utils.cpp:279
Triangulation triangulation
simplified triangulation for P, complete triangulation for Q
Definition: algorithm.h:142
global definitions for all algorithms.
std::set< Segment > Segments
a set of Segment objects
Definition: types.h:115
input data are faulty. P is convex.
Definition: algorithm.h:110
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
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
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
the algorithm is currently computing (decision variant, or optimisation variant)
Definition: algorithm.h:77
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
input data are faulty. P is not a simple polygon.
Definition: algorithm.h:102
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
Hertel and Mehlhorn's approximation algorithm.
Definition: poly_utils.h:134
void swap()
swap input curves. The algorithm by Buchin et al. chooses the smalled convex decompositioin as P.
Definition: algorithm.cpp:139
void clearTargets()
clear targets for shortest-path tree search
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
Definition: boundary.h:285
bool decompose(bool optimal)
decompose polygons into convex parts
Definition: algorithm.cpp:125
Vertex_handle createVertex(const Point &p, int i)
create a new triangulation vertex
void resize(int sz)
reset number of vertexes in triangulation
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
int simplify()
Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges....
Definition: poly_utils.cpp:163
Vertex_handle addVertex(double w)
add a triangulation vertex on the edge of the polygon (does not correspond to a polygon vertex)
double upper() const
Definition: interval.h:96
time_point printDebugTimer(std::string label)
clock benchmark and print elapsed time
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 & triangulation() const
BoundarySegment * Pointer
(dumb) pointer to a BoundarySegment object
Definition: boundary.h:55
GraphPtr newGraph(const GraphModel::ptr model)
Definition: graph_cl.cpp:12
void findShortestPaths(Vertex_handle start_point, const frechet::reach::Placement *asource, QLineF d, double epsilon, frechet::reach::Graph::ptr validPlacements)
void addTargetVertices(const frechet::reach::Placements &p)
add vertexes for computing valid placements
static assert_hook2 after_placement_added
unit test and debugging hook function; called when a valid placement is updated
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
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
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
bool is_diagonal(int n) const
Definition: types.h:69
int calculate_d_points()
calculate the d-points (end points of the diagonals)
Definition: algorithm.cpp:217
double lower() const
Definition: interval.h:92
void calculatePlacements(int i, frechet::reach::Placements &result)
calculate free-space placements
Definition: algorithm.cpp:590
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
Pointer calculate()
compute the reachability structure from the underlying free-space diagram. Uses a divide-and-conquere...
Definition: structure.cpp:130
Segments _c_diagonals
a list of c-diagonals
Definition: algorithm.h:138
bool assertEquals(const Triangulation &that) const
equality assertion for debugging
void fanTriangulate(Triangulation &tri) const
compute a fan-triangulation from a list of convex parts. Each convex sub-polygon is triangulated usin...
Definition: poly_utils.cpp:254
PolygonUtilities * utils
helper class for polygon analysis
Definition: algorithm.h:148
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
int l() const
number of diagonal end points
Definition: algorithm.h:413
#define str(S)
placement of a diagonal point in free-space diagram When calculating valid placements in [buchin06]
Definition: graph_model.h:132
input data are faulty. Q is an empty curve.
Definition: algorithm.h:96
Polygon reflex
reflex vertices (for Q only)
Definition: algorithm.h:146
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
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
The Reachability Structure; maintains a list of intervals on the border of Free Space,...
Definition: structure.h:32
Interval fs
Free-Space Interval.
Definition: graph_model.h:135
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....
a feasible-path for simple polygons.
Definition: poly_path.h:24
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
a helper class for polygon analysis.
Definition: poly_utils.h:121
an interval of two double values.
Definition: interval.h:31
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 decision variant for simple polygons
Definition: algorithm.h:79
virtual void clear()
Definition: fs_path.cpp:222
std::ostream & operator<<(std::ostream &out, const frechet::poly::CgalPolygon &poly)
print operator (for debugging)
Definition: poly_utils.cpp:338
double max(double a, double b)
maximum function with checks for NAN
Definition: numeric.h:233
Triangulation::Edge diagonalEdge(int i) const
a diagonal edge of the triangulation of P
Definition: algorithm.cpp:371
void update(const Graph::ptr result, double epsilon)
compute a feasible path from the results of the simple polygon algorithm
Definition: poly_path.cpp:17
virtual void calculateValidPlacements(double epsilon)=0
calculate all valid placements