Detailed Description

a feasible-path for simple polygons.

Adds to the base class:

feasible path is constructed from a series of smaller sections ("fix points")
these fix points are extracted from the solution to the algorithm ("Combined Reachability Graphs")
find shortest paths in P an Q (mapped to diagonals)

Author: Peter Schäfer

Definition at line 24 of file poly_path.h.

#include <poly_path.h>

Public Member Functions
	PolygonFSPath (FreeSpace::ptr fs)
	constructor with free-space More...

void	update (const Graph::ptr result, double epsilon)
	compute a feasible path from the results of the simple polygon algorithm More...

Curve	findShortestPathP (int qa, int qb, Triangulation &tri)
	given a diagonal in Q, compute the mapped shortest-path in P. More...

Curve	findShortestPathQ (int pa, int pb, Triangulation &tri)
	given a diagonal in P, compute the mapped shortest-path in Q More...

Public Member Functions inherited from frechet::reach::FSPath
	FSPath (FreeSpace::ptr afs)
	constructor with free-space More...

virtual	~FSPath ()
	destructor More...

bool	empty () const

Curve	getPath (int i) const
	get the feasible path for display on screen. May be split into two parts. More...

void	mapFromP (Segment pseg, Curve result[2]) const
	for a line segment in P, find the mapped part of the feasible path More...

void	mapFromQ (Segment pseg, Curve result[2]) const

void	mapToP (Curve path[2]) const

void	mapToQ (Curve path[2]) const

Point	mapFromP (int p) const

Point	mapFromQ (int q) const

double	mapFromPToQ (int p) const

double	mapFromQToP (int q) const

const frechet::data::Interval &	left (int i, int j) const

const frechet::data::Interval &	bottom (int i, int j) const

const Curve &	fixPoints () const

void	clearReachability ()

virtual void	clear ()

void	calculateReachability (Point start, Point end, bool allow_wrap, double prec=PRECISION)
	update L^R and B from Free-Space diagram More...

void	update (Point start, double epsilon)
	compute a feasible path from the free-space diagram More...

Point	toPoint (Pointer segment)
	pick a point from a reachability interval More...

bool	isReachable (int i, int j, double prec=PRECISION) const
	follow the reachable intervals and test whether a point is reachable from the start More...

bool	isReachable (Point a, double prec=PRECISION) const
	follow the reachable intervals and test whether a point is reachable from the start More...

Point	startPoint () const

Private Types
typedef std::pair< int, int >	IndexPair

Private Member Functions
void	addFixPoint (int pi, int qi)
	add a fix point to the feasible path More...

void	addFixPoint (Point p)
	add a fix point to the feasible path More...

void	drillDown (Graph::ptr res)
	Drill down, starting from the solution Graph, replacing diagonals step by step. Until finally we have the outer border curves. More...

void	drillDown (Graph::ptr M, int k1, int k2)
	given a merged reachability Graph, drill down to the original graphs and find the fixed points of the feasible path More...

IndexPair	findSolutionConnectingPoints (Graph::ptr A, int i, Graph::ptr B) const
	given the solution of the simple polygon algorithm, drill down to the original graphs and find the fixed points of the feasible path. The solution is the transitive closure G = ABA More...

int	findConnectingPoint (Graph::ptr A, int ia, Graph::ptr B, int ib) const
	given two reachability graphs, drill down to the original graphs and find the fixed points of the feasible path. More...

Interval	mapInterval (Orientation o, int p) const
	map a node of a reachability graph to the associated free-space interval More...

double	mapPoint (Orientation o, int p) const
	map a node of a reachability graph to a point in the free-space interval. More...

Static Private Member Functions
static bool	is_consistent (Curve fix)
	for debugging only; test the consistency of a feasible path. It must be monotone in both x- and y-coordinates More...

Private Attributes
GraphModel::ptr	gmodel
	model for mapping free-space intervals to reachability graph nodes More...

Additional Inherited Members
Public Types inherited from frechet::reach::FSPath
typedef boost::shared_ptr< FSPath >	ptr
	smart pointer to an FSPath object More...

Static Public Member Functions inherited from frechet::reach::FSPath
static Interval	opposite (const Interval &LR, const Interval &RF)

static void	propagate (const Interval &RF, const Interval &TF, const Interval &LR, const Interval &BR, Interval &RR, Interval &TR)
	propagate the reachable intervals within one cell. from bottom and left to right and top More...

