15 else if (ConcurrencyContext::countThreads() <= 1)
33 auto copyspt = [&] () {
49 for (LocalTriangulation::iterator i =
qtri.begin(); i !=
qtri.end(); ++i)
55 for (LocalSPT::iterator i =
spt.begin(); i !=
spt.end(); ++i)
87 for(
int i=0; i <
l(); ++i) {
100 auto lambda = [&](
size_t i) {
105 tbb::static_partitioner sp;
106 tbb::parallel_for((
size_t)0, (
size_t)
l(), lambda, sp);
113 for(
int i=0; i <
l(); ++i)
136 for(
int i=0; i <
l(); ++i)
167 tbb::affinity_partitioner ap;
168 auto lambda1 = [&] (
size_t i) {
171 tbb::parallel_for(0,
l(),lambda1, ap);
175 auto lambda2 = [&] (
size_t i) {
192 Q_ASSERT(&local_qtri == this->
qtri.local());
220 CRG_map.insert(std::make_pair(h,g));
233 if (v2.first->dindex == j)
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));
243 Q_ASSERT(i==0 && j==1 || i==1 && j==0);
247 if ((i+1)%
l() == j%
l()) {
260 Q_ASSERT( e2.first != e );
261 Q_ASSERT( e2.second != e );
270 Q_ASSERT(e2.first.first==e2.second.first);
271 Q_ASSERT(e2.first.first->has_vertex(vh));
272 Q_ASSERT(e2.second.first->has_vertex(vh));
276 Q_ASSERT(
d(h)==vh->pindex);
317 C->setOriginMerge2(A,B);
326 C->setOriginMerge3(A,B);
342 A->setOriginCombine(
P);
356 for(
int i=0; i <
l(); ++i)
369 Q_ASSERT(G->hmask() == rg->hmask());
384 G->queryDiagonalElement();
385 return (G->foundDiagonalElement() >= 0);
391 topo(), roots(), pool()
401 Q_ASSERT(RG->origin.blevel == 0);
409 C->setOriginMerge2(A, B);
417 C->setOriginMerge3(A, B);
426 A->setOriginCombine(
P);
427 P->origin.succesors++;
440 for (
int blevel=0; blevel <
topo.size(); ++blevel)
450 G->resetConditions();
458 if (G->foundDiagonalElement() >= 0)
467 Graph*
P = G->origin.P.get();
469 switch (G->origin.operation) {
470 case Graph::Origin::RG:
473 case Graph::Origin::MERGE2:
475 G->merge2(A,B, &
pool);
478 case Graph::Origin::MERGE3:
481 G->merge3(A,B, &
pool);
482 G->queryDiagonalElement();
494 Graph*
P = G->origin.P.get();
500 if (
P && (--
P->origin.succesors==0))
522 if (
topo.size() <= G->origin.blevel)
523 topo.resize(G->origin.blevel+1);
524 topo[G->origin.blevel].push_back(G);
528 if (ConcurrencyContext::hasGpuSupport())
531 clFinish(ConcurrencyContext::clQueue());
533 clEnqueueBarrier(ConcurrencyContext::clQueue());
Represents a polygon line segment from node i to j.
int mapKey(int di, int dj)
hash key for memo-ized maps
GraphPtr getValidPlacements(int di, int dj)
get valid placements for a given pair of diagonal end points; compute them, if necssary....
virtual bool isSolution(GraphPtr G)
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
AlgorithmTopoSort()
default constructor
Multi-Core implementaion. Uses Intel TBB to perform some parallel computation.
std::pair< Vertex_handle, Vertex_handle > VertexPair
a pair of vertexes
void testCancelFlag()
poll cancelFlag
void calculate(Graph::ptr G)
finally compute the contents of a CGR
tbb::combinable< CriticalValueList > LocalCriticalValueList
void barrier(bool finish)
put up a memory barrier between each level of the call graph (necessary for OpenCL implementation)
tbb::enumerable_thread_specific< PolygonShortestPathsFS * > LocalSPT
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...
Triangulation triangulation
simplified triangulation for P, complete triangulation for Q
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...
global definitions for all algorithms.
virtual void calculateValidPlacements(double epsilon) override
calculate all valid placements
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.
AlgorithmMultiCore()
default constructor
Algorithm::ptr newPolyAlgorithm(bool topo)
factory method for creating a new algorithm object. Choose the appropriate implementation based on av...
virtual void cleanup() override
release all memory
virtual ~AlgorithmMultiCore()
destructor
bool is_c_diagonal(int di, int dj) const
check, whether a diagonal is a c-diagonal
virtual void COMBINE(reach::Graph::ptr A, int di, int dj)
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...
reach::GraphModel::ptr graphModel
map free-space interval to nodes of the reachability graph
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
void clear_qtri()
release thread-local variables
virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr A, const reach::Graph::ptr B)
virtual GraphPtr findFeasiblePath() override
the main loop of Buchin et al's decision algorithm.
virtual void cleanup()
release memory (meoisation maps, etc.)
static bool is_polygon_edge(Edge e)
virtual void calculateValidPlacements(double epsilon) override
calculate all valid placements
Guibas' Algorithm with additional Free-Space computation.
struct frechet::poly::Algorithm::CurveData * Q
implementation with a sorted call-graph.
virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e)
compute a Combined Reachabilty Graph.
virtual reach::Graph::ptr create_RG(int i)
compute an initial Reachabilty Graph.
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....
virtual void calculateReachabilityGraphs() override
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map
base class for algorithm for simple polygons.
virtual ~AlgorithmTopoSort()
destructor release all memory
GraphList roots
roots of the call graph: this is where the results of the algorithm pop up
static LocalSPT spt
thread-local copies for PolygonShortestPathsFS
const Segments & c_diagonals() const
the c-diagonals
Triangulation & triangulation() const
void clear()
release all resources
void reclaimPredecessors(Graph::ptr G)
release CGRs that are not needed anymore
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...
virtual void triangulate() override
re-implements base class method; stores thread-local copies of Q's triangulation
GraphPtr newGraph(const GraphModel::ptr model)
std::vector< Segment > c_diagonals_vector
vector of c-diagonals
virtual void release()
release memory for all parts of the adjacancy matrix
int d(int i) const
map a diagonal end-point to a vertex in P
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
struct frechet::poly::Algorithm::CurveData * P
static bool is_south_pole(Vertex_handle v)
virtual bool isSolution(GraphPtr G) override
virtual void triangulate()
compute triangulations of input curves
GraphPtr calculate_RG(int i)
get a Reachability Graph; compute it, if necessary. Subsequent calls retrieve the memo-ized result.
PlacementMap _validPlacements
map of valid placements (as adjacency matrices, for each c-diagonal)
std::pair< Edge, Edge > EdgePair
a pair of edges
MatrixPool pool
recycling pool of matrices
virtual void calculateReachabilityGraphs() override
boost::shared_ptr< Graph > ptr
void calculatePlacements(int i, frechet::reach::Placements &result)
calculate free-space placements
GraphMap CRG_map
a map of memo-ized Combined Reachability Graphs
bool assertEquals(const Triangulation &that) const
equality assertion for debugging
Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure,...
PlacementVector _placements
list of placements (for each end point of diagonals)
bool assertReachabilityGraphs()
debug assertion; check if the CRGs are correctyl aligned
int l() const
number of diagonal end points
static LocalTriangulation qtri
thread-local copies of Q->triangulation
tbb::enumerable_thread_specific< Triangulation * > LocalTriangulation
VertexPair incidentVertexes(Edge e) const
struct frechet::reach::Graph::Origin origin
static LocalCriticalValueList localCriticalValues
thread-local copies of critical values
Graph::ptr A
if this graph was constructed as transitive closure: original graphs this = MERGE(A,...
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...
void addTopoSort(Graph::ptr G)
insert a CGR into the topologically sorted list of calls
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
int succesors
number of successors
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
void reclaim(Graph *G)
reclaim graph memory
static bool is_outer_edge(Edge e)
TopoSort topo
sorted call graph
static bool is_adjacent_to(const Graph &A, const Graph &B)
Triangulation::Edge diagonalEdge(int i) const
a diagonal edge of the triangulation of P
virtual void calculateValidPlacements(double epsilon)=0
calculate all valid placements