11 #include <boost/smart_ptr.hpp> 12 #include <boost/unordered_map.hpp> 16 #include <tbb/concurrent_unordered_map.h> 18 class TriangulationTestSuite;
20 namespace frechet {
namespace poly {
22 class PolygonUtilities;
23 class PolygonWorkerJob;
120 friend class ::TriangulationTestSuite;
198 typedef tbb::concurrent_unordered_map<int, reach::Graph::ptr>
GraphMap;
224 int mapKey(
int di,
int dj);
236 typedef boost::shared_ptr<Algorithm>
ptr;
279 return (primary ?
P:
Q)->utils;
343 double approximation=0.0);
406 double epsilon,
int di,
int dj);
413 int l()
const {
return P->
l(); }
415 int k()
const {
return P->
k(); }
419 int d(
int i)
const {
return P->
d(i); }
562 int binarySearch(
const std::vector<double>& values,
int lo,
int hi,
580 double lower_bound,
double upper_bound,
double precision,
599 template<
typename Float>
601 const Float& p1x,
const Float& p1y,
602 const Float& p2x,
const Float& p2y,
603 const Float& q1x,
const Float& q1y,
604 const Float& q2x,
const Float& q2y,
605 const Float& tolerance);
614 template<
typename Float>
627 template<
typename Float>
630 const QLineF& segment,
631 Float tolerance=0.0);
653 #endif // ALGORITHM_H virtual void calculateReachabilityGraphs()=0
calculate all initial Reachability Graphs and fill ("warm up") the memoisation map
Represents a polygon line segment from node i to j.
input data are faulty. Q is not a closed curve.
std::vector< reach::Placements > PlacementVector
list of valid placements
int mapKey(int di, int dj)
hash key for memo-ized maps
virtual GraphPtr findFeasiblePath()=0
the main loop of Buchin et al's decision algorithm.
GraphPtr getValidPlacements(int di, int dj)
get valid placements for a given pair of diagonal end points; compute them, if necssary....
the algorithm is currently computing the decision variant for curves
frechet::reach::Graph::ptr GraphPtr
the result of the decision algorithm is a reachability Graph containing a feasible path
bool canOptimiseCurve() const
check if we can execute the optimisation variant on curves (Alt and Godau's algorithm)
initial status: the algorithm is not yet ready to execute
bool canDecidePoly() const
check if we can execute the decision variant on simple polygons (Buchin et al.'s algorithm)
std::vector< frechet::reach::Placement > Placements
a list of Placement objects
virtual void COMBINE(reach::Graph::ptr A, int di, int dj)=0
perform the COMBINE operation, apply valid placements
~CurveData()
destructor; release all memory
void testCancelFlag()
poll cancelFlag
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,...
stores essential information about an input curve. This data is processed once for each input curve.
Status setInitialStatus(Status)
set initial status (after pre-processing input data)
Algorithm()
default constructor
input data have been successfully processed, the algorithm is now ready to execute
virtual void collectCriticalValues_d()=0
compute critical values for diagonals and reflex vertices
the algorithm is currently computing the approximation variant for curves
negative result of the decision version
Status status() const
current status of the algorithm
Triangulation triangulation
simplified triangulation for P, complete triangulation for Q
global definitions for all algorithms.
std::vector< double > CriticalValueList
a list of critical values
CriticalValueList criticalValues
the list of critical values (optimisation variant)
std::set< Segment > Segments
a set of Segment objects
input data are faulty. P is convex.
Algorithm::ptr newPolyAlgorithm(bool topo)
factory method for creating a new algorithm object. Choose the appropriate implementation based on av...
Status
indicates the current status of the algorithm. Negative values indicate that the algorithm is current...
int n() const
number of vertices = number of edges; start/end point is counted once (other than QPolygonF!...
bool is_c_diagonal(int di, int dj) const
check, whether a diagonal is a c-diagonal
int l() const
number of diagonal end points
int d(int i) const
map a diagonal end-point to a polygon vertex
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
void optimisationResult(double epsilon)
emitted when the optimisation (or approximation) algorithm finds a result
Partition partition
simplified polygon C' (containing only the end points of c-diagonals)
positive result of the decision version
input data are faulty. P is not a oriented counter-clockwise.
input data are faulty. Q is not a simple polygon.
reach::GraphModel::ptr graphModel
map free-space interval to nodes of the reachability graph
int k() const
number of c-diagonals
the algorithm is currently computing (decision variant, or optimisation variant)
boost::shared_ptr< GraphModel > ptr
smart pointer to a GraphModel object
void resetStatus(bool stopping=false)
reset the status of the algorithm
volatile bool * cancelFlag
indicates user interruption
boost::shared_ptr< Graph > GraphPtr
input data are faulty. P is not a simple polygon.
boost::shared_ptr< Algorithm > ptr
(smart) pointer to an Algorithm object
FreeSpace::ptr local_fs
Free-Space used during binary searches (optimisation variant)
the algorithm is currently computing the approximation variant for simple polygons
virtual void cleanup()
release memory (meoisation maps, etc.)
Guibas' Algorithm with additional Free-Space computation.
struct frechet::poly::Algorithm::CurveData * Q
virtual void combineCriticalValues()=0
hook for post-processing of critical values
Abstract base class for executing the algorithm for simple polygons in a background thread....
void removeDuplicates(CriticalValueList &vector)
remove duplicates from a sorted list of critical values
void swap()
swap input curves. The algorithm by Buchin et al. chooses the smalled convex decompositioin as P.
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
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
bool decompose(bool optimal)
decompose polygons into convex parts
base class for algorithm for simple polygons.
void updatePath(reach::FSPath::ptr path, GraphPtr result, double epsilon)
compute a feasible path from the result of (Buchin et al.'s) decision algorithm
tbb::concurrent_unordered_map< int, GraphPtr > PlacementMap
hash map for reachability graphs
tbb::concurrent_unordered_map< int, reach::Graph::ptr > GraphMap
used to store intermediate (memo-ized) reachability graphs
const Segments & c_diagonals() const
the c-diagonals
Curve curve
P, resp. Q. Must be a closed curve, start and endpoint are duplicated.
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)
Triangulation & QTriangulation()
the triangulation of Q
void collectCriticalValues_a()
compute critical values of type (a)
long double accurate_float
int d(int i) const
map a diagonal end-point to a vertex in P
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
struct frechet::poly::Algorithm::CurveData * P
void statusChanged()
emitted whenever the status of the algorithm changes.
enum Status _status
current status of the algorithm
boost::shared_ptr< FSPath > ptr
smart pointer to an FSPath object
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.
void collectCriticalValues_c(const QLineF &pseg, const Curve &Q)
compute critical values of type (c)
virtual void triangulate()
compute triangulations of input curves
GraphPtr calculate_RG(int i)
get a Reachability Graph; compute it, if necessary. Subsequent calls retrieve the memo-ized result.
virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e)=0
compute a Combined Reachabilty Graph.
int partitions() const
number of convex partitions (components)
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
Triangulation * display_triangulation
complete triangulation for P – only needed for visualisation; not for the algorithm as such
void pathUpdated(bool valid)
emitted when a feasible path has been found
PlacementMap _validPlacements
map of valid placements (as adjacency matrices, for each c-diagonal)
const Curve & Qcurve() const
the first input curve Q
virtual reach::Graph::ptr create_RG(int i)=0
compute an initial Reachabilty Graph.
int calculate_d_points()
calculate the d-points (end points of the diagonals)
std::list< Polygon > Partition
a partitioning of a polygon, that is a list of sub-sets
static Float segment_distance(const QLineF &segment, const Point &q1)
compute the distance between a polygon segment and a point
boost::shared_ptr< Graph > ptr
void calculatePlacements(int i, frechet::reach::Placements &result)
calculate free-space placements
void collectCriticalValues_b(const Point &p, const Curve &Q)
compute critical values of type (b)
GraphMap CRG_map
a map of memo-ized Combined Reachability Graphs
GraphPtr createValidPlacementGraph(int di, int dj)
compute an adjacancy matrix of valid placements for one pair of diagonal end points
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....
Segments _c_diagonals
a list of c-diagonals
PolygonUtilities * utils
helper class for polygon analysis
const Curve & Pcurve() const
the first input curve P
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)
PlacementVector _placements
list of placements (for each end point of diagonals)
double optimiseCurve(double approximation=0.0)
execute the optimisation variant for curves. (Alt and Godau's algorithm)
int l() const
number of diagonal end points
PolygonUtilities * polygonUtilities(bool primary)
helper object for polygon analysis
input data are faulty. Q is an empty curve.
Triangulation & displayPTriangulation()
a complete triangulation for P (only needed for visualisation
Polygon reflex
reflex vertices (for Q only)
CurveData()
empty constructor
void collectCriticalValues(bool a, bool b, bool c, bool d)
compute a set of critical values for the optimisation variant
int calculate_c_diagonals(Segments &result)
calculate the c-diagonals
input data are faulty. Q is not a oriented counter-clockwise.
virtual ~Algorithm()
destructor; releases all memory
input data are faulty. P is an empty curve.
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
Status setup(Curve &aP, Curve &aQ, bool fixOrientation=false)
Initialize input curves and perform some basic sanity checks.
Status setStatus(Status)
set current status
input data are faulty. P is not a closed curve.
enum Status initial_status
initial status of the algorithm (before or after processing input data)
FreeSpace::ptr fs
current Free-Space diagram (passed to the decision variant)
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 ...
std::vector< int > Polygon
Polygon a sub-set of vertex indexes.
input data are faulty. Q is convex.
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
int k() const
number of c-diagonals
virtual CriticalValueList & currentCriticalValueList()
get the set of current critical values
a helper class for polygon analysis.
an interval of two double values.
Polygon _d_points
all end points of diagonals
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
static double pickIntervalPoint(const Interval &j, int m=INT_MAX)
pick a point from a free-space interval. Helper function for creating feasible paths.
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
the algorithm is currently computing the optimisation variant for simple polygons
the algorithm is currently computing the optimisation variant for curves
the algorithm is currently computing the decision variant for simple polygons
virtual void collectCriticalValue(const accurate_float &x)
store a critical value. Duplicates are accepted but removed later.
bool canOptimisePoly() const
check if we can execute the optimisation variant on simple polygons (Buchin et al....
Triangulation::Edge diagonalEdge(int i) const
a diagonal edge of the triangulation of P
Triangulation & PTriangulation()
the triangulation of P
virtual void calculateValidPlacements(double epsilon)=0
calculate all valid placements