Static Public Attributes inherited from frechet::reach::FSPath
static const double	PRECISION = 1e-9
	floating point precision More...

Protected Member Functions inherited from frechet::reach::FSPath
	FSPath ()
	constructor for derived classes only More...

void	calculatePath ()
	calculate the feasible path More...

void	findPathSegment (Point a, Point b, Curve curve[2], int &cc)
	compute one segment of the feasible path. THe path is completed from top-right backwards to bottom-left. More...

bool	propagateHorizontalEdge (Point a, double bx, double prec=PRECISION)
	propagate the reachable intervals along the horizontal axis More...

bool	propagateVerticalEdge (Point a, double by, double prec=PRECISION)
	propagate the reachable intervals along the vertical axis More...

void	propagateInner (int i, int j, double bx, double by)
	propagate the reachable intervals within one cell. The cell is located in the inner part of the free-space diagram. More...

void	propagateBottom (int i, int j, double bx, double by)
	propagate the reachable intervals within one cell. The cell is located at the bottom of the free-space diagram. More...

int	next_hor (int i)

int	next_vert (int j)

bool	left_contains (int i, int j, double y, double prec=PRECISION) const
	test the reachability interval on the left of a cell More...

bool	bottom_contains (int i, int j, double x, double prec=PRECISION) const
	test the reachability interval on the bottom of a cell More...

void	propagateColumn (int i, int j0, double bx, double by, bool allow_wrap)
	propagate the reachable intervals along a column of the free-space diagram. More...

void	propagateBottom (int i, int j0, double bx, double by, bool allow_wrap)
	propagate the reachable intervals along a bottom row of the free-space diagram. More...

Static Protected Member Functions inherited from frechet::reach::FSPath
static double	mapToSegment (double a, Point p1, Point p2)
	map a relative offset to a line segment. For values in [0..1] the resulting point is one the line segment. For value <0 or >1 the resulting point would be off the line segment. More...

static void	append (std::vector< double > &map, double x)
	append a value to a vector, avoiding duplicates More...

static int	binSearchX (const Curve &curve, int x)
	find a point by its x coordinate More...

static int	binSearchY (const Curve &curve, int y)
	find a point by its y coordinate More...

static void	copy (Curve &dest, const Curve &source, int i, int j)
	copy parts of a curve More...

static bool	are_consistent (Curve path0, Curve path1, int n, int m)
	test if two curves are consistent with being a feasible path. Both curves must be monotone (asecning x and y-coordinates), wrap at the right or top edge. Used for debuggin and unit tests. More...

Protected Attributes inherited from frechet::reach::FSPath
FreeSpace::ptr	fs
	underlying free-space More...

bool	wrapTop
	free-space wraps at top, Q is closed More...

bool	wrapRight
	free-space wraps right, P is closed More...

Array2D< Interval >	LR
	reachable intervals More...

Array2D< Interval >	BR

Curve	fix
	fix points More...

Curve	path [2]
	Path curves(s) More...

Member Typedef Documentation

◆ IndexPair

typedef std::pair<int, int> frechet::poly::PolygonFSPath::IndexPair

private

Definition at line 100 of file poly_path.h.

Constructor & Destructor Documentation

◆ PolygonFSPath()

PolygonFSPath::PolygonFSPath ( FreeSpace::ptr fs )

constructor with free-space

Parameters

fs	the underlying free-space

Definition at line 11 of file poly_path.cpp.

Member Function Documentation

◆ addFixPoint() [1/2]

void PolygonFSPath::addFixPoint	(	int	pi,
		int	qi
	)

private

add a fix point to the feasible path

Parameters

pi	vertex index in P
qi	vertex index in Q

Definition at line 133 of file poly_path.cpp.

◆ addFixPoint() [2/2]

void PolygonFSPath::addFixPoint ( Point p )

private

add a fix point to the feasible path

Parameters

p	point in free-space

Definition at line 157 of file poly_path.cpp.

◆ drillDown() [1/2]

void PolygonFSPath::drillDown ( Graph::ptr res )

private

Drill down, starting from the solution Graph, replacing diagonals step by step. Until finally we have the outer border curves.

Parameters

res	solution to simple polygons algorithm

Definition at line 35 of file poly_path.cpp.

◆ drillDown() [2/2]

void PolygonFSPath::drillDown	(	Graph::ptr	M,
		int	k1,
		int	k2
	)

