Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
parallel.cpp
Go to the documentation of this file.
1 
2 #include <parallel.h>
3 #include <concurrency.h>
4 
5 using namespace frechet;
6 using namespace poly;
7 using namespace reach;
8 using namespace app;
9 
10 // Algorithm factory
12 {
13  if (topo)
15  else if (ConcurrencyContext::countThreads() <= 1)
17  else
19 }
20 
22 : Algorithm()
23 { }
24 
28 
31  c_diagonals_vector()
32 {
33  auto copyspt = [&] () {
34  return new PolygonShortestPathsFS(*qtri.local());
35  };
36  spt = LocalSPT(copyspt);
37 }
38 
39 
41 {
42  clear_qtri();
43  localCriticalValues.clear();
44  c_diagonals_vector.clear();
45 }
46 
48 {
49  for (LocalTriangulation::iterator i = qtri.begin(); i != qtri.end(); ++i)
50  {
51  Triangulation* copy = *i;
52  Q_ASSERT(copy != &Q->triangulation); // DO NOT delete the original
53  delete copy;
54  }
55  for (LocalSPT::iterator i = spt.begin(); i != spt.end(); ++i)
56  {
57  PolygonShortestPathsFS* psf = *i;
58  delete psf;
59  }
60  qtri.clear();
61 }
62 
64 {
66 
67  // local copies for Q->triangulation
68  clear_qtri();
70  return new Triangulation(Q->triangulation);
71  });
72 
73  // vector of c-diagonals
74  c_diagonals_vector.clear();
75  c_diagonals_vector.reserve(c_diagonals().size());
76  std::copy(c_diagonals().begin(), c_diagonals().end(),
77  std::back_inserter(c_diagonals_vector));
78 }
79 
80 
81 //
82 // Calculate Reachability Graphs
83 //
85 {
86 // std::cout << "working in thread " << ConcurrencyContext::instance.currentThread() << std::endl;
87  for(int i=0; i < l(); ++i) {
88  testCancelFlag(); // throws InterruptedException
89  CRG(i, i+1);
90  }
91  Q_ASSERT(assertReachabilityGraphs());
92 }
93 
99 {
100  auto lambda = [&](size_t i) {
101  CRG(i, i+1);
102  testCancelFlag(); // throws InterruptedException
103  };
104 
105  tbb::static_partitioner sp;
106  tbb::parallel_for((size_t)0, (size_t)l(), lambda, sp);
107  Q_ASSERT(assertReachabilityGraphs());
108  //printHistogram();
109 }
110 
112 {
113  for(int i=0; i < l(); ++i)
114  {
116  GraphPtr rg1 = CRG(i-1,i,e);
117  GraphPtr rg2 = CRG(i,i+1,e);
118  GraphPtr rg3 = CRG(i+1,i+2,e);
119  Q_ASSERT(Graph::is_adjacent_to(*rg1,*rg2));
120  Q_ASSERT(Graph::is_adjacent_to(*rg2,*rg3));
121  }
122  return true;
123 }
124 
125 
127 {
128  // validPlacements contains only VERTICAL-VERTICAL edges.
129  // No horizontal edges.
130  _validPlacements.clear();
131 
132  // (1) finde die zu di und dj gehörigen freien Intervalle (aus dem Free-Space)
133  // (2) wähle aus jedem Intervall einen beliebigen Punkt: w1,...,wm
134  // wenn möglich, wählen wir Eckpunkte aus, sonst den kleinsten Punkt im Intervall
135  _placements.resize(l());
136  for(int i=0; i < l(); ++i)
138 
139  Triangulation& qtri = Q->triangulation;
140  PolygonShortestPathsFS spt(qtri);
141 
142  /* Steps 7-11 */
143  for(const Segment& d : c_diagonals()) // parallel
144  {
145  // for all placements in the free space
146  int di = d.first;
147  int dj = d.second;
148 
149  // TODO calculate in one go, using mirrored R intervals ?!
150  Algorithm::calculateValidPlacements(spt, epsilon, di, dj);
151  Algorithm::calculateValidPlacements(spt, epsilon, dj, di);
152  }
153 }
154 
156 {
157  // validPlacements contains only VERTICAL-VERTICAL edges.
158  // No horizontal edges.
159  _validPlacements.clear();
160 
161  // (1) finde die zu di und dj gehörigen freien Intervalle (aus dem Free-Space)
162  // (2) wähle aus jedem Intervall einen beliebigen Punkt: w1,...,wm
163  // wenn möglich, wählen wir Eckpunkte aus, sonst den kleinsten Punkt im Intervall
164  _placements.resize(l());
165 
166  //for(int i=0; i < l(); ++i)
167  tbb::affinity_partitioner ap;
168  auto lambda1 = [&] (size_t i) {
170  };
171  tbb::parallel_for(0,l(),lambda1, ap);
172 
173  /* Steps 7-11 */
174 
175  auto lambda2 = [&] (size_t i) {
176  const Segment& d = c_diagonals_vector[i];
177  int di = d.first;
178  int dj = d.second;
179 
180  PolygonShortestPathsFS* local_spt = spt.local();
181 
182  // in multi-threading mode, each thread holds a separate copy of Q->triangulation
183 /* std::cout << "calculateValidPlacements "
184  << " thread " << ConcurrencyContext::instance.currentThread()
185  << " spt = " << &local_spt
186  << " tri = " << std::hex << &local_spt.triangulation()
187  << std::endl;
188 */
189 #ifdef QT_DEBUG
190  Triangulation& local_qtri = local_spt->triangulation();
191  Q_ASSERT(&local_qtri != &Q->triangulation);
192  Q_ASSERT(&local_qtri == this->qtri.local());
193  Q_ASSERT(local_qtri.assertEquals(Q->triangulation));
194 #endif
195 
196  Algorithm::calculateValidPlacements(*local_spt, epsilon, di, dj);
197  Algorithm::calculateValidPlacements(*local_spt, epsilon, dj, di);
198  };
199 
200  tbb::parallel_for( (size_t)0, (size_t)c_diagonals_vector.size(), lambda2, ap);
201 }
202 
203 
204 //
205 // The Main Loop
206 //
207 
209 {
210  i = (i+l()) % l();
211  j = (j+l()) % l();
212 
213  int h = mapKey(i,j);
214  auto p = CRG_map.find(h);
215  if (p!=CRG_map.end()) {
216  return p->second;
217  }
218  else {
219  Graph::ptr g = create_CRG(i,j,e);
220  CRG_map.insert(std::make_pair(h,g));
221  return g;
222  }
223 }
224 
226 {
227  Graph::ptr result;
228 
229 #ifdef QT_DEBUG
230  // i,j are supposed to be incident to e
231  if (e.first != Triangulation::Face_handle()) {
233  if (v2.first->dindex == j)
234  std::swap(v2.first, v2.second);
235  Q_ASSERT(v2.first->dindex == i);
236  Q_ASSERT(v2.second->dindex == j);
237  Q_ASSERT(v2.first->pindex == d(i));
238  Q_ASSERT(v2.second->pindex == d(j));
239  }
240  else if (e!=Triangulation::Edge()) {
241  // degenerated triangulation
242  Q_ASSERT(l()==2);
243  Q_ASSERT(i==0 && j==1 || i==1 && j==0);
244  }
245 #endif
246 
247  if ((i+1)%l() == j%l()) {
248  // RG(i,i+1)
249  Q_ASSERT(l()==2 || (e==Triangulation::Edge()) || Triangulation::is_polygon_edge(e));
250  result = create_RG(i);
251  }
252  else {
253  Q_ASSERT(Triangulation::is_inner_face(e.first));
254 
255  // where (d_i,d_h,d_j) is a triangle in T_C'
257 
258  //std::cout << e << " " << e2.first << " " << e2.second << std::endl;
259 
260  Q_ASSERT( e2.first != e );
261  Q_ASSERT( e2.second != e );
262  //Q_ASSERT( P->triangulation.is_ccw_face(e2.first.first));
263  //Q_ASSERT( P->triangulation.is_ccw_face(e2.second.first));
264  Q_ASSERT(! P->triangulation.is_outer_edge(e2.first));
265  Q_ASSERT(! P->triangulation.is_outer_edge(e2.second));
266 
267  Triangulation::Vertex_handle vh = e.first->vertex(e.second);
268  Q_ASSERT(!Triangulation::is_south_pole(vh));
269 
270  Q_ASSERT(e2.first.first==e2.second.first); // same Face
271  Q_ASSERT(e2.first.first->has_vertex(vh));
272  Q_ASSERT(e2.second.first->has_vertex(vh));
273 
274  int h = vh->dindex;
275  Q_ASSERT(h >= 0);
276  Q_ASSERT(d(h)==vh->pindex);
277 
278  // pick h so to avoid infinite recursion !
279 
280  P->triangulation.mirror(e2.first);
281  Q_ASSERT(! P->triangulation.is_outer_edge(e2.first));
282 
283  //std::cout << e.first << std::endl;
284  //std::cout << e2.second.first->neighbor(e2.second.second) << std::endl;
285  P->triangulation.mirror(e2.second);
286  Q_ASSERT(! P->triangulation.is_outer_edge(e2.second));
287 
288  //std::cout << "MERGE( CRG("<<i<<","<<h<<"), CRG("<<h<<","<<j<<"))" << std::endl;
289  result = MERGE_inner( CRG(i,h,e2.first), CRG(h,j,e2.second) );
290  }
291 
292  int di = d(i);
293  int dj = d(j);
294  if (is_c_diagonal(di,dj))
295  COMBINE(result, di,dj);
296 
297  return result;
298 }
299 
300 
302 {
303  return Algorithm::calculate_RG(i);
304 }
305 
306 
312 {
313  //std::cout << "MERGE("<<A->origin.i<<","<<B->origin.i<<")" << std::endl;
314  testCancelFlag();
315 
316  GraphPtr C = A->merge2(B.get());
317  C->setOriginMerge2(A,B);
318  return C;
319 }
320 
321 
323 {
324  // return A_HV * B_VV * A_VH
325  GraphPtr C = A->merge3(B.get());
326  C->setOriginMerge3(A,B);
327  return C;
328 
329 }
330 
331 
337 void AlgorithmSingleCore::COMBINE(GraphPtr A, int di, int dj)
338 {
339  // apply only to the VERTICAL-VERTICAL part of the matrix.
340  GraphPtr P = getValidPlacements(di,dj);
341  A->combine(P.get());
342  A->setOriginCombine(P);
343 }
344 
345 
347 {
353  //FrechetViewApplication::instance()->pushTimer();
354 
355  Q_ASSERT(l() >= 2);
356  for(int i=0; i < l(); ++i) // parallel
357  {
358  testCancelFlag();
359 
361 
362  // G = MERGE( RG(i-1,i), CRG(i,i-1,true), RG(i-1,i) );
363  GraphPtr rg = CRG(i-1, i);
364  GraphPtr G = MERGE_outer(rg, CRG(i, i-1, e));
365  // returns only the HH part of G
366 
367  // Query G for a feasible path starting in [d_(i-1),d_i)
368  // (and ending in [d_(i-1) +n, d_i +n))
369  Q_ASSERT(G->hmask() == rg->hmask());
370 
371  if (isSolution(G))
372  return G;
373  }
374 
375  //FrechetViewApplication::instance()->popTimer("Main Loop");
376 
377  return Graph::ptr();
378 }
379 
381 {
382  // Note: search/foundDiagonalElement is decouopled for other implementations
383  // the default implementation returns a result immediately
384  G->queryDiagonalElement();
385  return (G->foundDiagonalElement() >= 0);
386 }
387 
388 
391  topo(), roots(), pool()
392 { }
393 
395 { }
396 
398  // calculate, enqueue - and insert into topo list
400  // do not COMBINE
401  Q_ASSERT(RG->origin.blevel == 0);
402  addTopoSort(RG);
403  return RG;
404 }
405 
407  // DON'T calculate - just insert into topo list
408  Graph::ptr C = newGraph(graphModel, graphModel->mergedHMask(A->hmask(),B->hmask()));
409  C->setOriginMerge2(A, B);
410  addTopoSort(C);
411  return C;
412 }
413 
415  // DON'T calculate - just insert into topo list
416  GraphPtr C = newGraph(A->graphModel(), A->hmask());
417  C->setOriginMerge3(A, B);
418  addTopoSort(C);
419  roots.push_back(C);
420  return C;
421 }
422 
424  // DON'T calculate - just update origin
425  GraphPtr P = getValidPlacements(di, dj);
426  A->setOriginCombine(P);
427  P->origin.succesors++;
428 }
429 
431  // Solutions are evaluated later
432  return false;
433 }
434 
436  // don't calculate - just insert Graphs into topo list
438 
439  // next: calculate from bottom upwards
440  for (int blevel=0; blevel < topo.size(); ++blevel)
441  {
442  // calculate one level
443  for (Graph::ptr G : topo[blevel]) {
444  calculate(G);
445  }
446 
447  barrier(false); // before re-using matrix buffers
448 
449  for (Graph::ptr G : topo[blevel]) {
450  G->resetConditions();
451  // after a barrier, all conditions are met (we need not track them)
453  }
454  }
455  // collect resuts from roots
456  barrier(true);
457  for(Graph::ptr G : roots)
458  if (G->foundDiagonalElement() >= 0)
459  return G;
460  return Graph::ptr();
461 }
462 
464 {
465  Graph* A = G->origin.A.get();
466  Graph* B = G->origin.B.get();
467  Graph* P = G->origin.P.get();
468 
469  switch (G->origin.operation) {
470  case Graph::Origin::RG:
471  Q_ASSERT(!A && !B);
472  break;
473  case Graph::Origin::MERGE2:
474  Q_ASSERT(A && B);
475  G->merge2(A,B, &pool);
476  break;
477 
478  case Graph::Origin::MERGE3:
479  Q_ASSERT(A && B);
480  Q_ASSERT(!P);
481  G->merge3(A,B, &pool);
482  G->queryDiagonalElement();
483  break;
484  }
485 
486  if (P)
487  G->combine(P);
488 }
489 
491 {
492  Graph* A = G->origin.A.get();
493  Graph* B = G->origin.B.get();
494  Graph* P = G->origin.P.get();
495 
496  if (A && (--A->origin.succesors==0)) // count dependencies on A_VV
497  reclaim(A);
498  if (B && (--B->origin.succesors==0)) // count dependencies on B_VV
499  reclaim(B);
500  if (P && (--P->origin.succesors==0))
501  reclaim(P);
502 }
503 
505 {
506  // reclaim matrix data (will be used for upper levels)
509  // Note: G_HH may be used for finding a solution
510  // but the solution will be found before the next barrier()
511 }
512 
514 {
516  topo.clear();
517  roots.clear();
518  pool.clear();
519 }
520 
522  if (topo.size() <= G->origin.blevel)
523  topo.resize(G->origin.blevel+1);
524  topo[G->origin.blevel].push_back(G);
525 }
526 
527 void AlgorithmTopoSort::barrier(bool finish) {
528  if (ConcurrencyContext::hasGpuSupport())
529  {
530  if (finish)
531  clFinish(ConcurrencyContext::clQueue());
532  else
533  clEnqueueBarrier(ConcurrencyContext::clQueue());
534  }
535 }
536 
537 
Represents a polygon line segment from node i to j.
Definition: types.h:39
int mapKey(int di, int dj)
hash key for memo-ized maps
Definition: algorithm.cpp:614
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
virtual bool isSolution(GraphPtr G)
Definition: parallel.cpp:380
void swap(gpuword **A, gpuword **B)
frechet::reach::Graph::ptr GraphPtr
the result of the decision algorithm is a reachability Graph containing a feasible path
Definition: algorithm.h:116
AlgorithmTopoSort()
default constructor
Definition: parallel.cpp:389
Multi-Core implementaion. Uses Intel TBB to perform some parallel computation.
Definition: parallel.h:88
std::pair< Vertex_handle, Vertex_handle > VertexPair
a pair of vertexes
void testCancelFlag()
poll cancelFlag
Definition: algorithm.cpp:287
void calculate(Graph::ptr G)
finally compute the contents of a CGR
Definition: parallel.cpp:463
tbb::combinable< CriticalValueList > LocalCriticalValueList
Definition: parallel.h:96
void barrier(bool finish)
put up a memory barrier between each level of the call graph (necessary for OpenCL implementation)
Definition: parallel.cpp:527
tbb::enumerable_thread_specific< PolygonShortestPathsFS * > LocalSPT
Definition: parallel.h:100
virtual reach::Graph::ptr create_RG(int i) override
re-implements base method; instead of calculating the Graph, we just put a placeholder into the memoi...
Definition: parallel.cpp:397
Triangulation triangulation
simplified triangulation for P, complete triangulation for Q
Definition: algorithm.h:142
virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr A, const reach::Graph::ptr B) override
re-implements base method; instead of calculating the result, we just put a placeholder into the memo...
Definition: parallel.cpp:406
global definitions for all algorithms.
virtual void calculateValidPlacements(double epsilon) override
calculate all valid placements
Definition: parallel.cpp:126
void mirror(Edge &e) const
flip the direction of an edge. Keep in mind that Edge object are desribed as a Face + opposite vertex...
Sequential implementation for a single processor core.
Definition: parallel.h:24
AlgorithmMultiCore()
default constructor
Definition: parallel.cpp:29
Algorithm::ptr newPolyAlgorithm(bool topo)
factory method for creating a new algorithm object. Choose the appropriate implementation based on av...
Definition: parallel.cpp:11
virtual void cleanup() override
release all memory
Definition: parallel.cpp:513
virtual ~AlgorithmMultiCore()
destructor
Definition: parallel.cpp:40
bool is_c_diagonal(int di, int dj) const
check, whether a diagonal is a c-diagonal
Definition: algorithm.cpp:47
virtual void COMBINE(reach::Graph::ptr A, int di, int dj)
Definition: parallel.cpp:337
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
virtual GraphPtr findFeasiblePath() override
re-implements the main loop of the decision variant; traverse the call-graph bottom-up and compute th...
Definition: parallel.cpp:435
reach::GraphModel::ptr graphModel
map free-space interval to nodes of the reachability graph
Definition: algorithm.h:195
static bool is_inner_face(Face_handle f)
EdgePair adjacentEdges(Edge e) const
TDS::Face_handle Face_handle
handle to a triangulation face (handles are managed by TDS base class)
boost::shared_ptr< Algorithm > ptr
(smart) pointer to an Algorithm object
Definition: algorithm.h:236
void clear_qtri()
release thread-local variables
Definition: parallel.cpp:47
virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr A, const reach::Graph::ptr B)
Definition: parallel.cpp:311
virtual GraphPtr findFeasiblePath() override
the main loop of Buchin et al's decision algorithm.
Definition: parallel.cpp:346
virtual void cleanup()
release memory (meoisation maps, etc.)
Definition: algorithm.cpp:550
static bool is_polygon_edge(Edge e)
virtual void calculateValidPlacements(double epsilon) override
calculate all valid placements
Definition: parallel.cpp:155
Guibas' Algorithm with additional Free-Space computation.
struct frechet::poly::Algorithm::CurveData * Q
implementation with a sorted call-graph.
Definition: parallel.h:167
virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e)
compute a Combined Reachabilty Graph.
Definition: parallel.cpp:225
virtual reach::Graph::ptr create_RG(int i)
compute an initial Reachabilty Graph.
Definition: parallel.cpp:301
virtual reach::Graph::ptr CRG(int i, int j, Triangulation::Edge e=Triangulation::Edge())
get a memoised Combined Reachabilty Graph. This is one of the steps in Buchin et al....
Definition: parallel.cpp:208
virtual void calculateReachabilityGraphs() override
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map
Definition: parallel.cpp:84
base class for algorithm for simple polygons.
Definition: algorithm.h:51
virtual ~AlgorithmTopoSort()
destructor release all memory
Definition: parallel.cpp:394
GraphList roots
roots of the call graph: this is where the results of the algorithm pop up
Definition: parallel.h:176
static LocalSPT spt
thread-local copies for PolygonShortestPathsFS
Definition: parallel.h:102
const Segments & c_diagonals() const
the c-diagonals
Definition: algorithm.cpp:38
Triangulation & triangulation() const
void clear()
release all resources
Definition: matrix_pool.cpp:94
void reclaimPredecessors(Graph::ptr G)
release CGRs that are not needed anymore
Definition: parallel.cpp:490
virtual void COMBINE(reach::Graph::ptr A, int di, int dj) override
re-implements base method; instead of calculating the result, we just put a placeholder into the memo...
Definition: parallel.cpp:423
virtual void triangulate() override
re-implements base class method; stores thread-local copies of Q's triangulation
Definition: parallel.cpp:63
GraphPtr newGraph(const GraphModel::ptr model)
Definition: graph_cl.cpp:12
std::vector< Segment > c_diagonals_vector
vector of c-diagonals
Definition: parallel.h:94
virtual void release()
release memory for all parts of the adjacancy matrix
Definition: graph_m4ri.cpp:203
int d(int i) const
map a diagonal end-point to a vertex in P
Definition: algorithm.h:419
virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr A, const reach::Graph::ptr B)
perform the final MERGE operation on two Reachability Graphs
Definition: parallel.cpp:322
struct frechet::poly::Algorithm::CurveData * P
static bool is_south_pole(Vertex_handle v)
virtual bool isSolution(GraphPtr G) override
Definition: parallel.cpp:430
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
PlacementMap _validPlacements
map of valid placements (as adjacency matrices, for each c-diagonal)
Definition: algorithm.h:192
std::pair< Edge, Edge > EdgePair
a pair of edges
MatrixPool pool
recycling pool of matrices
Definition: parallel.h:178
virtual void calculateReachabilityGraphs() override
Definition: parallel.cpp:98
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
GraphMap CRG_map
a map of memo-ized Combined Reachability Graphs
Definition: algorithm.h:201
bool assertEquals(const Triangulation &that) const
equality assertion for debugging
Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure,...
Definition: graph_boost.h:39
PlacementVector _placements
list of placements (for each end point of diagonals)
Definition: algorithm.h:190
bool assertReachabilityGraphs()
debug assertion; check if the CRGs are correctyl aligned
Definition: parallel.cpp:111
int l() const
number of diagonal end points
Definition: algorithm.h:413
static LocalTriangulation qtri
thread-local copies of Q->triangulation
Definition: parallel.h:92
tbb::enumerable_thread_specific< Triangulation * > LocalTriangulation
Definition: parallel.h:90
VertexPair incidentVertexes(Edge e) const
struct frechet::reach::Graph::Origin origin
static LocalCriticalValueList localCriticalValues
thread-local copies of critical values
Definition: parallel.h:98
Graph::ptr A
if this graph was constructed as transitive closure: original graphs this = MERGE(A,...
Definition: graph_m4ri.h:106
virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr A, const reach::Graph::ptr B) override
re-implements base method; instead of calculating the result, we just put a placeholder into the memo...
Definition: parallel.cpp:414
void addTopoSort(Graph::ptr G)
insert a CGR into the topologically sorted list of calls
Definition: parallel.cpp:521
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
int succesors
number of successors
Definition: graph_m4ri.h:99
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
void reclaim(Graph *G)
reclaim graph memory
Definition: parallel.cpp:504
static bool is_outer_edge(Edge e)
TopoSort topo
sorted call graph
Definition: parallel.h:174
static bool is_adjacent_to(const Graph &A, const Graph &B)
Definition: graph_m4ri.cpp:775
Triangulation::Edge diagonalEdge(int i) const
a diagonal edge of the triangulation of P
Definition: algorithm.cpp:371
virtual void calculateValidPlacements(double epsilon)=0
calculate all valid placements