Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::poly::Algorithm Class Referenceabstract

Detailed Description

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)

  1. performs convex decomposition and triangulation of polygons.
  2. computes valid placements (using the shortest-path-tree algorithm of Guibas et al.)
  3. computes reachability graphs
  4. computes a solution to the algorithm of Buchin et al.

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:

  • closed curves. Open curves are handled by decideCurve() instead.
  • simple polygons. There must be no self-intersections.
  • not convex. Convex curves are handled by decideCurve() instead.
  • oriented counter-clockwise. This condition can be easily repaired.

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).

Author
Peter Schäfer

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< Algorithmptr
 (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 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...
 
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 CriticalValueListcurrentCriticalValueList ()
 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, 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 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::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...
 

Friends

class frechet::poly::PolygonWorkerJob
 background worker job More...
 

Member Typedef Documentation

◆ CriticalValueList

typedef std::vector<double> frechet::poly::Algorithm::CriticalValueList
protected

a list of critical values

Definition at line 230 of file algorithm.h.

◆ GraphMap

typedef tbb::concurrent_unordered_map<int, reach::Graph::ptr> frechet::poly::Algorithm::GraphMap
protected

used to store intermediate (memo-ized) reachability graphs

Definition at line 198 of file algorithm.h.

◆ GraphPtr

the result of the decision algorithm is a reachability Graph containing a feasible path

Definition at line 116 of file algorithm.h.

◆ PlacementMap

typedef tbb::concurrent_unordered_map<int,GraphPtr> frechet::poly::Algorithm::PlacementMap
protected

hash map for reachability graphs

Definition at line 185 of file algorithm.h.

◆ PlacementVector

list of valid placements

Definition at line 187 of file algorithm.h.

◆ ptr

typedef boost::shared_ptr<Algorithm> frechet::poly::Algorithm::ptr

(smart) pointer to an Algorithm object

Definition at line 236 of file algorithm.h.

Member Enumeration Documentation

◆ Status

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.

Enumerator
RUNNING 

the algorithm is currently computing (decision variant, or optimisation variant)

RUNNING_DECIDE_POLY 

the algorithm is currently computing the decision variant for simple polygons

RUNNING_OPT_POLY 

the algorithm is currently computing the optimisation variant for simple polygons

RUNNING_APPROX_POLY 

the algorithm is currently computing the approximation variant for simple polygons

RUNNING_DECIDE_CURVE 

the algorithm is currently computing the decision variant for curves

RUNNING_OPT_CURVE 

the algorithm is currently computing the optimisation variant for curves

RUNNING_APPROX_CURVE 

the algorithm is currently computing the approximation variant for curves

YES 

positive result of the decision version

NO 

negative result of the decision version

NOT_SET_UP 

initial status: the algorithm is not yet ready to execute

SET_UP 

input data have been successfully processed, the algorithm is now ready to execute

P_EMPTY 

input data are faulty. P is an empty curve.

Q_EMPTY 

input data are faulty. Q is an empty curve.

P_NOT_CLOSED 

input data are faulty. P is not a closed curve.

Q_NOT_CLOSED 

input data are faulty. Q is not a closed curve.

P_NOT_SIMPLE 

input data are faulty. P is not a simple polygon.

Q_NOT_SIMPLE 

input data are faulty. Q is not a simple polygon.

P_NOT_COUNTER_CLOCKWISE 

input data are faulty. P is not a oriented counter-clockwise.

Q_NOT_COUNTER_CLOCKWISE 

input data are faulty. Q is not a oriented counter-clockwise.

P_CONVEX 

input data are faulty. P is convex.

Q_CONVEX 

input data are faulty. Q is convex.

Definition at line 76 of file algorithm.h.

Constructor & Destructor Documentation

◆ Algorithm()

Algorithm::Algorithm ( )

default constructor

Definition at line 18 of file algorithm.cpp.

◆ ~Algorithm()

Algorithm::~Algorithm ( )
virtual

destructor; releases all memory

Definition at line 32 of file algorithm.cpp.

Member Function Documentation

◆ binarySearch() [1/2]

template<typename R >
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.

◆ binarySearch() [2/2]

template<typename R >
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 
)
protected

perform a binary search on a list of critical values. For each step of the binary search, perform the decision variant.

Parameters
valueslist of critical values
lolower index (inclusive)
hiupper index (exclusive)
decideFunctiondecision function
Template Parameters
Rresult type of the decision function (either a reachability Graph, or an interval of the reachability structure)
Parameters
resultholds the result on return
Returns
result index, or -1 if there is no solution

◆ bisector_distance() [1/4]

template<typename Float >
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.

◆ bisector_distance() [2/4]

template<typename Float >
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.

◆ bisector_distance() [3/4]

template<typename Float >
static 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 
)
staticprotected

compute the distance between a bisector and a polygon segment

Parameters
tolerancefor 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
Template Parameters
Floatfloating point type for intermediate results (float,double,long double,...)
Returns
distance between bisector and a polygon segment

◆ bisector_distance() [4/4]

template<typename Float >
static Float frechet::poly::Algorithm::bisector_distance ( const Point q1,
const Point q2,
const QLineF &  segment,
Float  tolerance = 0.0 
)
staticprotected

compute the distance between a bisector and a polygon segment

Parameters
q1a point in Q
q2anotehr point in Q
segmentsegment in P
tolerancefor testig line intersections: allow some tolerance for (better find too many critical values, than find too little!)
Template Parameters
Floatfloating point type for intermediate results (float,double,long double,...)
Returns
distance between bisector and a polygon segment

◆ c_diagonals()

const Segments & Algorithm::c_diagonals ( ) const

the c-diagonals

Definition at line 38 of file algorithm.cpp.

◆ calculate_RG()

Algorithm::GraphPtr Algorithm::calculate_RG ( int  i)
protected

get a Reachability Graph; compute it, if necessary. Subsequent calls retrieve the memo-ized result.

Parameters
idiagonal point index
Returns
a reachability graph

Definition at line 629 of file algorithm.cpp.

◆ calculatePlacements()

void Algorithm::calculatePlacements ( int  i,
frechet::reach::Placements result 
)
protected

calculate free-space placements

Parameters
ifree-space column
resultholds the placements on return

Definition at line 590 of file algorithm.cpp.

◆ calculateReachabilityGraphs()

virtual void frechet::poly::Algorithm::calculateReachabilityGraphs ( )
protectedpure virtual

calculate all initial Reachability Graphs and fill ("warm up") the memoisation map

Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.

◆ calculateValidPlacements() [1/2]

virtual void frechet::poly::Algorithm::calculateValidPlacements ( double  epsilon)
protectedpure virtual

calculate all valid placements

Parameters
epsilonfree-space epsilon

Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.

◆ calculateValidPlacements() [2/2]

void Algorithm::calculateValidPlacements ( poly::PolygonShortestPathsFS spt,
double  epsilon,
int  di,
int  dj 
)
protected

calculate valid placements for a pair of diagonal end points

Parameters
sptimplements the shortest-paths-tree algorithm of Guibas et al.
epsilonfree-space epsilon
dia diagonal end point
djanother diagonal end point

Definition at line 306 of file algorithm.cpp.

◆ canDecidePoly()

bool frechet::poly::Algorithm::canDecidePoly ( ) const
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.

◆ canOptimiseCurve()

bool frechet::poly::Algorithm::canOptimiseCurve ( ) const
inline

check if we can execute the optimisation variant on curves (Alt and Godau's algorithm)

Definition at line 251 of file algorithm.h.

◆ canOptimisePoly()

bool frechet::poly::Algorithm::canOptimisePoly ( ) const
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.

◆ cleanup()

void Algorithm::cleanup ( )
protectedvirtual

release memory (meoisation maps, etc.)

Reimplemented in frechet::poly::AlgorithmTopoSort.

Definition at line 550 of file algorithm.cpp.

◆ collectCriticalValue()

void Algorithm::collectCriticalValue ( const accurate_float x)
protectedvirtual

store a critical value. Duplicates are accepted but removed later.

Parameters
xa critical value

Definition at line 20 of file optimise.cpp.

◆ collectCriticalValues()

void Algorithm::collectCriticalValues ( bool  a,
bool  b,
bool  c,
bool  d 
)

compute a set of critical values for the optimisation variant

Parameters
aif true, compute critical values of type (a)
bif true, compute critical values of type (b)
cif true, compute critical values of type (c)
dif true, compute critical values for diagonals and reflex vertices (Buchin's optimisation algorithm only)

Definition at line 37 of file optimise.cpp.

◆ collectCriticalValues_a()

void Algorithm::collectCriticalValues_a ( )
protected

compute critical values of type (a)

Definition at line 111 of file optimise.cpp.

◆ collectCriticalValues_b() [1/2]

void Algorithm::collectCriticalValues_b ( const Point p,
const Curve Q 
)
protected

compute critical values of type (b)

Parameters
pa point in P
Qthe second curve Q

Definition at line 125 of file optimise.cpp.

◆ collectCriticalValues_b() [2/2]

virtual void frechet::poly::Algorithm::collectCriticalValues_b ( const Curve P,
const Curve Q 
)
protectedpure virtual

compute critical values of type (b)

Parameters
Pfirst input curve P
Qsecond curve Q

Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.

◆ collectCriticalValues_c() [1/2]

void Algorithm::collectCriticalValues_c ( const QLineF &  pseg,
const Curve Q 
)
protected

compute critical values of type (c)

Parameters
psega line segment in P
Qthe second curve Q

Definition at line 157 of file optimise.cpp.

◆ collectCriticalValues_c() [2/2]

virtual void frechet::poly::Algorithm::collectCriticalValues_c ( const Curve P,
const Curve Q 
)
protectedpure virtual

compute critical values of type (c)

Parameters
Pfirst input curve P
Qsecond curve Q

Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.

◆ collectCriticalValues_d() [1/2]

void Algorithm::collectCriticalValues_d ( const QLineF &  diagonal)
protected

compute critical values for diagonals and reflex vertices

Parameters
diagonala diagonal in P

Definition at line 195 of file optimise.cpp.

◆ collectCriticalValues_d() [2/2]

virtual void frechet::poly::Algorithm::collectCriticalValues_d ( )
protectedpure virtual

compute critical values for diagonals and reflex vertices

Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.

◆ COMBINE()

virtual void frechet::poly::Algorithm::COMBINE ( reach::Graph::ptr  A,
int  di,
int  dj 
)
protectedpure virtual

perform the COMBINE operation, apply valid placements

Parameters
Aa (combined) reachability graph; updated on return
didiagonal end point
djdiagonal end point

Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.

◆ combineCriticalValues()

virtual void frechet::poly::Algorithm::combineCriticalValues ( )
protectedpure virtual

hook for post-processing of critical values

Implemented in frechet::poly::AlgorithmMultiCore, and frechet::poly::AlgorithmSingleCore.

◆ create_CRG()

virtual reach::Graph::ptr frechet::poly::Algorithm::create_CRG ( int  i,
int  j,
Triangulation::Edge  e 
)
protectedpure virtual

compute a Combined Reachabilty Graph.

Parameters
ifirst free-space column
jlast free-space column
etriangulation edge that is currently examined
Returns
a newly craeted Combined Reachability Graph

Implemented in frechet::poly::AlgorithmSingleCore.

◆ create_RG()

virtual reach::Graph::ptr frechet::poly::Algorithm::create_RG ( int  i)
protectedpure virtual

compute an initial Reachabilty Graph.

Parameters
ifree-space column
Returns
a combined reachability graph

Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.

◆ createValidPlacementGraph()

Algorithm::GraphPtr Algorithm::createValidPlacementGraph ( int  di,
int  dj 
)
protected

compute an adjacancy matrix of valid placements for one pair of diagonal end points

Parameters
dia diagonal end point
djanother diagonal end point
Returns
adjacancy matrix of valid placements

Definition at line 295 of file algorithm.cpp.

◆ CRG()

virtual reach::Graph::ptr frechet::poly::Algorithm::CRG ( int  i,
int  j,
Triangulation::Edge  e = Triangulation::Edge() 
)
protectedpure virtual

get a memoised Combined Reachabilty Graph. This is one of the steps in Buchin et al.'s decision algorithm.

Parameters
ifirst free-space column
jlast free-space column
etriangulation edge that is currently examined
Returns
a combined reachability graph, computed if necessary

Implemented in frechet::poly::AlgorithmSingleCore.

◆ currentCriticalValueList()

Algorithm::CriticalValueList & Algorithm::currentCriticalValueList ( )
virtual

get the set of current critical values

Precondition
collectCriticalValues() must have computed a set of critical values

Reimplemented in frechet::poly::AlgorithmMultiCore.

Definition at line 29 of file optimise.cpp.

◆ d()

int frechet::poly::Algorithm::d ( int  i) const
inlineprotected

map a diagonal end-point to a vertex in P

Parameters
iindex into [0..l) modulo l
Returns
index of vertex in P

Definition at line 419 of file algorithm.h.

◆ decideCurve()

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)

Precondition
a free-space diagram must have been computed
status must be SET_UP or > NOT_CLOSED
Parameters
fsfree-space diagram
pathholds a feasible path on return
ignored(not used)
update_statusif true, update the status variable
Returns
a reference to the starting interval of the path, or nullptr if there is no solution

Definition at line 238 of file algorithm.cpp.

◆ decidePolygon()

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)

Precondition
status must be SET_UP, i.e. input curves must be correct
a free-space diagram must have been computed
Parameters
fsfree-space diagram
pathholds a feasible path on return
epsilonfree-space epsilon
update_statusif true, update the status variable
Returns
the resulting reachability graph, or nullptr if there is no solution

Definition at line 429 of file algorithm.cpp.

◆ decompose()

bool Algorithm::decompose ( bool  optimal)

decompose polygons into convex parts

Returns
true if P was chosen as primary curve, false if Q was chosen (application should adapt)

Unfortunately, decomposition algorithms fail on some inputs:

  • Greene Optimal decomposition fails on hilbert-4.js, producting false results
  • Greene Approximation fails on hilbert-5.svg, producing faulty segments

The ONLY, so far, reliable algorithm seems to be Hertel & Mehlhorn's

Definition at line 125 of file algorithm.cpp.

◆ diagonalEdge()

Triangulation::Edge Algorithm::diagonalEdge ( int  i) const
protected

a diagonal edge of the triangulation of P

Parameters
ia diagonal end point index

Definition at line 371 of file algorithm.cpp.

◆ displayPTriangulation()

Triangulation& frechet::poly::Algorithm::displayPTriangulation ( )
inline

a complete triangulation for P (only needed for visualisation

Definition at line 269 of file algorithm.h.

◆ findFeasiblePath()

virtual GraphPtr frechet::poly::Algorithm::findFeasiblePath ( )
protectedpure virtual

the main loop of Buchin et al's decision algorithm.

Returns
resulting CRG, or nullptr if there is no solution.

Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.

◆ getValidPlacements()

Algorithm::GraphPtr Algorithm::getValidPlacements ( int  di,
int  dj 
)
protected

get valid placements for a given pair of diagonal end points; compute them, if necssary. Subsequent calls retrieve the memo-ized result.

Parameters
dia diagonal endpoint
djanotehr diagonal endpoint
Returns
valid placements

Definition at line 620 of file algorithm.cpp.

◆ intervalSearch() [1/2]

template<typename R >
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.

◆ intervalSearch() [2/2]

template<typename R >
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 
)
protected

perform a nested interval search. For each step of the search, perform the decision variant.

Parameters
lower_boundlower bound for epsilon
upper_boundupper bound for epsilon
precisiondesired result tolerance (smallest interval)
decideFunctiondecision function
Template Parameters
Rresult type of the decision function (either a reachability Graph, or an interval of the reachability structure)
Parameters
resultholds the result on return
Returns
approximate result epsilon, or 0.0 if there is not solution

◆ is_c_diagonal() [1/2]

bool Algorithm::is_c_diagonal ( int  di,
int  dj 
) const

check, whether a diagonal is a c-diagonal

Parameters
diindex of a diagonal endpoint
djindex of another diagonal endpoint

Definition at line 47 of file algorithm.cpp.

◆ is_c_diagonal() [2/2]

bool Algorithm::is_c_diagonal ( Segment  s) const

check, whether a diagonal is a c-diagonal

Parameters
sa diagonal segment

Definition at line 43 of file algorithm.cpp.

◆ k()

int frechet::poly::Algorithm::k ( ) const
inlineprotected

number of c-diagonals

Definition at line 415 of file algorithm.h.

◆ l()

int frechet::poly::Algorithm::l ( ) const
inlineprotected

number of diagonal end points

Definition at line 413 of file algorithm.h.

◆ mapKey()

int Algorithm::mapKey ( int  di,
int  dj 
)
protected

hash key for memo-ized maps

Parameters
dia diagonal endpoint
djanother diagonal endpoint
Returns
a hash key for a pair of diagonal end points

Definition at line 614 of file algorithm.cpp.

◆ MERGE_inner()

virtual reach::Graph::ptr frechet::poly::Algorithm::MERGE_inner ( const reach::Graph::ptr  A,
const reach::Graph::ptr  B 
)
protectedpure virtual

perform the MERGE operation on two Reachability Graphs

Parameters
Aa (combined) reachability graph
Banother (combined) reachability graph
Returns
result of MERGE(A,B)

Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.

◆ MERGE_outer()

