15 using namespace reach;
21 initial_status(NOT_SET_UP),
56 triangulation(), display_triangulation(nullptr),
62 delete display_triangulation;
96 std::reverse(aP.begin(),aP.end());
100 std::reverse(aQ.begin(),aQ.end());
128 Q_ASSERT(optimal==
false);
158 if (convex_parts > 0) {
189 Q_ASSERT(
Q->
reflex.size() >= 1);
201 for(
const Polygon& p : partition)
204 for(
int i=0; i < p.size(); i += 2)
214 return (
int)result.size();
222 for(
const Polygon& p : partition)
227 std::copy(set.begin(),set.end(), std::back_inserter(_d_points));
229 for(
int i=0; i < _d_points.size(); ++i) {
230 int di = _d_points[i];
231 Q_ASSERT(di >= 0 && di < n());
233 triangulation[di]->dindex = i;
235 return (
int) _d_points.size();
244 if (afs->n==0 || afs->m==0
254 int concurrency = ConcurrencyContext::countThreads();
279 path->update(path->toPoint(startPointer),epsilon);
291 throw InterruptedException();
299 valid->setOriginPlacement(di,dj);
308 double epsilon,
int di,
int dj)
323 int size_before1,size_before2;
324 size_before1 = sptri.
size();
328 static const double PRECISION=1e-9;
331 for( ; wi!=wiend; ++wi)
338 for ( ; wj != wjend; ++wj)
339 if (wi->fs.intersects(wj->fs))
341 double w = (wi->fs & wj->fs).mid();
343 Q_ASSERT(numeric::euclidean_distance<double>(dline.p1(),q) <= epsilon+PRECISION);
344 Q_ASSERT(numeric::euclidean_distance<double>(dline.p2(),q) <= epsilon+PRECISION);
346 valid->add_range(wi->gn,wj->gn);
356 size_before2 = sptri.
size();
361 sptri.
resize(size_before2);
367 sptri.
resize(size_before1);
378 int di1 =
d(i - 1) % n;
439 { Q_ASSERT(!update_status); }
483 std::cout <<
" Data: " <<
"matrix size (VV) = " <<
graphModel->count2(
VERTICAL) << std::endl;
525 if (path && update_status)
542 poly_path->
update(result, epsilon);
575 int ci = (int)ceil(j.
lower());
576 if (ci > j.
upper()) {
592 std::list<Interval> ivals =
fs->collectFreeVerticalIntervals(di);
594 result.resize(ivals.size());
595 std::list<Interval>::iterator j = ivals.begin();
597 for(
int i=0; i < ivals.size(); ++i,++j)
599 Q_ASSERT(j->lower() >= 0);
600 Q_ASSERT(j->upper() >= j->lower());
601 Q_ASSERT(j->upper() <=
fs->m);
606 Q_ASSERT(j->contains(p.w));
607 Q_ASSERT(p.w!=(
fs->m-1));
616 return dj *
P->
n() + di;
634 int dj1 =
d(i+1) % n;
635 int dj2 = (dj1 >= di) ? dj1 : (dj1+n);
640 str.calculateColumns( di, dj2 );
649 int h3 =
graphModel->lowerShiftedHorizontally(h1);
651 Q_ASSERT((h1==h2) || (h2==h3));
653 double s0 =
str.bottom().first()->lower();
654 double s1 =
str.bottom().last()->upper();
663 Q_ASSERT(result->hmask().lower==H0);
664 Q_ASSERT(result->hmask().upper==H2);
666 result->setOriginRG(i %
l());
674 return out <<
"["<<seg.first<<
".."<<seg.second<<
"]";
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.
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
void swap(gpuword **A, gpuword **B)
void setPolygonSize(int n)
set number of polygon vertexes
frechet::reach::Graph::ptr GraphPtr
the result of the decision algorithm is a reachability Graph containing a feasible path
Edge edge(int i, int j) const
construct an edge from two vertexes
initial status: the algorithm is not yet ready to execute
double round_up(double x, int ulps=1)
rounding function with 'units in the last place' Roughly speaking, a ulp is the smallest representabl...
time_point printTimer(std::string label, bool do_print=true)
clock benchmark
std::vector< frechet::reach::Placement > Placements
a list of Placement objects
~CurveData()
destructor; release all memory
void testCancelFlag()
poll cancelFlag
int decompose(DecompositionAlgorithm algo, bool verify)
compute a convex decomposition of the polygon. Store results in the member variable 'convex'.
stores essential information about an input curve. This data is processed once for each input curve.
static Point mapToPoint(const Curve &C, double x)
given a polygonal curve and an offset, compute the point on the curve
int partition(Partition &partition) const
compute a list of sub-polygons, one for each convex part. This is mainly copying data to a more conve...
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
model the mapping of free-space intervals to nodes in a frechet::reach::Graph.
negative result of the decision version
void findReflexVertices(Polygon &poly, double tolerance=0.0)
find all reflex (concave) vertices.
Triangulation triangulation
simplified triangulation for P, complete triangulation for Q
global definitions for all algorithms.
std::set< Segment > Segments
a set of Segment objects
input data are faulty. P is convex.
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
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
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
the algorithm is currently computing (decision variant, or optimisation variant)
void resetStatus(bool stopping=false)
reset the status of the algorithm
volatile bool * cancelFlag
indicates user interruption
input data are faulty. P is not a simple polygon.
bool is_counter_clockwise()
virtual void cleanup()
release memory (meoisation maps, etc.)
Guibas' Algorithm with additional Free-Space computation.
struct frechet::poly::Algorithm::CurveData * Q
Hertel and Mehlhorn's approximation algorithm.
void swap()
swap input curves. The algorithm by Buchin et al. chooses the smalled convex decompositioin as P.
void clearTargets()
clear targets for shortest-path tree search
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
bool decompose(bool optimal)
decompose polygons into convex parts
Vertex_handle createVertex(const Point &p, int i)
create a new triangulation vertex
void resize(int sz)
reset number of vertexes in triangulation
void updatePath(reach::FSPath::ptr path, GraphPtr result, double epsilon)
compute a feasible path from the result of (Buchin et al.'s) decision algorithm
int simplify()
Contract polygon chains to a single edge. Kepp only c-diagonal and contracted edges....
Vertex_handle addVertex(double w)
add a triangulation vertex on the edge of the polygon (does not correspond to a polygon vertex)
time_point printDebugTimer(std::string label)
clock benchmark and print elapsed time
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 & triangulation() const
BoundarySegment * Pointer
(dumb) pointer to a BoundarySegment object
GraphPtr newGraph(const GraphModel::ptr model)
void findShortestPaths(Vertex_handle start_point, const frechet::reach::Placement *asource, QLineF d, double epsilon, frechet::reach::Graph::ptr validPlacements)
void addTargetVertices(const frechet::reach::Placements &p)
add vertexes for computing valid placements
static assert_hook2 after_placement_added
unit test and debugging hook function; called when a valid placement is updated
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
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.
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)
bool is_diagonal(int n) const
int calculate_d_points()
calculate the d-points (end points of the diagonals)
void calculatePlacements(int i, frechet::reach::Placements &result)
calculate free-space placements
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
Pointer calculate()
compute the reachability structure from the underlying free-space diagram. Uses a divide-and-conquere...
Segments _c_diagonals
a list of c-diagonals
bool assertEquals(const Triangulation &that) const
equality assertion for debugging
void fanTriangulate(Triangulation &tri) const
compute a fan-triangulation from a list of convex parts. Each convex sub-polygon is triangulated usin...
PolygonUtilities * utils
helper class for polygon analysis
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)
int l() const
number of diagonal end points
placement of a diagonal point in free-space diagram When calculating valid placements in [buchin06]
input data are faulty. Q is an empty curve.
Polygon reflex
reflex vertices (for Q only)
CurveData()
empty constructor
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.
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)
The Reachability Structure; maintains a list of intervals on the border of Free Space,...
Interval fs
Free-Space Interval.
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....
a feasible-path for simple polygons.
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
a helper class for polygon analysis.
an interval of two double values.
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 decision variant for simple polygons
std::ostream & operator<<(std::ostream &out, const frechet::poly::CgalPolygon &poly)
print operator (for debugging)
double max(double a, double b)
maximum function with checks for NAN
Triangulation::Edge diagonalEdge(int i) const
a diagonal edge of the triangulation of P
void update(const Graph::ptr result, double epsilon)
compute a feasible path from the results of the simple polygon algorithm
virtual void calculateValidPlacements(double epsilon)=0
calculate all valid placements