Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::poly::AlgorithmMultiCore Class Reference

Detailed Description

Multi-Core implementaion. Uses Intel TBB to perform some parallel computation.

The number of parallel threads is controlled by ConcurrencyContext.

  • computation of free-space intervals is done in parallel
  • computation of initial reachability graphs is done in parallel
  • computation of critical values is done in parallel thread-local copies of critical values are hold and finally reduced to a single list
  • computation of valid placements is done in parallel to avoid conncurrency issues, the algorithm for shortest-paths trees operates on thread-local copies
  • MERGE and COMBINE operations on reachability graphs (multiplication of adjacancy matrices) are parallelized
  • if GPGPU support is available, matrix multiplications are delegated to the GPU. This is handled transparently by frechet::reach::Graph factory methods.

    Parallelisation of the decision-variant main loop was considered but discarded. See AlgorithmTopoSort for more information.

    In the decision variant for curves (Alt and Godau's algorithm): computation of reachability structures (recursion) is parallelized.

Author
Peter Schäfer

Definition at line 88 of file parallel.h.

#include <parallel.h>

Inherits frechet::poly::AlgorithmSingleCore.

Inherited by frechet::poly::AlgorithmTopoSort.

Public Member Functions

 AlgorithmMultiCore ()
 default constructor More...
 
virtual ~AlgorithmMultiCore ()
 destructor More...
 
virtual void triangulate () override
 re-implements base class method; stores thread-local copies of Q's triangulation More...
 
- Public Member Functions inherited from frechet::poly::AlgorithmSingleCore
 AlgorithmSingleCore ()
 
- Public Member Functions inherited from frechet::poly::Algorithm
 Algorithm ()
 default constructor More...
 
virtual ~Algorithm ()
 destructor; releases all memory More...
 
Status status () const
 current status of the algorithm More...
 
bool canDecidePoly () const
 check if we can execute the decision variant on simple polygons (Buchin et al.'s algorithm) More...
 
bool canOptimisePoly () const
 check if we can execute the optimisation variant on simple polygons (Buchin et al.'s algorithm) More...
 
bool canOptimiseCurve () const
 check if we can execute the optimisation variant on curves (Alt and Godau's algorithm) More...
 
const Segmentsc_diagonals () const
 the c-diagonals More...
 
bool is_c_diagonal (int di, int dj) const
 check, whether a diagonal is a c-diagonal More...
 
bool is_c_diagonal (Segment s) const
 check, whether a diagonal is a c-diagonal More...
 
TriangulationPTriangulation ()
 the triangulation of P More...
 
TriangulationQTriangulation ()
 the triangulation of Q More...
 
TriangulationdisplayPTriangulation ()
 a complete triangulation for P (only needed for visualisation More...
 
const CurvePcurve () const
 the first input curve P More...
 
const CurveQcurve () const
 the first input curve Q More...
 
PolygonUtilitiespolygonUtilities (bool primary)
 helper object for polygon analysis More...
 
Status setup (Curve &aP, Curve &aQ, bool fixOrientation=false)
 Initialize input curves and perform some basic sanity checks. More...
 
bool decompose (bool optimal)
 decompose polygons into convex parts More...
 
void swap ()
 swap input curves. The algorithm by Buchin et al. chooses the smalled convex decompositioin as P. More...
 
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) More...
 
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 broadcast by signal optimisationResult(double epsilon). More...
 
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) More...
 
double optimiseCurve (double approximation=0.0)
 execute the optimisation variant for curves. (Alt and Godau's algorithm) More...
 
void collectCriticalValues (bool a, bool b, bool c, bool d)
 compute a set of critical values for the optimisation variant More...
 
template<typename R >
int binarySearch (const std::vector< double > &values, int lo, int hi, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)
 
template<typename R >
double intervalSearch (double lower_bound, double upper_bound, double precision, R(Algorithm::*decideFunction)(FreeSpace::ptr, reach::FSPath::ptr, double, bool), R &result)
 
template<typename Float >
Float segment_distance (const QLineF &segment, const Point &q1)
 
template<typename Float >
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)
 
template<typename Float >
Float bisector_distance (const Point &q1, const Point &q2, const QLineF &segment, Float tolerance)
 

Protected Member Functions

virtual void calculateReachabilityGraphs () override
 
virtual void calculateValidPlacements (double epsilon) override
 calculate all valid placements More...
 
virtual CriticalValueListcurrentCriticalValueList ()
 thread-local copy of critical values More...
 
virtual void collectCriticalValues_b (const Curve &P, const Curve &Q) override
 compute critical values of type (b) More...
 
virtual void collectCriticalValues_c (const Curve &P, const Curve &Q) override
 compute critical values of type (c) More...
 
virtual void collectCriticalValues_d () override
 compute critical values for diagonals and reflex vertices More...
 
virtual void combineCriticalValues () override
 reduce thread-local lists to a global list, then sort it More...
 
void clear_qtri ()
 release thread-local variables More...
 
- Protected Member Functions inherited from frechet::poly::AlgorithmSingleCore
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.'s decision algorithm. More...
 
virtual reach::Graph::ptr create_RG (int i)
 compute an initial Reachabilty Graph. More...
 
virtual reach::Graph::ptr create_CRG (int i, int j, Triangulation::Edge e)
 compute a Combined Reachabilty Graph. More...
 
virtual reach::Graph::ptr MERGE_inner (const reach::Graph::ptr A, const reach::Graph::ptr B)
 
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 More...
 
virtual void COMBINE (reach::Graph::ptr A, int di, int dj)
 
virtual GraphPtr findFeasiblePath () override
 the main loop of Buchin et al's decision algorithm. More...
 
virtual bool isSolution (GraphPtr G)
 
bool assertReachabilityGraphs ()
 debug assertion; check if the CRGs are correctyl aligned More...
 
- Protected Member Functions inherited from frechet::poly::Algorithm
GraphPtr getValidPlacements (int di, int dj)
 get valid placements for a given pair of diagonal end points; compute them, if necssary. Subsequent calls retrieve the memo-ized result. More...
 
GraphPtr calculate_RG (int i)
 get a Reachability Graph; compute it, if necessary. Subsequent calls retrieve the memo-ized result. More...
 
int mapKey (int di, int dj)
 hash key for memo-ized maps More...
 
GraphPtr createValidPlacementGraph (int di, int dj)
 compute an adjacancy matrix of valid placements for one pair of diagonal end points More...
 
void calculateValidPlacements (poly::PolygonShortestPathsFS &spt, double epsilon, int di, int dj)
 calculate valid placements for a pair of diagonal end points More...
 
Triangulation::Edge diagonalEdge (int i) const
 a diagonal edge of the triangulation of P More...
 
int l () const
 number of diagonal end points More...
 
int k () const
 number of c-diagonals More...
 
int d (int i) const
 map a diagonal end-point to a vertex in P More...
 
int partitions () const
 number of convex partitions (components) More...
 
void calculatePlacements (int i, frechet::reach::Placements &result)
 calculate free-space placements More...
 
Status setStatus (Status)
 set current status More...
 
Status setInitialStatus (Status)
 set initial status (after pre-processing input data) More...
 
virtual void cleanup ()
 release memory (meoisation maps, etc.) More...
 
void updatePath (reach::FSPath::ptr path, GraphPtr result, double epsilon)
 compute a feasible path from the result of (Buchin et al.'s) decision algorithm More...
 
void updatePath (reach::FSPath::ptr path, reach::Pointer startPointer, double epsilon)
 compute a feasible path from the result of (Alt and Godau's) decision algorithm More...
 
void collectCriticalValues_a ()
 compute critical values of type (a) More...
 
void collectCriticalValues_b (const Point &p, const Curve &Q)
 compute critical values of type (b) More...
 
void collectCriticalValues_c (const QLineF &pseg, const Curve &Q)
 compute critical values of type (c) More...
 
void collectCriticalValues_d (const QLineF &diagonal)
 compute critical values for diagonals and reflex vertices More...
 
virtual void collectCriticalValue (const accurate_float &x)
 store a critical value. Duplicates are accepted but removed later. More...
 
void removeDuplicates (CriticalValueList &vector)
 remove duplicates from a sorted list of critical values More...
 
template<typename R >
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, perform the decision variant. More...
 
template<typename R >
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. More...
 
void testCancelFlag ()
 poll cancelFlag More...
 

Static Protected Member Functions

static const CriticalValueListcombine (CriticalValueList &a, const CriticalValueList &b)
 reduce two thread-local lists of critical values; the lists are simply appended More...
 
- Static Protected Member Functions inherited from frechet::poly::Algorithm
template<typename Float >
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 More...
 
template<typename Float >
static Float segment_distance (const QLineF &segment, const Point &q1)
 compute the distance between a polygon segment and a point More...
 
template<typename Float >
static Float bisector_distance (const Point &q1, const Point &q2, const QLineF &segment, Float tolerance=0.0)
 compute the distance between a bisector and a polygon segment More...
 

Private Types

typedef tbb::enumerable_thread_specific< Triangulation * > LocalTriangulation
 
typedef tbb::combinable< CriticalValueListLocalCriticalValueList
 
typedef tbb::enumerable_thread_specific< PolygonShortestPathsFS * > LocalSPT
 

Private Attributes

std::vector< Segmentc_diagonals_vector
 vector of c-diagonals More...
 

Static Private Attributes

static LocalTriangulation qtri
 thread-local copies of Q->triangulation More...
 
static LocalCriticalValueList localCriticalValues
 thread-local copies of critical values More...
 
static LocalSPT spt
 thread-local copies for PolygonShortestPathsFS More...
 

Additional Inherited Members

- Public Types inherited from frechet::poly::Algorithm
enum  Status : int8_t {
  RUNNING = -2, RUNNING_DECIDE_POLY =-8, RUNNING_OPT_POLY =-7, RUNNING_APPROX_POLY =-6,
  RUNNING_DECIDE_CURVE =-5, RUNNING_OPT_CURVE =-4, RUNNING_APPROX_CURVE =-3, YES =0,
  NO, NOT_SET_UP, SET_UP, P_EMPTY,
  Q_EMPTY, P_NOT_CLOSED, Q_NOT_CLOSED, P_NOT_SIMPLE,
  Q_NOT_SIMPLE, P_NOT_COUNTER_CLOCKWISE, Q_NOT_COUNTER_CLOCKWISE, P_CONVEX,
  Q_CONVEX
}
 indicates the current status of the algorithm. Negative values indicate that the algorithm is currently computing. Positive values indicate the result and also conditions of input data. More...
 
typedef frechet::reach::Graph::ptr GraphPtr
 the result of the decision algorithm is a reachability Graph containing a feasible path More...
 
typedef boost::shared_ptr< Algorithmptr
 (smart) pointer to an Algorithm object More...
 
- Public Slots inherited from frechet::poly::Algorithm
void resetStatus (bool stopping=false)
 reset the status of the algorithm More...
 
- Signals inherited from frechet::poly::Algorithm
void statusChanged ()
 emitted whenever the status of the algorithm changes. More...
 
void pathUpdated (bool valid)
 emitted when a feasible path has been found More...
 
void optimisationResult (double epsilon)
 emitted when the optimisation (or approximation) algorithm finds a result More...
 
- Static Public Member Functions inherited from frechet::poly::Algorithm
static double pickIntervalPoint (const Interval &j, int m=INT_MAX)
 pick a point from a free-space interval. Helper function for creating feasible paths. More...
 
- Protected Types inherited from frechet::poly::Algorithm
typedef tbb::concurrent_unordered_map< int, GraphPtrPlacementMap
 hash map for reachability graphs More...
 
typedef std::vector< reach::PlacementsPlacementVector
 list of valid placements More...
 
typedef tbb::concurrent_unordered_map< int, reach::Graph::ptrGraphMap
 used to store intermediate (memo-ized) reachability graphs More...
 
typedef std::vector< double > CriticalValueList
 a list of critical values More...
 
- Protected Attributes inherited from frechet::poly::Algorithm
enum Status _status
 current status of the algorithm More...
 
enum Status initial_status
 initial status of the algorithm (before or after processing input data) More...
 
struct frechet::poly::Algorithm::CurveDataP
 
struct frechet::poly::Algorithm::CurveDataQ
 
FreeSpace::ptr fs
 current Free-Space diagram (passed to the decision variant) More...
 
PlacementVector _placements
 list of placements (for each end point of diagonals) More...
 
PlacementMap _validPlacements
 map of valid placements (as adjacency matrices, for each c-diagonal) More...
 
reach::GraphModel::ptr graphModel
 map free-space interval to nodes of the reachability graph More...
 
GraphMap CRG_map
 a map of memo-ized Combined Reachability Graphs More...
 
FreeSpace::ptr local_fs
 Free-Space used during binary searches (optimisation variant) More...
 
CriticalValueList criticalValues
 the list of critical values (optimisation variant) More...
 
volatile bool * cancelFlag
 indicates user interruption More...
 

Member Typedef Documentation

◆ LocalCriticalValueList

Definition at line 96 of file parallel.h.

◆ LocalSPT

typedef tbb::enumerable_thread_specific<PolygonShortestPathsFS*> frechet::poly::AlgorithmMultiCore::LocalSPT
private

Definition at line 100 of file parallel.h.

◆ LocalTriangulation

typedef tbb::enumerable_thread_specific<Triangulation*> frechet::poly::AlgorithmMultiCore::LocalTriangulation
private

Definition at line 90 of file parallel.h.

Constructor & Destructor Documentation

◆ AlgorithmMultiCore()

AlgorithmMultiCore::AlgorithmMultiCore ( )

default constructor

Definition at line 29 of file parallel.cpp.

◆ ~AlgorithmMultiCore()

AlgorithmMultiCore::~AlgorithmMultiCore ( )
virtual

destructor

Definition at line 40 of file parallel.cpp.

Member Function Documentation

◆ calculateReachabilityGraphs()

void AlgorithmMultiCore::calculateReachabilityGraphs ( )
overrideprotectedvirtual

Now with a parallel for loop. Note that writes to _RG_map are independent, no concurrency problems.

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 98 of file parallel.cpp.

◆ calculateValidPlacements()

void AlgorithmMultiCore::calculateValidPlacements ( double  epsilon)
overrideprotectedvirtual

calculate all valid placements

Parameters
epsilonfree-space epsilon

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 155 of file parallel.cpp.

◆ clear_qtri()

void AlgorithmMultiCore::clear_qtri ( )
protected

release thread-local variables

Definition at line 47 of file parallel.cpp.

◆ collectCriticalValues_b()

void AlgorithmMultiCore::collectCriticalValues_b ( const Curve P,
const Curve Q 
)
overrideprotectedvirtual

compute critical values of type (b)

Parameters
Pfirst input curve P
Qsecond curve Q

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 145 of file optimise.cpp.

◆ collectCriticalValues_c()

void AlgorithmMultiCore::collectCriticalValues_c ( const Curve P,
const Curve Q 
)
overrideprotectedvirtual

compute critical values of type (c)

Parameters
Pfirst input curve P
Qsecond curve Q

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 185 of file optimise.cpp.

◆ collectCriticalValues_d()

void AlgorithmMultiCore::collectCriticalValues_d ( )
overrideprotectedvirtual

compute critical values for diagonals and reflex vertices

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 238 of file optimise.cpp.

◆ combine()

const AlgorithmMultiCore::CriticalValueList & AlgorithmMultiCore::combine ( CriticalValueList a,
const CriticalValueList b 
)
staticprotected

reduce two thread-local lists of critical values; the lists are simply appended

Parameters
aa list
banother list
Returns
reference to a, after appending b

Definition at line 100 of file optimise.cpp.

◆ combineCriticalValues()

void AlgorithmMultiCore::combineCriticalValues ( )
overrideprotectedvirtual

reduce thread-local lists to a global list, then sort it

Reimplemented from frechet::poly::AlgorithmSingleCore.

Definition at line 71 of file optimise.cpp.

◆ currentCriticalValueList()

Algorithm::CriticalValueList & AlgorithmMultiCore::currentCriticalValueList ( )
protectedvirtual

thread-local copy of critical values

Reimplemented from frechet::poly::Algorithm.

Definition at line 33 of file optimise.cpp.

◆ triangulate()

void AlgorithmMultiCore::triangulate ( )
overridevirtual

re-implements base class method; stores thread-local copies of Q's triangulation

Reimplemented from frechet::poly::Algorithm.

Definition at line 63 of file parallel.cpp.

Member Data Documentation

◆ c_diagonals_vector

std::vector<Segment> frechet::poly::AlgorithmMultiCore::c_diagonals_vector
private

vector of c-diagonals

Definition at line 94 of file parallel.h.

◆ localCriticalValues

AlgorithmMultiCore::LocalCriticalValueList AlgorithmMultiCore::localCriticalValues
staticprivate

thread-local copies of critical values

Definition at line 98 of file parallel.h.

◆ qtri

AlgorithmMultiCore::LocalTriangulation AlgorithmMultiCore::qtri
staticprivate

thread-local copies of Q->triangulation

Definition at line 92 of file parallel.h.

◆ spt

AlgorithmMultiCore::LocalSPT AlgorithmMultiCore::spt
staticprivate

thread-local copies for PolygonShortestPathsFS

Definition at line 102 of file parallel.h.


The documentation for this class was generated from the following files: