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)

performs convex decomposition and triangulation of polygons.
computes valid placements (using the shortest-path-tree algorithm of Guibas et al.)
computes reachability graphs
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< 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...

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

typedef frechet::reach::Graph::ptr frechet::poly::Algorithm::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

typedef std::vector<reach::Placements> frechet::poly::Algorithm::PlacementVector

protected

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

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.

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

values	list of critical values
lo	lower index (inclusive)
hi	upper index (exclusive)
decideFunction	decision function

Template Parameters

R	result type of the decision function (either a reachability Graph, or an interval of the reachability structure)

Parameters

result holds 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

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

Template Parameters

Float floating 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

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

Template Parameters

Float floating 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

i	diagonal 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

i	free-space column
result	holds 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

epsilon free-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

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.

◆ 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

x	a 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

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.

◆ 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

p	a point in P
Q	the 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

P	first input curve P
Q	second 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

pseg	a line segment in P
Q	the 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

P	first input curve P
Q	second 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

diagonal a 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

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.

◆ 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

i	first free-space column
j	last free-space column
e	triangulation 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

i	free-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

di	a diagonal end point
dj	another 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

i	first free-space column
j	last free-space column
e	triangulation 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

i	index 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

fs	free-space diagram
path	holds a feasible path on return
ignored	(not used)
update_status	if 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

fs	free-space diagram
path	holds a feasible path on return
epsilon	free-space epsilon
update_status	if 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

i	a 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

di	a diagonal endpoint
dj	anotehr 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_bound	lower bound for epsilon
upper_bound	upper bound for epsilon
precision	desired result tolerance (smallest interval)
decideFunction	decision function

Template Parameters

R	result type of the decision function (either a reachability Graph, or an interval of the reachability structure)

Parameters

result holds 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

di	index of a diagonal endpoint
dj	index 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

s	a 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

di	a diagonal endpoint
dj	another 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

A	a (combined) reachability graph
B	another (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

A	a reachability graph
B	another (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

epsilon result 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

approximation if ==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

path	holds a feasible path on return
approximation	if ==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

valid true 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

j	a free-space interval
m	number 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

primary for 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

vector a 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

stopping indicates 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

segment	segment in P
q1	point in Q

Template Parameters

Float floating 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

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.

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

InterruptedException if 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

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.

◆ 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

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.

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:

include/frechet/poly/algorithm.h
src/frechet/poly/algorithm.cpp
src/frechet/poly/optimise.cpp
include/frechet/poly/optimise_impl.h

Detailed Description

Classes

Public Types

Public Slots

Signals

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Friends

Member Typedef Documentation

◆ CriticalValueList

◆ GraphMap

◆ GraphPtr

◆ PlacementMap

◆ PlacementVector

◆ ptr

Member Enumeration Documentation

◆ Status

Constructor & Destructor Documentation

◆ Algorithm()

◆ ~Algorithm()

Member Function Documentation

◆ binarySearch() [1/2]

◆ binarySearch() [2/2]

◆ bisector_distance() [1/4]

◆ bisector_distance() [2/4]

◆ bisector_distance() [3/4]

◆ bisector_distance() [4/4]

◆ c_diagonals()

◆ calculate_RG()

◆ calculatePlacements()

◆ calculateReachabilityGraphs()

◆ calculateValidPlacements() [1/2]

◆ calculateValidPlacements() [2/2]

◆ canDecidePoly()

◆ canOptimiseCurve()

◆ canOptimisePoly()

◆ cleanup()

◆ collectCriticalValue()

◆ collectCriticalValues()

◆ collectCriticalValues_a()

◆ collectCriticalValues_b() [1/2]

◆ collectCriticalValues_b() [2/2]

◆ collectCriticalValues_c() [1/2]

◆ collectCriticalValues_c() [2/2]

◆ collectCriticalValues_d() [1/2]

◆ collectCriticalValues_d() [2/2]

◆ COMBINE()

◆ combineCriticalValues()

◆ create_CRG()

◆ create_RG()

◆ createValidPlacementGraph()

◆ CRG()

◆ currentCriticalValueList()

◆ d()

◆ decideCurve()

◆ decidePolygon()

◆ decompose()

◆ diagonalEdge()

◆ displayPTriangulation()

◆ findFeasiblePath()

◆ getValidPlacements()

◆ intervalSearch() [1/2]

◆ intervalSearch() [2/2]

◆ is_c_diagonal() [1/2]

◆ is_c_diagonal() [2/2]

◆ k()

◆ l()

◆ mapKey()

◆ MERGE_inner()

◆ MERGE_outer()

◆ optimisationResult

◆ optimiseCurve()

◆ optimisePolygon()

◆ partitions()

◆ pathUpdated

◆ Pcurve()