![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
Sequential implementation for a single processor core.
Definition at line 24 of file parallel.h.
#include <parallel.h>
Inherits frechet::poly::Algorithm.
Inherited by frechet::poly::AlgorithmMultiCore.
Public Member Functions | |
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... | |
virtual void | triangulate () |
compute triangulations of input curves 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... | |
virtual CriticalValueList & | currentCriticalValueList () |
get the set of current 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) |
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 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 void | calculateReachabilityGraphs () override |
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map More... | |
virtual void | calculateValidPlacements (double epsilon) override |
calculate all valid placements More... | |
virtual GraphPtr | findFeasiblePath () override |
the main loop of Buchin et al's decision algorithm. More... | |
virtual bool | isSolution (GraphPtr G) |
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 |
hook for post-processing of critical values More... | |
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... | |
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... | |
![]() | |
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... | |
![]() | |
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... | |
AlgorithmSingleCore::AlgorithmSingleCore | ( | ) |
Definition at line 21 of file parallel.cpp.
|
protected |
debug assertion; check if the CRGs are correctyl aligned
Definition at line 111 of file parallel.cpp.
|
overrideprotectedvirtual |
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 84 of file parallel.cpp.
|
overrideprotectedvirtual |
calculate all valid placements
epsilon | free-space epsilon |
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 126 of file parallel.cpp.
|
overrideprotectedvirtual |
compute critical values of type (b)
P | first input curve P |
Q | second curve Q |
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 137 of file optimise.cpp.
|
overrideprotectedvirtual |
compute critical values of type (c)
P | first input curve P |
Q | second curve Q |
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 177 of file optimise.cpp.
|
overrideprotectedvirtual |
compute critical values for diagonals and reflex vertices
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 228 of file optimise.cpp.
|
protectedvirtual |
The COMBINE function computes the combined reachability graph from the input reachability graph by keeping only those edges that encode valid placements of diagonals.
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmTopoSort.
Definition at line 337 of file parallel.cpp.
|
overrideprotectedvirtual |
hook for post-processing of critical values
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 65 of file optimise.cpp.
|
protectedvirtual |
compute a Combined Reachabilty Graph.
i | first free-space column |
j | last free-space column |
e | triangulation edge that is currently examined |
Implements frechet::poly::Algorithm.
Definition at line 225 of file parallel.cpp.
|
protectedvirtual |
compute an initial Reachabilty Graph.
i | free-space column |
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmTopoSort.
Definition at line 301 of file parallel.cpp.
|
protectedvirtual |
get a memoised Combined Reachabilty Graph. This is one of the steps in Buchin et al.'s decision algorithm.
i | first free-space column |
j | last free-space column |
e | triangulation edge that is currently examined |
Implements frechet::poly::Algorithm.
Definition at line 208 of file parallel.cpp.
|
overrideprotectedvirtual |
the main loop of Buchin et al's decision algorithm.
TODO start iteration at a promising i, e.g. the result from previous decideCurve()
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmTopoSort.
Definition at line 346 of file parallel.cpp.
|
protectedvirtual |
Reimplemented in frechet::poly::AlgorithmTopoSort.
Definition at line 380 of file parallel.cpp.
|
protectedvirtual |
The MERGE function "concatenates" adjacent reachability graphs by taking the union of the graphs, computing the transitive closure, and discarding intermediate vertices.
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmTopoSort.
Definition at line 311 of file parallel.cpp.
|
protectedvirtual |
perform the final MERGE operation on two Reachability Graphs
A | a reachability graph |
B | another (combined) reachability graph |
Implements frechet::poly::Algorithm.
Reimplemented in frechet::poly::AlgorithmTopoSort.
Definition at line 322 of file parallel.cpp.