Detailed Description

Calculates a feasible path in the Free-Space given a start point (0,0) and an end point (n-1,m-1).

Maintains an Array of L^R and B^R intervals, that are reachable from the starting point.

Allows arbitrary start points (x,0), or (0,y) wrap around right / top border if curves are closed.

The feasible path, as displayed on screen, may contain two parts (because we fold the double-free-space into one).

Floating point precision is an issue: Free-Space values are in [0..1]

Interval in Reachability structure are shifted in [i..i+1] introducing potential rounding errors. Be careful to compare value either

without offset
with identically calculated offset

Avoid calculating offsets back and fort.

Alternatively, use a fixed point representation like FixedPoint { int i; double mantissa; }

Author: Peter Schäfer

Definition at line 44 of file fs_path.h.

#include <fs_path.h>

Inherited by frechet::poly::PolygonFSPath.

Public Types
typedef boost::shared_ptr< FSPath >	ptr
	smart pointer to an FSPath object More...

Public Member Functions
	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

Static Public Member Functions
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
static const double	PRECISION = 1e-9
	floating point precision More...

Protected Member Functions
	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
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
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

◆ ptr

typedef boost::shared_ptr<FSPath> frechet::reach::FSPath::ptr

smart pointer to an FSPath object

Definition at line 65 of file fs_path.h.

Constructor & Destructor Documentation

◆ FSPath() [1/2]

FSPath::FSPath ( FreeSpace::ptr afs )

constructor with free-space

Parameters

afs	the underlying free-space

Definition at line 26 of file fs_path.cpp.

◆ ~FSPath()

virtual frechet::reach::FSPath::~FSPath ( )

inlinevirtual

destructor

Definition at line 75 of file fs_path.h.

◆ FSPath() [2/2]

FSPath::FSPath ( )

protected

constructor for derived classes only

Definition at line 19 of file fs_path.cpp.

Member Function Documentation

◆ append()

void FSPath::append	(	std::vector< double > &	map,
		double	x
	)

staticprotected

append a value to a vector, avoiding duplicates

Parameters

map	a vector of values
x	new value

Definition at line 49 of file fs_path.cpp.

◆ are_consistent()

bool FSPath::are_consistent	(	Curve	path0,
		Curve	path1,
		int	n,
		int	m
	)

staticprotected

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.

Parameters

path0	first part of feasible path
path1	second part of feasible path
n	number of vertexes on P
m	number of vertexes on Q

Returns: true, if the two parts are properly monotone

Definition at line 845 of file fs_path.cpp.

◆ binSearchX()

int FSPath::binSearchX	(	const Curve &	curve,
		int	x
	)

staticprotected

find a point by its x coordinate

Parameters

curve	a polygonal curve, assumed to be sorted
x	x-coordinate of a point

Returns: index of x, or -i-1 for the index where x should be inserted

Definition at line 158 of file fs_path.cpp.

◆ binSearchY()

int FSPath::binSearchY	(	const Curve &	curve,
		int	y
	)

staticprotected

find a point by its y coordinate

Parameters

curve	a polygonal curve, assumed to be sorted
y	y-coordinate of a point

Returns: index of y, or -i-1 for the index where x should be inserted

Definition at line 174 of file fs_path.cpp.

◆ bottom()

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

inline

Definition at line 114 of file fs_path.h.

◆ bottom_contains()

bool FSPath::bottom_contains	(	int	i,
		int	j,
		double	x,
		double	prec = `PRECISION`
	)		const

protected

test the reachability interval on the bottom of a cell

Parameters

i	column in free-space
j	row in free-space
x	point to test
prec	numerical precision for comparing intervals

Returns: true if x is contained in the bottom reachable interval in cell (i,j)

Definition at line 645 of file fs_path.cpp.

◆ calculatePath()

void FSPath::calculatePath ( )

protected

calculate the feasible path

Definition at line 674 of file fs_path.cpp.

◆ calculateReachability()

