1 #ifndef SHORTEST_PATHS_H 2 #define SHORTEST_PATHS_H 10 class TriangulationTestSuite;
13 namespace frechet {
namespace poly {
165 template<
typename Float>
234 friend class ::TriangulationTestSuite;
248 template<
typename Float>
252 double x1 = floor(a->offset);
254 if ((x1==x2) && (p->offset >= x1) && (p->offset <= (x1+1)))
264 Float A = (py-ay) * (bx-ax);
265 Float B = (px-ax) * (by-ay);
266 if (A < B)
return -1;
267 if (A > B)
return +1;
271 #endif // SHORTEST_PATHS_H Triangulation & tri
the Triangulation
Triangulation::Face_handle Face_handle
static assert_hook1 after_target_found
unit test and debugging hook function; called when a target vertex is found
Triangulation::Vertex_handle Vertex_handle
virtual void undo()
callback-function when backtrcking derived classes hook in to perform additional computations
int findTangentRight(int t1, int t2, Vertex_handle v) const
find a tangent from a point to the right part of the funnel
Triangulation::Face_circulator Face_circulator
global definitions for all algorithms.
virtual bool updateSPSegment(Vertex_handle prev, Vertex_handle v) override
hook function that is called by the shortest-tree search whenever a new segment is added to the tree....
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
void(* assert_hook1)(PolygonShortestPathsFS *, Vertex_handle v, bool reachable)
TDS::Face_handle Face_handle
handle to a triangulation face (handles are managed by TDS base class)
double epsilon
free-space parameter epsilon
Guibas' Algorithm with additional Free-Space computation.
virtual void shortestPath()
callback-function when a new shortest-path has been found. derived classes hook in to perform additio...
void findShortestPaths(Vertex_handle start_point)
traverse the polygon and report found paths
const frechet::reach::Placement * source
source placement and
void propagateReachability(Vertex_handle v)
update free-space and reachability info, called when a vertex is updated in the shortest-paths tree
void search(Vertex_handle start_point, Face_handle f)
compute the shortest-paths tree
bool isTangent(int t, Vertex_handle v) const
tangent test
Triangulation & triangulation() const
PolygonShortestPathsFS(Triangulation &atri)
default constructor
static int halfplaneTest(Vertex_handle a, Vertex_handle b, Vertex_handle p)
half-plane test.
Curve find1ShortestPath(double p1, double p2)
compute the shortest path between two points on the boundary of the polygon
int lower_floor(double x, int min=0)
floor function with lower limit
DoubleEndedQueue< Vertex_handle > Funnel
void findShortestPaths(Vertex_handle start_point, const frechet::reach::Placement *asource, QLineF d, double epsilon, frechet::reach::Graph::ptr validPlacements)
static assert_hook2 after_placement_added
unit test and debugging hook function; called when a valid placement is updated
int findTangentLeft(int t1, int t2, Vertex_handle v) const
find a tangent from a point to the left part of the funnel
void assertFunnel() const
assertion for unit testing: is the Funnel in a consistent state?
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
boost::shared_ptr< Graph > ptr
void(* assert_hook2)(PolygonShortestPathsFS *, const frechet::reach::Placement *, const frechet::reach::Placement *)
void initReachability(Vertex_handle v)
set up reachability info for a triangulation vertex
placement of a diagonal point in free-space diagram When calculating valid placements in [buchin06]
compute Shortest-Paths-Tree on a polygon
PolygonShortestPaths(Triangulation &atri)
default constructor
TDS::Face_circulator Face_circulator
a circulating iterator
virtual bool updateSPSegment(Vertex_handle prev, Vertex_handle v)
called whenever a ne segment is added to the shortest path tree; hook for derived classes
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
int findTangent(Vertex_handle v) const
find a tangent from a point to the funnel
const Funnel & getFunnel() const
for debugging only: access to funnel
frechet::reach::Graph::ptr validPlacements
result: holds the valid placements on return