private

given a merged reachability Graph, drill down to the original graphs and find the fixed points of the feasible path

Parameters

M	a reachability graph that is the transitive closusre of thow other Graphs
k1	left start node
k2	right node

Definition at line 76 of file poly_path.cpp.

◆ findConnectingPoint()

int PolygonFSPath::findConnectingPoint	(	Graph::ptr	A,
		int	ia,
		Graph::ptr	B,
		int	ib
	)		const

private

given two reachability graphs, drill down to the original graphs and find the fixed points of the feasible path.

Parameters

A	combined reachability graph
ia	exit node in A
B	combined reachability graph
ib	entry node in B

Returns: the connecting node of a feasible path

Definition at line 99 of file poly_path.cpp.

◆ findShortestPathP()

Curve PolygonFSPath::findShortestPathP	(	int	qa,
		int	qb,
		Triangulation &	tri
	)

given a diagonal in Q, compute the mapped shortest-path in P.

Parameters

qa	a vertex in Q
qb	a vertex in Q
tri	triangulation of P

Returns: shortest path that maps to the diagonal

Definition at line 236 of file poly_path.cpp.

◆ findShortestPathQ()

Curve PolygonFSPath::findShortestPathQ	(	int	pa,
		int	pb,
		Triangulation &	tri
	)

given a diagonal in P, compute the mapped shortest-path in Q

To map a polygon edge to a sequence in Q, use Grid::mapToPoint(mapQ(p1),mapQ(p2)) instead.

Parameters

pa	a vertex in P
pb	a vertex in P
tri	triangulation of Q

Returns: shortest path that maps to the diagonal

Definition at line 248 of file poly_path.cpp.

◆ findSolutionConnectingPoints()

PolygonFSPath::IndexPair PolygonFSPath::findSolutionConnectingPoints	(	Graph::ptr	A,
		int	i,
		Graph::ptr	B
	)		const

private

given the solution of the simple polygon algorithm, drill down to the original graphs and find the fixed points of the feasible path. The solution is the transitive closure G = A*B*A

Parameters

A	reachability graph
i	start node of feasible path
B	combined reachability graph

Returns: two connecting nodes

Definition at line 188 of file poly_path.cpp.

◆ is_consistent()

bool PolygonFSPath::is_consistent ( Curve fix )

staticprivate

for debugging only; test the consistency of a feasible path. It must be monotone in both x- and y-coordinates

Parameters

fix	fix points of the feasible path

Returns: true if the curve is monotone

Definition at line 263 of file poly_path.cpp.

◆ mapInterval()

Interval PolygonFSPath::mapInterval	(	Orientation	o,
		int	p
	)		const

private

map a node of a reachability graph to the associated free-space interval

Parameters

o	horizontal or vertical
p	node index

Returns: the associated free-space interval

Maybe this method should be moved to GraphModel.

Definition at line 175 of file poly_path.cpp.

◆ mapPoint()

double PolygonFSPath::mapPoint	(	Orientation	o,
		int	p
	)		const

private

map a node of a reachability graph to a point in the free-space interval.

Parameters

o	horizontal or vertical
p	node index

Returns: a point in the associated free-space interval

See poly::Algorithm::pickIntervalPoint.

Definition at line 183 of file poly_path.cpp.

◆ update()

void PolygonFSPath::update	(	const Graph::ptr	result,
		double	epsilon
	)

compute a feasible path from the results of the simple polygon algorithm

Parameters

result	a reachability graph
epsilon	free-space parameter epsilon

Definition at line 17 of file poly_path.cpp.

Member Data Documentation

◆ gmodel

GraphModel::ptr frechet::poly::PolygonFSPath::gmodel

private

model for mapping free-space intervals to reachability graph nodes

Definition at line 28 of file poly_path.h.

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

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

Detailed Description

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Member Typedef Documentation

◆ IndexPair

Constructor & Destructor Documentation

◆ PolygonFSPath()

Member Function Documentation

◆ addFixPoint() [1/2]

◆ addFixPoint() [2/2]

◆ drillDown() [1/2]

◆ drillDown() [2/2]

◆ findConnectingPoint()

◆ findShortestPathP()

◆ findShortestPathQ()

◆ findSolutionConnectingPoints()

◆ is_consistent()

◆ mapInterval()

◆ mapPoint()

◆ update()

Member Data Documentation

◆ gmodel