void FSPath::calculateReachability	(	Point	start,
		Point	end,
		bool	allow_wrap,
		double	prec = `PRECISION`
	)

update L^R and B from Free-Space diagram

Parameters

start	start location in free-space diagram (column and row)
end	destination location in free-space diagram (column and row)
allow_wrap	allow to wrap at edges of free-space
prec	numerical precision for comparing intervals

Definition at line 429 of file fs_path.cpp.

◆ clear()

void FSPath::clear ( )

virtual

Definition at line 222 of file fs_path.cpp.

◆ clearReachability()

void FSPath::clearReachability ( )

Definition at line 213 of file fs_path.cpp.

◆ copy()

void FSPath::copy	(	Curve &	dest,
		const Curve &	source,
		int	i,
		int	j
	)

staticprotected

copy parts of a curve

Parameters

dest	destination curve
source	input curve
i	start index to copy from
j	end index

Definition at line 190 of file fs_path.cpp.

◆ empty()

bool frechet::reach::FSPath::empty ( ) const

inline

Returns: true, if there is no feasible path

Definition at line 80 of file fs_path.h.

◆ findPathSegment()

void FSPath::findPathSegment	(	Point	a,
		Point	b,
		Curve	curve[2],
		int &	cc
	)

protected

compute one segment of the feasible path. THe path is completed from top-right backwards to bottom-left.

Parameters

a	destination point (bottom-left)
b	start point (top-right)
curve	holds the new segments on return
cc	holds the number of curve segments on return

Definition at line 705 of file fs_path.cpp.

◆ fixPoints()

const Curve& frechet::reach::FSPath::fixPoints ( ) const

inline

Definition at line 118 of file fs_path.h.

◆ getPath()

Curve FSPath::getPath ( int i ) const

get the feasible path for display on screen. May be split into two parts.

Parameters

i 0 or 1

Returns: first or second part of the feasible path

Definition at line 36 of file fs_path.cpp.

◆ isReachable() [1/2]

bool frechet::reach::FSPath::isReachable	(	int	i,
		int	j,
		double	prec = `PRECISION`
	)		const

follow the reachable intervals and test whether a point is reachable from the start

Parameters

i	column in free-space
j	row in free-space
prec	numerical precision for comparing intervals

Returns: true, if q is reachable from p

◆ isReachable() [2/2]

bool frechet::reach::FSPath::isReachable	(	Point	a,
		double	prec = `PRECISION`
	)		const

follow the reachable intervals and test whether a point is reachable from the start

Parameters

a	point in free-space
prec	numerical precision for comparing intervals

Returns: true, if q is reachable from p

◆ left()

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

inline

Definition at line 110 of file fs_path.h.

◆ left_contains()

bool FSPath::left_contains	(	int	i,
		int	j,
		double	y,
		double	prec = `PRECISION`
	)		const

protected

test the reachability interval on the left of a cell

Parameters

i	column in free-space
j	row in free-space
y	point to test
prec	numerical precision for comparing intervals

Returns: true if y is contained in the left reachable interval in cell (i,j)

Definition at line 637 of file fs_path.cpp.

◆ mapFromP() [1/2]

void FSPath::mapFromP	(	Segment	pseg,
		Curve	result[2]
	)		const

for a line segment in P, find the mapped part of the feasible path

Parameters

pseg	line segment in P
result	on return, holds the feasible path segment that maps to the P line segment

Definition at line 55 of file fs_path.cpp.

◆ mapFromP() [2/2]

Point FSPath::mapFromP ( int p ) const

Definition at line 822 of file fs_path.cpp.

◆ mapFromPToQ()

double FSPath::mapFromPToQ ( int p ) const

Definition at line 811 of file fs_path.cpp.

◆ mapFromQ() [1/2]

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

Definition at line 90 of file fs_path.cpp.

◆ mapFromQ() [2/2]

Point FSPath::mapFromQ ( int q ) const

Definition at line 833 of file fs_path.cpp.