virtual reach::Graph::ptr frechet::poly::Algorithm::MERGE_outer ( const reach::Graph::ptr  A,
const reach::Graph::ptr  B 
)
protectedpure virtual

perform the final MERGE operation on two Reachability Graphs

Parameters
Aa reachability graph
Banother (combined) reachability graph
Returns
result of MERGE(A,B,A)

Implemented in frechet::poly::AlgorithmTopoSort, and frechet::poly::AlgorithmSingleCore.

◆ optimisationResult

void frechet::poly::Algorithm::optimisationResult ( double  epsilon)
signal

emitted when the optimisation (or approximation) algorithm finds a result

Parameters
epsilonresult of the optimisation (or approximation) algorithm

◆ optimiseCurve()

double Algorithm::optimiseCurve ( double  approximation = 0.0)

execute the optimisation variant for curves. (Alt and Godau's algorithm)

Precondition
status must be SET_UP or > NOT_CLOSED
Parameters
approximationif ==0, execute the optimisation variant. If >0, execute the approximation variant with given approximation tolerance.
Returns
result epsilon, or 0.0 if there is no result
result epsilon, or 0.0 if there is no result

Definition at line 355 of file optimise.cpp.

◆ optimisePolygon()

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).

Precondition
status must be SET_UP, i.e. input curves must be correct
Parameters
pathholds a feasible path on return
approximationif ==0, execute the optimisation variant. If >0, execute the approximation variant with given approximation tolerance.
Returns
result epsilon, or 0.0 if there is no result

Definition at line 252 of file optimise.cpp.

◆ partitions()

int frechet::poly::Algorithm::partitions ( ) const
inlineprotected

number of convex partitions (components)

Definition at line 422 of file algorithm.h.

◆ pathUpdated

void frechet::poly::Algorithm::pathUpdated ( bool  valid)
signal

emitted when a feasible path has been found

Parameters
validtrue if there is a valid feasible path. The path can be retrieved from FrechetViewApplication

◆ Pcurve()

const Curve& frechet::poly::Algorithm::Pcurve ( ) const
inline

the first input curve P

Definition at line 272 of file algorithm.h.

◆ pickIntervalPoint()

double Algorithm::pickIntervalPoint ( const Interval j,
int  m = INT_MAX 
)
static

pick a point from a free-space interval. Helper function for creating feasible paths.

Parameters
ja free-space interval
mnumber of columns in free-space (optional)
Returns
a point in the interval

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.

◆ polygonUtilities()

PolygonUtilities* frechet::poly::Algorithm::polygonUtilities ( bool  primary)
inline

helper object for polygon analysis

Parameters
primaryfor P or for Q?

Definition at line 278 of file algorithm.h.

◆ PTriangulation()

Triangulation& frechet::poly::Algorithm::PTriangulation ( )
inline

the triangulation of P

Definition at line 265 of file algorithm.h.

◆ Qcurve()

const Curve& frechet::poly::Algorithm::Qcurve ( ) const
inline

the first input curve Q

Definition at line 274 of file algorithm.h.

◆ QTriangulation()

Triangulation& frechet::poly::Algorithm::QTriangulation ( )
inline

the triangulation of Q

Definition at line 267 of file algorithm.h.

◆ removeDuplicates()

void Algorithm::removeDuplicates ( CriticalValueList vector)
protected

remove duplicates from a sorted list of critical values

Parameters
vectora list of critical values
Precondition
list must be sorted

Definition at line 82 of file optimise.cpp.

◆ resetStatus

void Algorithm::resetStatus ( bool  stopping = false)
slot

reset the status of the algorithm

Parameters
stoppingindicates that the reset happened in response to user interruption

Definition at line 413 of file algorithm.cpp.

◆ segment_distance() [1/2]

template<typename Float >
Float frechet::poly::Algorithm::segment_distance ( const QLineF &  segment,
const Point q1 
)

Definition at line 62 of file optimise_impl.h.

◆ segment_distance() [2/2]

template<typename Float >
static Float frechet::poly::Algorithm::segment_distance ( const QLineF &  segment,
const Point q1 
)
staticprotected

compute the distance between a polygon segment and a point

Parameters
segmentsegment in P
q1point in Q
Template Parameters
Floatfloating point type for intermediate results (float,double,long double,...)
Returns
distance between segment and point

◆ setInitialStatus()

Algorithm::Status Algorithm::setInitialStatus ( Status  st)
protected

set initial status (after pre-processing input data)

Definition at line 398 of file algorithm.cpp.

