Detailed Description

Guibas' Algorithm with additional Free-Space computation.

Whenever a new point is added to the SP tree, we calculate (incrementally) Free-Space reachability.

For that purpose, Vertex_base contains additional data members to store free-space and reachability information.

Some points are marked as "Target" points. When they are reached, we have discovered a "valid placmenent" which is recorded in a rechability graph.

Author: Peter Schäfer

Definition at line 184 of file shortest_paths.h.

#include <shortest_paths.h>

Inherits frechet::poly::PolygonShortestPaths.

Public Types
typedef void(*	assert_hook1) (PolygonShortestPathsFS *, Vertex_handle v, bool reachable)

typedef void(*	assert_hook2) (PolygonShortestPathsFS , const frechet::reach::Placement , const frechet::reach::Placement *)

Public Types inherited from frechet::poly::PolygonShortestPaths
typedef Triangulation::Vertex_handle	Vertex_handle

typedef Triangulation::Face_handle	Face_handle

typedef Triangulation::Face_circulator	Face_circulator

typedef Triangulation::Edge	Edge

typedef DoubleEndedQueue< Vertex_handle >	Funnel

Public Member Functions
	PolygonShortestPathsFS (Triangulation &atri)
	default constructor More...

void	findShortestPaths (Vertex_handle start_point, const frechet::reach::Placement *asource, QLineF d, double epsilon, frechet::reach::Graph::ptr validPlacements)

Public Member Functions inherited from frechet::poly::PolygonShortestPaths
	PolygonShortestPaths (Triangulation &atri)
	default constructor More...

Triangulation &	triangulation () const

void	findShortestPaths (Vertex_handle start_point)
	traverse the polygon and report found paths More...

Curve	find1ShortestPath (double p1, double p2)
	compute the shortest path between two points on the boundary of the polygon More...

virtual void	shortestPath ()
	callback-function when a new shortest-path has been found. derived classes hook in to perform additional computations More...

virtual void	undo ()
	callback-function when backtrcking derived classes hook in to perform additional computations More...

void	assertFunnel () const
	assertion for unit testing: is the Funnel in a consistent state? More...

const Funnel &	getFunnel () const
	for debugging only: access to funnel More...

Static Public Attributes
static assert_hook1	after_target_found = nullptr
	unit test and debugging hook function; called when a target vertex is found More...

static assert_hook2	after_placement_added = nullptr
	unit test and debugging hook function; called when a valid placement is updated More...

Protected Member Functions
void	initReachability (Vertex_handle v)
	set up reachability info for a triangulation vertex More...

void	propagateReachability (Vertex_handle v)
	update free-space and reachability info, called when a vertex is updated in the shortest-paths tree More...

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. We test whether the new vertex is a 'target' vertex, and if so, update its free-space data. Valid placements are updated. More...

Protected Member Functions inherited from frechet::poly::PolygonShortestPaths
void	search (Vertex_handle start_point, Face_handle f)
	compute the shortest-paths tree More...

void	search (Edge e)
	compute the shortest-paths tree More...

int	findTangent (Vertex_handle v) const
	find a tangent from a point to the funnel More...

int	findTangentLeft (int t1, int t2, Vertex_handle v) const
	find a tangent from a point to the left part of the funnel More...

int	findTangentRight (int t1, int t2, Vertex_handle v) const
	find a tangent from a point to the right part of the funnel More...

bool	isTangent (int t, Vertex_handle v) const
	tangent test More...

Private Attributes
const frechet::reach::Placement *	source
	source placement and More...

QLineF	d
	diagonal More...

double	epsilon
	free-space parameter epsilon More...

frechet::reach::Graph::ptr	validPlacements
	result: holds the valid placements on return More...

Additional Inherited Members
Static Public Member Functions inherited from frechet::poly::PolygonShortestPaths
template<typename Float >
static int	halfplaneTest (Vertex_handle a, Vertex_handle b, Vertex_handle p)
	half-plane test. More...

Protected Attributes inherited from frechet::poly::PolygonShortestPaths
Triangulation &	tri
	the Triangulation More...

Funnel	funnel
	the Funnel More...

Member Typedef Documentation

◆ assert_hook1