◆ mapFromQToP()

double FSPath::mapFromQToP ( int q ) const

Definition at line 817 of file fs_path.cpp.

◆ mapToP()

void FSPath::mapToP ( Curve path[2] ) const

Definition at line 125 of file fs_path.cpp.

◆ mapToQ()

void FSPath::mapToQ ( Curve path[2] ) const

Definition at line 142 of file fs_path.cpp.

◆ mapToSegment()

double FSPath::mapToSegment	(	double	a,
		Point	p1,
		Point	p2
	)

staticprotected

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.

Parameters

a	relative offset on line segment
p1	start of line
p2	end of line

Returns: mapped point

Definition at line 44 of file fs_path.cpp.

◆ next_hor()

int FSPath::next_hor ( int i )

protected

Returns: the next column, possible wrapping around the right edge

Definition at line 198 of file fs_path.cpp.

◆ next_vert()

int FSPath::next_vert ( int j )

protected

Returns: the next row, possible wrapping around the top edge

Definition at line 205 of file fs_path.cpp.

◆ opposite()

Interval FSPath::opposite	(	const Interval &	LR,
		const Interval &	RF
	)

static

Calculate reachability interval opposite to a given interval.

Parameters

LR	Left (or bottom) Rechability
RF	Right (or top) Free-Space

Returns: result RR Right Reachability

Definition at line 398 of file fs_path.cpp.

◆ propagate()

void FSPath::propagate	(	const Interval &	RF,
		const Interval &	TF,
		const Interval &	LR,
		const Interval &	BR,
		Interval &	RR,
		Interval &	TR
	)

static

propagate the reachable intervals within one cell. from bottom and left to right and top

Parameters

RF	free-space interval on the right edge of the cell
TF	free-space interval on the top edge of the cell
LR	reachable interval on the left edge
BR	reachable interval on the bottom edge
RR	holds on return the reachable interval on the right edge
TR	holds on return the reachable interval on the top edge

Definition at line 406 of file fs_path.cpp.

◆ propagateBottom() [1/2]

void FSPath::propagateBottom	(	int	i,
		int	j,
		double	bx,
		double	by
	)

protected

propagate the reachable intervals within one cell. The cell is located at the bottom of the free-space diagram.

Parameters

i	column in free-space
j	row in free-space
bx	x-coordinate of destination point
by	y-coordinate of destination point

Definition at line 367 of file fs_path.cpp.

◆ propagateBottom() [2/2]

void FSPath::propagateBottom	(	int	i,
		int	j0,
		double	bx,
		double	by,
		bool	allow_wrap
	)

protected

propagate the reachable intervals along a bottom row of the free-space diagram.

Parameters

i	column in free-space
j0	bottom row in free-space
bx	x-coordinate of destination point
by	y-coordinate of destination point
allow_wrap	if true, wrap at the top edge

Definition at line 605 of file fs_path.cpp.

◆ propagateColumn()

void FSPath::propagateColumn	(	int	i,
		int	j0,
		double	bx,
		double	by,
		bool	allow_wrap
	)

protected

propagate the reachable intervals along a column of the free-space diagram.

Parameters

i	column in free-space
j0	bottom row in free-space
bx	x-coordinate of destination point
by	y-coordinate of destination point
allow_wrap	if true, wrap at the top edge

Definition at line 574 of file fs_path.cpp.

◆ propagateHorizontalEdge()

bool FSPath::propagateHorizontalEdge	(	Point	a,
		double	bx,
		double	prec = `PRECISION`
	)

protected

propagate the reachable intervals along the horizontal axis

Parameters

a	start point
bx	destination coordinate
prec	numerical precision for comparing intervals

Returns: false, if the start point is not reachable

Definition at line 229 of file fs_path.cpp.

◆ propagateInner()

void FSPath::propagateInner	(	int	i,
		int	j,
		double	bx,
		double	by
	)

protected

propagate the reachable intervals within one cell. The cell is located in the inner part of the free-space diagram.

