![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
Multi-Core implementaion. Uses Intel TBB to perform some parallel computation.
The number of parallel threads is controlled by ConcurrencyContext.
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.
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... | |
![]() | |
AlgorithmSingleCore () | |
![]() | |
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 Segments & | c_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... | |
Triangulation & | PTriangulation () |
the triangulation of P More... | |
Triangulation & | QTriangulation () |
the triangulation of Q More... | |
Triangulation & | displayPTriangulation () |
a complete triangulation for P (only needed for visualisation More... | |
const Curve & | Pcurve () const |
the first input curve P More... | |
const Curve & | Qcurve () const |
the first input curve Q More... | |
PolygonUtilities * | polygonUtilities (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 CriticalValueList & | currentCriticalValueList () |
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... | |
![]() | |
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... | |
![]() | |
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 CriticalValueList & | combine (CriticalValueList &a, const CriticalValueList &b) |
reduce two thread-local lists of critical values; the lists are simply appended More... | |
![]() | |
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< CriticalValueList > | LocalCriticalValueList |
typedef tbb::enumerable_thread_specific< PolygonShortestPathsFS * > | LocalSPT |
Private Attributes | |
std::vector< Segment > | c_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 | |
![]() | |
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< Algorithm > | ptr |
(smart) pointer to an Algorithm object More... | |
![]() | |
void | resetStatus (bool stopping=false) |
reset the status of the algorithm More... | |
![]() | |
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 double | pickIntervalPoint (const Interval &j, int m=INT_MAX) |
pick a point from a free-space interval. Helper function for creating feasible paths. More... | |
![]() | |
typedef tbb::concurrent_unordered_map< int, GraphPtr > | PlacementMap |
hash map for reachability graphs More... | |
typedef std::vector< reach::Placements > | PlacementVector |
list of valid placements More... | |
typedef tbb::concurrent_unordered_map< int, reach::Graph::ptr > | GraphMap |
used to store intermediate (memo-ized) reachability graphs More... | |
typedef std::vector< double > | CriticalValueList |
a list of critical values More... | |
![]() | |
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::CurveData * | P |
struct frechet::poly::Algorithm::CurveData * | Q |
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... | |
|
private |
Definition at line 96 of file parallel.h.
|
private |
Definition at line 100 of file parallel.h.
|
private |
Definition at line 90 of file parallel.h.
AlgorithmMultiCore::AlgorithmMultiCore | ( | ) |
default constructor
Definition at line 29 of file parallel.cpp.
|
virtual |
destructor
Definition at line 40 of file parallel.cpp.
|
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.
|
overrideprotectedvirtual |
calculate all valid placements
epsilon | free-space epsilon |
Reimplemented from frechet::poly::AlgorithmSingleCore.
Definition at line 155 of file parallel.cpp.
|
protected |
release thread-local variables
Definition at line 47 of file parallel.cpp.
|
overrideprotectedvirtual |
compute critical values of type (b)
P | first input curve P |
Q | second curve Q |
Reimplemented from frechet::poly::AlgorithmSingleCore.
Definition at line 145 of file optimise.cpp.
|
overrideprotectedvirtual |
compute critical values of type (c)
P | first input curve P |
Q | second curve Q |
Reimplemented from frechet::poly::AlgorithmSingleCore.
Definition at line 185 of file optimise.cpp.
|
overrideprotectedvirtual |
compute critical values for diagonals and reflex vertices
Reimplemented from frechet::poly::AlgorithmSingleCore.
Definition at line 238 of file optimise.cpp.
|
staticprotected |
reduce two thread-local lists of critical values; the lists are simply appended
a | a list |
b | another list |
Definition at line 100 of file optimise.cpp.
|
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.
|
protectedvirtual |
thread-local copy of critical values
Reimplemented from frechet::poly::Algorithm.
Definition at line 33 of file optimise.cpp.
|
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.
|
private |
vector of c-diagonals
Definition at line 94 of file parallel.h.
|
staticprivate |
thread-local copies of critical values
Definition at line 98 of file parallel.h.
|
staticprivate |
thread-local copies of Q->triangulation
Definition at line 92 of file parallel.h.
|
staticprivate |
thread-local copies for PolygonShortestPathsFS
Definition at line 102 of file parallel.h.