◆ setStatus()

Algorithm::Status Algorithm::setStatus ( Status  st)
protected

set current status

Definition at line 404 of file algorithm.cpp.

◆ setup()

Algorithm::Status Algorithm::setup ( frechet::Curve aP,
frechet::Curve aQ,
bool  fixOrientation = false 
)

Initialize input curves and perform some basic sanity checks.

Parameters
aPfirst input curve
aQsecond input curve
fixOrientationif true, clockwise oriented curves are reversed ("repaired") to become counter-clockwise. The subsequent algorithm required counter-clockwise oriented curves.
Returns
status of input processinig

Definition at line 66 of file algorithm.cpp.

◆ status()

Status frechet::poly::Algorithm::status ( ) const
inline

current status of the algorithm

Definition at line 244 of file algorithm.h.

◆ statusChanged

void frechet::poly::Algorithm::statusChanged ( )
signal

emitted whenever the status of the algorithm changes.

◆ swap()

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.

◆ testCancelFlag()

void Algorithm::testCancelFlag ( )
protected

poll cancelFlag

Exceptions
InterruptedExceptionif the user requested an interruption

Definition at line 287 of file algorithm.cpp.

◆ triangulate()

void Algorithm::triangulate ( )
virtual

compute triangulations of input curves

Precondition
decompose() must have creted a convex decomposition

Reimplemented in frechet::poly::AlgorithmMultiCore.

Definition at line 144 of file algorithm.cpp.

◆ updatePath() [1/2]

void Algorithm::updatePath ( reach::FSPath::ptr  path,
GraphPtr  result,
double  epsilon 
)
protected

compute a feasible path from the result of (Buchin et al.'s) decision algorithm

Parameters
pathholds the feasible path on return
resultresult of the decision algorithm
epsilonfree-space epsilon

Definition at line 537 of file algorithm.cpp.

◆ updatePath() [2/2]

void Algorithm::updatePath ( reach::FSPath::ptr  path,
reach::Pointer  startPointer,
double  epsilon 
)
protected

compute a feasible path from the result of (Alt and Godau's) decision algorithm

Parameters
pathholds the feasible path on return
startPointerstart point of feasible path in reachability structure
epsilonfree-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.

Friends And Related Function Documentation

◆ frechet::poly::PolygonWorkerJob

friend class frechet::poly::PolygonWorkerJob
friend

background worker job

Definition at line 634 of file algorithm.h.

Member Data Documentation

◆ _placements

PlacementVector frechet::poly::Algorithm::_placements
protected

list of placements (for each end point of diagonals)

Definition at line 190 of file algorithm.h.

◆ _status

enum Status frechet::poly::Algorithm::_status
protected

current status of the algorithm

Definition at line 124 of file algorithm.h.

◆ _validPlacements

PlacementMap frechet::poly::Algorithm::_validPlacements
protected

map of valid placements (as adjacency matrices, for each c-diagonal)

Definition at line 192 of file algorithm.h.

◆ cancelFlag

volatile bool* frechet::poly::Algorithm::cancelFlag
protected

indicates user interruption

Definition at line 636 of file algorithm.h.

◆ CRG_map

GraphMap frechet::poly::Algorithm::CRG_map
protected

a map of memo-ized Combined Reachability Graphs

Definition at line 201 of file algorithm.h.

◆ criticalValues

CriticalValueList frechet::poly::Algorithm::criticalValues
protected

the list of critical values (optimisation variant)

Definition at line 232 of file algorithm.h.

◆ fs

FreeSpace::ptr frechet::poly::Algorithm::fs
protected

current Free-Space diagram (passed to the decision variant)

Definition at line 181 of file algorithm.h.

◆ graphModel

reach::GraphModel::ptr frechet::poly::Algorithm::graphModel
protected

map free-space interval to nodes of the reachability graph

Definition at line 195 of file algorithm.h.

◆ initial_status

enum Status frechet::poly::Algorithm::initial_status
protected

initial status of the algorithm (before or after processing input data)

Definition at line 126 of file algorithm.h.

◆ local_fs

FreeSpace::ptr frechet::poly::Algorithm::local_fs
protected

Free-Space used during binary searches (optimisation variant)

Definition at line 227 of file algorithm.h.

◆ P

struct frechet::poly::Algorithm::CurveData * frechet::poly::Algorithm::P
protected

◆ Q

struct frechet::poly::Algorithm::CurveData * frechet::poly::Algorithm::Q
protected

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