Parameters

i	column in free-space
j	row in free-space
bx	x-coordinate of destination point,
by	y-coordinate of destination point

Definition at line 321 of file fs_path.cpp.

◆ propagateVerticalEdge()

bool FSPath::propagateVerticalEdge	(	Point	a,
		double	by,
		double	prec = `PRECISION`
	)

protected

propagate the reachable intervals along the vertical axis

Parameters

a	start point
by	destination coordinate
prec	numerical precision for comparing intervals

Returns: false, if the start point is not reachable

Definition at line 275 of file fs_path.cpp.

◆ startPoint()

Point frechet::reach::FSPath::startPoint ( ) const

inline

Returns: start of feasible path

Definition at line 168 of file fs_path.h.

◆ toPoint()

Point FSPath::toPoint ( Pointer segment )

pick a point from a reachability interval

Parameters

segment interval of a reachability structure

Returns: a point within the interval, a candidate for a feasible path

Definition at line 541 of file fs_path.cpp.

◆ update()

void FSPath::update	(	Point	start,
		double	epsilon
	)

compute a feasible path from the free-space diagram

Parameters

start	start point
epsilon

Definition at line 484 of file fs_path.cpp.

Member Data Documentation

◆ BR

Array2D<Interval> frechet::reach::FSPath::BR

protected

Definition at line 54 of file fs_path.h.

◆ fix

Curve frechet::reach::FSPath::fix

protected

fix points

Definition at line 56 of file fs_path.h.

◆ fs

FreeSpace::ptr frechet::reach::FSPath::fs

protected

underlying free-space

Definition at line 48 of file fs_path.h.

◆ LR

Array2D<Interval> frechet::reach::FSPath::LR

protected

reachable intervals

Definition at line 54 of file fs_path.h.

◆ path

Curve frechet::reach::FSPath::path[2]

protected

Path curves(s)

Definition at line 58 of file fs_path.h.

◆ PRECISION

const double FSPath::PRECISION = 1e-9

static

floating point precision

Definition at line 61 of file fs_path.h.

◆ wrapRight

bool frechet::reach::FSPath::wrapRight

protected

free-space wraps right, P is closed

Definition at line 52 of file fs_path.h.

◆ wrapTop

bool frechet::reach::FSPath::wrapTop

protected

free-space wraps at top, Q is closed

Definition at line 50 of file fs_path.h.

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

include/frechet/reachability/fs_path.h
src/frechet/reachability/fs_path.cpp

Detailed Description

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ ptr

Constructor & Destructor Documentation

◆ FSPath() [1/2]

◆ ~FSPath()

◆ FSPath() [2/2]

Member Function Documentation

◆ append()

◆ are_consistent()

◆ binSearchX()

◆ binSearchY()

◆ bottom()

◆ bottom_contains()

◆ calculatePath()

◆ calculateReachability()

◆ clear()

◆ clearReachability()

◆ copy()

◆ empty()

◆ findPathSegment()

◆ fixPoints()

◆ getPath()

◆ isReachable() [1/2]

◆ isReachable() [2/2]

◆ left()

◆ left_contains()

◆ mapFromP() [1/2]

◆ mapFromP() [2/2]

◆ mapFromPToQ()

◆ mapFromQ() [1/2]

◆ mapFromQ() [2/2]

◆ mapFromQToP()

◆ mapToP()

◆ mapToQ()

◆ mapToSegment()

◆ next_hor()

◆ next_vert()

◆ opposite()

◆ propagate()

◆ propagateBottom() [1/2]

◆ propagateBottom() [2/2]

◆ propagateColumn()

◆ propagateHorizontalEdge()

◆ propagateInner()

◆ propagateVerticalEdge()

◆ startPoint()

◆ toPoint()

◆ update()

Member Data Documentation

◆ BR

◆ fix

◆ fs

◆ LR

◆ path

◆ PRECISION

◆ wrapRight

◆ wrapTop