typedef void(* frechet::poly::PolygonShortestPathsFS::assert_hook1) (PolygonShortestPathsFS *, Vertex_handle v, bool reachable)

Definition at line 237 of file shortest_paths.h.

◆ assert_hook2

typedef void(* frechet::poly::PolygonShortestPathsFS::assert_hook2) (PolygonShortestPathsFS *, const frechet::reach::Placement *, const frechet::reach::Placement *)

Definition at line 238 of file shortest_paths.h.

Constructor & Destructor Documentation

◆ PolygonShortestPathsFS()

PolygonShortestPathsFS::PolygonShortestPathsFS ( Triangulation & atri )

default constructor

Parameters

atri	the underlying triangulation

Definition at line 19 of file shortest_paths.cpp.

Member Function Documentation

◆ findShortestPaths()

void PolygonShortestPathsFS::findShortestPaths	(	Vertex_handle	start_point,
		const frechet::reach::Placement *	asource,
		QLineF	d,
		double	epsilon,
		frechet::reach::Graph::ptr	validPlacements
	)

Definition at line 24 of file shortest_paths.cpp.

◆ initReachability()

void PolygonShortestPathsFS::initReachability ( Vertex_handle v )

protected

set up reachability info for a triangulation vertex

Parameters

v	a vertex in the triangulation

Definition at line 178 of file shortest_paths.cpp.

◆ propagateReachability()

void PolygonShortestPathsFS::propagateReachability ( Vertex_handle v )

protected

update free-space and reachability info, called when a vertex is updated in the shortest-paths tree

Parameters

v	a vertex in the triangulation

Assumes v->L,B,R is already. calculated Calculate reachable intervals.

Definition at line 223 of file shortest_paths.cpp.

◆ updateSPSegment()

bool PolygonShortestPathsFS::updateSPSegment	(	Vertex_handle	prev,
		Vertex_handle	v
	)

overrideprotectedvirtual

hook function that is called by the shortest-tree search whenever a new segment is added to the tree. We test whether the new vertex is a 'target' vertex, and if so, update its free-space data. Valid placements are updated.

Parameters

prev	first vertex of the segment
v	second vertex of the segment

Returns: true if the tree segment has changed

TODO short-cut when the cell is unreachable i.e. when

Reimplemented from frechet::poly::PolygonShortestPaths.

Definition at line 97 of file shortest_paths.cpp.

Member Data Documentation

◆ after_placement_added

PolygonShortestPathsFS::assert_hook2 PolygonShortestPathsFS::after_placement_added = nullptr

static

unit test and debugging hook function; called when a valid placement is updated

Definition at line 242 of file shortest_paths.h.

◆ after_target_found

PolygonShortestPathsFS::assert_hook1 PolygonShortestPathsFS::after_target_found = nullptr

static

unit test and debugging hook function; called when a target vertex is found

Definition at line 240 of file shortest_paths.h.

◆ d

QLineF frechet::poly::PolygonShortestPathsFS::d

private

diagonal

Definition at line 190 of file shortest_paths.h.

◆ epsilon

double frechet::poly::PolygonShortestPathsFS::epsilon

private

free-space parameter epsilon

Definition at line 192 of file shortest_paths.h.

◆ source

const frechet::reach::Placement* frechet::poly::PolygonShortestPathsFS::source

private

source placement and

Definition at line 188 of file shortest_paths.h.

◆ validPlacements

frechet::reach::Graph::ptr frechet::poly::PolygonShortestPathsFS::validPlacements

private

result: holds the valid placements on return

Definition at line 194 of file shortest_paths.h.

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

include/frechet/poly/shortest_paths.h
src/frechet/poly/shortest_paths.cpp

Detailed Description

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Private Attributes

Additional Inherited Members

Member Typedef Documentation

◆ assert_hook1

◆ assert_hook2

Constructor & Destructor Documentation

◆ PolygonShortestPathsFS()

Member Function Documentation

◆ findShortestPaths()

◆ initReachability()

◆ propagateReachability()

◆ updateSPSegment()

Member Data Documentation

◆ after_placement_added

◆ after_target_found

◆ d

◆ epsilon

◆ source

◆ validPlacements