![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
base class for algorithm for simple polygons.
This class performs all necessary steps to compute the algorithm for simple polygons (decision variant, and optimisation variant)
The current status of the algorithm is tracked and reported to the application logic. Other parts of the application (notably the GUI) connect to signals.
Input data are meant to be:
For open curves and convex curves we apply the much simpler algorithm of Alt and Godau (which is, for convenience, implemented in the same class).
Definition at line 51 of file algorithm.h.
#include <algorithm.h>
Inherits QObject.
Inherited by frechet::poly::AlgorithmSingleCore.
Classes | |
struct | CurveData |
stores essential information about an input curve. This data is processed once for each input curve. More... | |
Public Types | |
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... | |
Public Slots | |
void | resetStatus (bool stopping=false) |
reset the status of the algorithm More... | |
Signals | |
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... | |
Public Member Functions | |
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) |
Static Public Member Functions | |
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 | |
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... | |
Protected Member Functions | |
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... | |
virtual void | calculateValidPlacements (double epsilon)=0 |
calculate all valid placements More... | |
virtual void | calculateReachabilityGraphs ()=0 |
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map More... | |
virtual GraphPtr | findFeasiblePath ()=0 |
the main loop of Buchin et al's decision algorithm. 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... | |
virtual reach::Graph::ptr | CRG (int i, int j, Triangulation::Edge e=Triangulation::Edge())=0 |
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)=0 |
compute an initial Reachabilty Graph. More... | |
virtual reach::Graph::ptr | create_CRG (int i, int j, Triangulation::Edge e)=0 |
compute a Combined Reachabilty Graph. More... | |
virtual reach::Graph::ptr | MERGE_inner (const reach::Graph::ptr A, const reach::Graph::ptr B)=0 |
perform the MERGE operation on two Reachability Graphs More... | |
virtual reach::Graph::ptr | MERGE_outer (const reach::Graph::ptr A, const reach::Graph::ptr B)=0 |
perform the final MERGE operation on two Reachability Graphs More... | |
virtual void | COMBINE (reach::Graph::ptr A, int di, int dj)=0 |
perform the COMBINE operation, apply valid 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... | |
virtual void | collectCriticalValues_b (const Curve &P, const Curve &Q)=0 |
compute critical values of type (b) More... | |
virtual void | collectCriticalValues_c (const Curve &P, const Curve &Q)=0 |
compute critical values of type (c) More... | |
virtual void | collectCriticalValues_d ()=0 |
compute critical values for diagonals and reflex vertices More... | |
virtual void | combineCriticalValues ()=0 |
hook for post-processing of critical values 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 | |
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... | |
Protected Attributes | |
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... | |
Friends | |
class | frechet::poly::PolygonWorkerJob |
background worker job More... | |
|
protected |
a list of critical values
Definition at line 230 of file algorithm.h.
|
protected |
used to store intermediate (memo-ized) reachability graphs
Definition at line 198 of file algorithm.h.
the result of the decision algorithm is a reachability Graph containing a feasible path
Definition at line 116 of file algorithm.h.
|
protected |
hash map for reachability graphs
Definition at line 185 of file algorithm.h.
|
protected |
list of valid placements
Definition at line 187 of file algorithm.h.
typedef boost::shared_ptr<Algorithm> frechet::poly::Algorithm::ptr |
(smart) pointer to an Algorithm object
Definition at line 236 of file algorithm.h.
enum frechet::poly::Algorithm::Status : int8_t |
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.
Definition at line 76 of file algorithm.h.
Algorithm::Algorithm | ( | ) |
default constructor
Definition at line 18 of file algorithm.cpp.
|
virtual |
destructor; releases all memory
Definition at line 32 of file algorithm.cpp.
int frechet::poly::Algorithm::binarySearch | ( | const std::vector< double > & | values, |
int | lo, | ||
int | hi, | ||
R(Algorithm::*)(FreeSpace::ptr, reach::FSPath::ptr, double, bool) | decideFunction, | ||
R & | result | ||
) |
Definition at line 3 of file optimise_impl.h.
|
protected |
perform a binary search on a list of critical values. For each step of the binary search, perform the decision variant.
values | list of critical values |
lo | lower index (inclusive) |
hi | upper index (exclusive) |
decideFunction | decision function |
R | result type of the decision function (either a reachability Graph, or an interval of the reachability structure) |
result | holds the result on return |
Float frechet::poly::Algorithm::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 | ||
) |
Definition at line 73 of file optimise_impl.h.
Float frechet::poly::Algorithm::bisector_distance | ( | const Point & | q1, |
const Point & | q2, | ||
const QLineF & | segment, | ||
Float | tolerance | ||
) |
Definition at line 105 of file optimise_impl.h.
|
staticprotected |
compute the distance between a bisector and a polygon segment
tolerance | for testig line intersections: allow some tolerance for (better find too many critical values, than find too little!) |
p1x | |
p1y | |
p2x | |
p2y | |
q1x | |
q1y | |
q2x | |
q2y |
Float | floating point type for intermediate results (float,double,long double,...) |
|
staticprotected |
compute the distance between a bisector and a polygon segment
q1 | a point in Q |
q2 | anotehr point in Q |
segment | segment in P |
tolerance | for testig line intersections: allow some tolerance for (better find too many critical values, than find too little!) |
Float | floating point type for intermediate results (float,double,long double,...) |
const Segments & Algorithm::c_diagonals | ( | ) | const |
the c-diagonals
Definition at line 38 of file algorithm.cpp.
|
protected |
get a Reachability Graph; compute it, if necessary. Subsequent calls retrieve the memo-ized result.
i | diagonal point index |
Definition at line 629 of file algorithm.cpp.
|
protected |
calculate free-space placements
i | free-space column |
result | holds the placements on return |
Definition at line 590 of file algorithm.cpp.
|
protectedpure virtual |
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map
Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.
|
protectedpure virtual |
calculate all valid placements
epsilon | free-space epsilon |
Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.
|
protected |
calculate valid placements for a pair of diagonal end points
spt | implements the shortest-paths-tree algorithm of Guibas et al. |
epsilon | free-space epsilon |
di | a diagonal end point |
dj | another diagonal end point |
Definition at line 306 of file algorithm.cpp.
|
inline |
check if we can execute the decision variant on simple polygons (Buchin et al.'s algorithm)
Definition at line 247 of file algorithm.h.
|
inline |
check if we can execute the optimisation variant on curves (Alt and Godau's algorithm)
Definition at line 251 of file algorithm.h.
|
inline |
check if we can execute the optimisation variant on simple polygons (Buchin et al.'s algorithm)
Definition at line 249 of file algorithm.h.
|
protectedvirtual |
release memory (meoisation maps, etc.)
Reimplemented in frechet::poly::AlgorithmTopoSort.
Definition at line 550 of file algorithm.cpp.
|
protectedvirtual |
store a critical value. Duplicates are accepted but removed later.
x | a critical value |
Definition at line 20 of file optimise.cpp.
void Algorithm::collectCriticalValues | ( | bool | a, |
bool | b, | ||
bool | c, | ||
bool | d | ||
) |
compute a set of critical values for the optimisation variant
a | if true, compute critical values of type (a) |
b | if true, compute critical values of type (b) |
c | if true, compute critical values of type (c) |
d | if true, compute critical values for diagonals and reflex vertices (Buchin's optimisation algorithm only) |
Definition at line 37 of file optimise.cpp.
|
protected |
compute critical values of type (a)
Definition at line 111 of file optimise.cpp.
compute critical values of type (b)
p | a point in P |
Q | the second curve Q |
Definition at line 125 of file optimise.cpp.
|
protectedpure virtual |
compute critical values of type (b)
P | first input curve P |
Q | second curve Q |
Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.
|
protected |
compute critical values of type (c)
pseg | a line segment in P |
Q | the second curve Q |
Definition at line 157 of file optimise.cpp.
|
protectedpure virtual |
compute critical values of type (c)
P | first input curve P |
Q | second curve Q |
Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.
|
protected |
compute critical values for diagonals and reflex vertices
diagonal | a diagonal in P |
Definition at line 195 of file optimise.cpp.
|
protectedpure virtual |
compute critical values for diagonals and reflex vertices
Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.
|
protectedpure virtual |
perform the COMBINE operation, apply valid placements
A | a (combined) reachability graph; updated on return |
di | diagonal end point |
dj | diagonal end point |
Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.
|
protectedpure virtual |
hook for post-processing of critical values
Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.
|
protectedpure virtual |
compute a Combined Reachabilty Graph.
i | first free-space column |
j | last free-space column |
e | triangulation edge that is currently examined |
Implemented in frechet::poly::AlgorithmSingleCore.
|
protectedpure virtual |
compute an initial Reachabilty Graph.
i | free-space column |
Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.
|
protected |
compute an adjacancy matrix of valid placements for one pair of diagonal end points
di | a diagonal end point |
dj | another diagonal end point |
Definition at line 295 of file algorithm.cpp.
|
protectedpure virtual |
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 |
Implemented in frechet::poly::AlgorithmSingleCore.
|
virtual |
get the set of current critical values
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 29 of file optimise.cpp.
|
inlineprotected |
map a diagonal end-point to a vertex in P
i | index into [0..l) modulo l |
Definition at line 419 of file algorithm.h.
reach::Pointer Algorithm::decideCurve | ( | FreeSpace::ptr | fs, |
reach::FSPath::ptr | path, | ||
double | ignored, | ||
bool | update_status | ||
) |
execute the decision variant for curves. (Alt and Godau's algorithm)
fs | free-space diagram |
path | holds a feasible path on return |
ignored | (not used) |
update_status | if true, update the status variable |
Definition at line 238 of file algorithm.cpp.
Algorithm::GraphPtr Algorithm::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)
fs | free-space diagram |
path | holds a feasible path on return |
epsilon | free-space epsilon |
update_status | if true, update the status variable |
Definition at line 429 of file algorithm.cpp.
bool Algorithm::decompose | ( | bool | optimal | ) |
decompose polygons into convex parts
Unfortunately, decomposition algorithms fail on some inputs:
The ONLY, so far, reliable algorithm seems to be Hertel & Mehlhorn's
Definition at line 125 of file algorithm.cpp.
|
protected |
a diagonal edge of the triangulation of P
i | a diagonal end point index |
Definition at line 371 of file algorithm.cpp.
|
inline |
a complete triangulation for P (only needed for visualisation
Definition at line 269 of file algorithm.h.
|
protectedpure virtual |
the main loop of Buchin et al's decision algorithm.
Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.
|
protected |
get valid placements for a given pair of diagonal end points; compute them, if necssary. Subsequent calls retrieve the memo-ized result.
di | a diagonal endpoint |
dj | anotehr diagonal endpoint |
Definition at line 620 of file algorithm.cpp.
double frechet::poly::Algorithm::intervalSearch | ( | double | lower_bound, |
double | upper_bound, | ||
double | precision, | ||
R(Algorithm::*)(FreeSpace::ptr, reach::FSPath::ptr, double, bool) | decideFunction, | ||
R & | result | ||
) |
Definition at line 32 of file optimise_impl.h.
|
protected |
perform a nested interval search. For each step of the search, perform the decision variant.
lower_bound | lower bound for epsilon |
upper_bound | upper bound for epsilon |
precision | desired result tolerance (smallest interval) |
decideFunction | decision function |
R | result type of the decision function (either a reachability Graph, or an interval of the reachability structure) |
result | holds the result on return |
bool Algorithm::is_c_diagonal | ( | int | di, |
int | dj | ||
) | const |
check, whether a diagonal is a c-diagonal
di | index of a diagonal endpoint |
dj | index of another diagonal endpoint |
Definition at line 47 of file algorithm.cpp.
bool Algorithm::is_c_diagonal | ( | Segment | s | ) | const |
check, whether a diagonal is a c-diagonal
s | a diagonal segment |
Definition at line 43 of file algorithm.cpp.
|
inlineprotected |
number of c-diagonals
Definition at line 415 of file algorithm.h.
|
inlineprotected |
number of diagonal end points
Definition at line 413 of file algorithm.h.
|
protected |
hash key for memo-ized maps
di | a diagonal endpoint |
dj | another diagonal endpoint |
Definition at line 614 of file algorithm.cpp.
|
protectedpure virtual |
perform the MERGE operation on two Reachability Graphs
A | a (combined) reachability graph |
B | another (combined) reachability graph |
Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.
|
protectedpure virtual |
perform the final MERGE operation on two Reachability Graphs
A | a reachability graph |
B | another (combined) reachability graph |
Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.
|
signal |
emitted when the optimisation (or approximation) algorithm finds a result
epsilon | result of the optimisation (or approximation) algorithm |
double Algorithm::optimiseCurve | ( | double | approximation = 0.0 | ) |
execute the optimisation variant for curves. (Alt and Godau's algorithm)
approximation | if ==0, execute the optimisation variant. If >0, execute the approximation variant with given approximation tolerance. |
Definition at line 355 of file optimise.cpp.
double Algorithm::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).
path | holds a feasible path on return |
approximation | if ==0, execute the optimisation variant. If >0, execute the approximation variant with given approximation tolerance. |
Definition at line 252 of file optimise.cpp.
|
inlineprotected |
number of convex partitions (components)
Definition at line 422 of file algorithm.h.
|
signal |
emitted when a feasible path has been found
valid | true if there is a valid feasible path. The path can be retrieved from FrechetViewApplication |
|
inline |
the first input curve P
Definition at line 272 of file algorithm.h.
|
static |
pick a point from a free-space interval. Helper function for creating feasible paths.
j | a free-space interval |
m | number of columns in free-space (optional) |
Note: in principle, p.w can be picked arbitrarily. However, to avoid nasty border cases, we should pick a somewhat predictable value that does not change too much between iterations of 'epsilon'.
The idea should be, that with growing epsilon the reachability regions grow, too. With oddly picked points this might fail sometimes.
TODO There might be smarter strategies to allow for smoother drawing of feasible paths. Border Case: a free-space interval at the bottom opens up. The feasible path is picked from that interval, creating a visible jump. To avoid those, consider two intervals for picking the next point. (don't worry if you didn't understand what I was trying to explain ;-)
Definition at line 572 of file algorithm.cpp.
|
inline |
helper object for polygon analysis
primary | for P or for Q? |
Definition at line 278 of file algorithm.h.
|
inline |
the triangulation of P
Definition at line 265 of file algorithm.h.
|
inline |
the first input curve Q
Definition at line 274 of file algorithm.h.
|
inline |
the triangulation of Q
Definition at line 267 of file algorithm.h.
|
protected |
remove duplicates from a sorted list of critical values
vector | a list of critical values |
Definition at line 82 of file optimise.cpp.
|
slot |
reset the status of the algorithm
stopping | indicates that the reset happened in response to user interruption |
Definition at line 413 of file algorithm.cpp.
Float frechet::poly::Algorithm::segment_distance | ( | const QLineF & | segment, |
const Point & | q1 | ||
) |
Definition at line 62 of file optimise_impl.h.
|
staticprotected |
compute the distance between a polygon segment and a point
segment | segment in P |
q1 | point in Q |
Float | floating point type for intermediate results (float,double,long double,...) |
|
protected |
set initial status (after pre-processing input data)
Definition at line 398 of file algorithm.cpp.
|
protected |
set current status
Definition at line 404 of file algorithm.cpp.
Algorithm::Status Algorithm::setup | ( | frechet::Curve & | aP, |
frechet::Curve & | aQ, | ||
bool | fixOrientation = false |
||
) |
Initialize input curves and perform some basic sanity checks.
aP | first input curve |
aQ | second input curve |
fixOrientation | if true, clockwise oriented curves are reversed ("repaired") to become counter-clockwise. The subsequent algorithm required counter-clockwise oriented curves. |
Definition at line 66 of file algorithm.cpp.
|
inline |
current status of the algorithm
Definition at line 244 of file algorithm.h.
|
signal |
emitted whenever the status of the algorithm changes.
void Algorithm::swap | ( | ) |
swap input curves. The algorithm by Buchin et al. chooses the smalled convex decompositioin as P.
Definition at line 139 of file algorithm.cpp.
|
protected |
poll cancelFlag
InterruptedException | if the user requested an interruption |
Definition at line 287 of file algorithm.cpp.
|
virtual |
compute triangulations of input curves
Reimplemented in frechet::poly::AlgorithmMultiCore.
Definition at line 144 of file algorithm.cpp.
|
protected |
compute a feasible path from the result of (Buchin et al.'s) decision algorithm
path | holds the feasible path on return |
result | result of the decision algorithm |
epsilon | free-space epsilon |
Definition at line 537 of file algorithm.cpp.
|
protected |
compute a feasible path from the result of (Alt and Godau's) decision algorithm
path | holds the feasible path on return |
startPointer | start point of feasible path in reachability structure |
epsilon | free-space epsilon |
Strictly speaking, we don't need a Reachability Structure for open curves. We could simply calculate an FSPath from (0,0).
We do calculate Reachability Structures for open curves just to simplify code paths, and for additional testing. It's cheap anyway.
Definition at line 275 of file algorithm.cpp.
|
friend |
background worker job
Definition at line 634 of file algorithm.h.
|
protected |
list of placements (for each end point of diagonals)
Definition at line 190 of file algorithm.h.
|
protected |
current status of the algorithm
Definition at line 124 of file algorithm.h.
|
protected |
map of valid placements (as adjacency matrices, for each c-diagonal)
Definition at line 192 of file algorithm.h.
|
protected |
indicates user interruption
Definition at line 636 of file algorithm.h.
|
protected |
a map of memo-ized Combined Reachability Graphs
Definition at line 201 of file algorithm.h.
|
protected |
the list of critical values (optimisation variant)
Definition at line 232 of file algorithm.h.
|
protected |
current Free-Space diagram (passed to the decision variant)
Definition at line 181 of file algorithm.h.
|
protected |
map free-space interval to nodes of the reachability graph
Definition at line 195 of file algorithm.h.
|
protected |
initial status of the algorithm (before or after processing input data)
Definition at line 126 of file algorithm.h.
|
protected |
Free-Space used during binary searches (optimisation variant)
Definition at line 227 of file algorithm.h.
|
protected |
|
protected |