Detailed Description

class for computing reachability structures and graphs.

Classes
class	BoundarySegment
	boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSpace (bottom.left,top, or right) More...

struct	BoundsIndex
	mapping within a GraphModel More...

class	CalculateTask
	a sub-task, computing a region of the reachability structure More...

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

class	Graph
	Represents a Reachability Graph. Vertices correspond to intervals in the reachability structure, broken down to the most fine-grained intervals. More...

class	GraphCL
	Reachability Graph with additional storage in GPU memory. More...

class	GraphModel
	model the mapping of free-space intervals to nodes in a frechet::reach::Graph. More...

class	GraphModelAxis
	manages a mapping between free-space intervals (continous, floating point) to reachability graph nodes (discrete, integer) More...

struct	IndexRange
	a range of node indices in a Reachability Graph More...

class	MergeTask
	a sub-taks, performing the merging of two reachability structures More...

struct	Placement
	placement of a diagonal point in free-space diagram When calculating valid placements in [buchin06] More...

struct	PointerInterval
	describes l,h pointers. Both pointers are assumed to point into the same rectangle section (right-top OR bottom-left) More...

class	Structure
	The Reachability Structure; maintains a list of intervals on the border of Free Space, along with pointers to reachable intervals on the opposite side. More...

class	StructureIterator
	The StructureIterator class. More...

class	StructureTask
	task object for parallel execution. When the reachability structur is computed in parallel threads, we create a tree of task objects that are distributed over threads. More...

Typedefs
typedef BoundarySegment *	Pointer
	(dumb) pointer to a BoundarySegment object More...

typedef data::LinkedList< BoundarySegment >	BoundaryList
	a double-linked list of reachability segments. makes up one of the four edges of a reachability structure More...

typedef boost::shared_ptr< Graph >	GraphPtr

typedef std::vector< frechet::reach::Placement >	Placements
	a list of Placement objects More...

Enumerations
enum	Type : uint8_t { NON_ACCESSIBLE, REACHABLE, SEE_THROUGH }
	Segment Types. More...

enum	Orientation : uint8_t { HORIZONTAL =0, VERTICAL =1 }
	Segment Orientation. More...

enum	Direction : uint8_t { FIRST =0, SECOND =1, BOTTOM_LEFT = FIRST, RIGHT_TOP = SECOND, FORWARD = RIGHT_TOP, BACKWARD = BOTTOM_LEFT, COUNTER_CLOCKWISE = RIGHT_TOP, CLOCKWISE = BOTTOM_LEFT }
	direction of a Pointer inside the reachability structure. More...

enum	Bias : uint8_t { UNBIASED =0, LOWER =1, UPPER =2, LOWER_UPPER =3 }
	bias of a GraphModel boundary (how shall we explain this?) More...

Functions
Orientation	opposite (Orientation ori)

Orientation &	operator++ (Orientation &ori)
	pre-increment an orientation variable. Note that an orientation variable can only be incremented once from HORIZONTAL to VERTICAL. Incrementing VERTICAL causes an undefined result. More...

Direction	opposite (Direction dir)

Direction &	operator++ (Direction &dir)
	pre-increment a direction variable. Note that a direction variable can only be incremented once from FIRST to SECOND. Incrementing SECOND causes an undefined result. More...

Pointer	min (const Pointer a, const Pointer b)
	minimum of two reachability intervals; compare lower bound, then upper bound More...

Pointer	min (const PointerInterval &ival)
	minimum of two reachability intervals; compare lower bound, then upper bound More...

Pointer	min (const PointerInterval &a, const PointerInterval &b)
	minimum of two reachability intervals; compare lower bound, then upper bound More...

Pointer	max (const Pointer a, const Pointer b)
	maximum of two reachability intervals; compare lower bound, then upper bound More...

Pointer	max (const PointerInterval &ival)
	maximum of two reachability intervals; compare lower bound, then upper bound More...

Pointer	max (const PointerInterval &a, const PointerInterval &b)
	maximum of two reachability intervals; compare lower bound, then upper bound More...

int	compare_interval (Pointer a, Pointer b)
	compare two pointers in the same part of a reachability structure (either right-top, or bottom-left) More...

int	compare_interval (const PointerInterval &ival)
	compare two pointers in the same part of a reachability structure (either right-top, or bottom-left) More...

bool	empty_interval (Pointer a, Pointer b)
	test intersection of intervals More...

bool	empty_interval (const PointerInterval &ival)
	test intersection of intervals More...

bool	empty_see_through_interval (Pointer p)
	test intersection of intervals. Assumes a SEE_THROUGH segment. More...

int	compare_pointers (Pointer a, Pointer b)
	compare two pointers on opposite parts of a reachability structure (eitehr left->right-top, or bottom->right-top) More...

std::ostream &	operator<< (std::ostream &out, const BoundaryList &list)
	print operator for debugging More...

GraphPtr	newGraph (const GraphModel::ptr model)

GraphPtr	newGraph (const GraphModel::ptr model, IndexRange hmask)

GraphPtr	newGraph (const GraphModel::ptr model, Structure &str)

Bias	operator\| (Bias a, Bias b)
	union operator More...

Bias &	operator\|= (Bias &a, Bias b)
	union operator More...

std::ostream &	operator<< (std::ostream &out, const Structure &str)
	print operator used for debugging; prints diagnostic info about a reachability structure More...

Typedef Documentation

◆ BoundaryList

typedef data::LinkedList<BoundarySegment> frechet::reach::BoundaryList

a double-linked list of reachability segments. makes up one of the four edges of a reachability structure

Definition at line 461 of file boundary.h.

◆ GraphPtr

typedef boost::shared_ptr<Graph> frechet::reach::GraphPtr

Definition at line 14 of file graph_m4ri.h.

◆ Placements

typedef std::vector<frechet::reach::Placement> frechet::reach::Placements

a list of Placement objects

Definition at line 144 of file graph_model.h.

◆ Pointer

typedef BoundarySegment* frechet::reach::Pointer

(dumb) pointer to a BoundarySegment object

Definition at line 55 of file boundary.h.

Enumeration Type Documentation

◆ Bias

enum frechet::reach::Bias : uint8_t

bias of a GraphModel boundary (how shall we explain this?)

Enumerator
UNBIASED	boundary is not inclusive to any interval
LOWER	boundary is inclusive to adjacent lower interval
UPPER	boundary is inclusive to adjacent upper interval
LOWER_UPPER

Definition at line 150 of file graph_model.h.

◆ Direction

enum frechet::reach::Direction : uint8_t

direction of a Pointer inside the reachability structure.

Direction describes three (related) concepts:

the two parts of a reachability cell: bottom-left segement and right-top segment
the direction of an l,h pointer forward pointer = pointing from bottom-left INTO right-top backward pointer pointer from right-top segment BACK INTO bottom-left
the orientation of an l,h interval, or traversal sequence of segments
- counter-clockwise: start at lower right corner, traverse right edge bottom-up, bend at top-right corner, traverse top edge from right to left, finish at top-left corner.
- clockwise: start at lower right corner, traverse bottom edge from right to left, bend and lower left corner, then left edge bottom up, finish at top-left corner.
As you can see, vertical edges are traversed bottom-up. Horizontal edges are traversed left-to-right.

Each BoundarySegment knows its Direction. The l,h pointers of a segement always point into the opposite segment.

   end            <-- TOP = part of SECOND segment
   traversal      <-- traverse COUNTER-CLOCKWISE
       O-----------+-----------+-----------+-----------+-----------+
       |               /                                           |
       |              /                                           ^|
       +             /                                           / |
       |            /                                          /   |
       |           / BACKWARD pointer                        /     |
   ^   +          /                                        /       +  ^
   |   |         /                                       /         |  | traverse COUNTER-CLOCKWISE
       |        /                                      /           |
  LEFT +       /                                     /             + RIGHT
 =FIRST|      /                                    /               | = part of SECOND segment
       |     /                                   /                 |
       +    /                                  /                   +
       |   /                                 /                     |
       |  /                                /                       |
       + v                               /                         +
       |                               /                           |
       |                             /                             |
       +                           /   FORWARD pointer             +
       |                         /                                 |
       |                       /                                   |
       +                     /                                     +
       |                   /                                       |
       |                 /                                         |
       +-----------+-----------+-----------+-----------+-----------O start traversal

                     <--  BOTTOM = part of FIRST segment
                     <--  traverse CLOCKWISE

Enumerator
FIRST	first segment = bottom and left edge
SECOND	second segment = right and top edge
BOTTOM_LEFT	bottom and left part of the reachability structure
RIGHT_TOP	right and top part of the reachability structure
FORWARD	forward l,h pointer = from first INTO second segment
BACKWARD	backward l,h pointer = from second INTO first segment
COUNTER_CLOCKWISE	counter-clockwise interval (right-then-top)
CLOCKWISE	clockwise interval (bottom-then-left)

Definition at line 115 of file boundary.h.

◆ Orientation

enum frechet::reach::Orientation : uint8_t

Segment Orientation.

some segments are horizontal, others are vertical.

Enumerator
HORIZONTAL
VERTICAL

Definition at line 31 of file boundary.h.

◆ Type

enum frechet::reach::Type : uint8_t

Segment Types.

each segment of a reachability structure is labelled with its reachability status

See also: [alt95]

Enumerator
NON_ACCESSIBLE	non-accesible. no interval is reachable from this one
REACHABLE	reachable: other intervals are reachable
SEE_THROUGH	see-through: other interals are visible with a straight line

Definition at line 17 of file boundary.h.

Function Documentation

◆ compare_interval() [1/2]

int frechet::reach::compare_interval	(	Pointer	a,
		Pointer	b
	)

compare two pointers in the same part of a reachability structure (either right-top, or bottom-left)

we assume that both intervals are on the same Direction

Parameters

a	pointer to a segment, in the same part as b
b	pointer to a segment, in the same part as a

Returns: <0 if a<b, ==0 if a==b, >0 if a>b

Definition at line 148 of file boundary.cpp.

◆ compare_interval() [2/2]

int frechet::reach::compare_interval ( const PointerInterval & ival )

compare two pointers in the same part of a reachability structure (either right-top, or bottom-left)

Parameters

ival	a segment interval

Returns: <0 if a<b, ==0 if a==b, >0 if a>b

Definition at line 186 of file boundary.cpp.

◆ compare_pointers()

int frechet::reach::compare_pointers	(	Pointer	a,
		Pointer	b
	)

compare two pointers on opposite parts of a reachability structure (eitehr left->right-top, or bottom->right-top)

assumes pointers on different directions

Parameters

a	pointer to a segment, in the opposite part as b
b	pointer to a segment, in the opposite part as a

Returns: <0 if a<b, ==0 if a==b, >0 if a>b

Definition at line 214 of file boundary.cpp.

◆ empty_interval() [1/2]

bool frechet::reach::empty_interval	(	Pointer	a,
		Pointer	b
	)

test intersection of intervals

Parameters

a	pointer to a segment, in the same part as b
b	pointer to a segment, in the same part as a

Returns: true if a>b

Definition at line 191 of file boundary.cpp.

◆ empty_interval() [2/2]

bool frechet::reach::empty_interval ( const PointerInterval & ival )

test intersection of intervals

Parameters

ival	a segment interval

Returns: true if a>b

Definition at line 197 of file boundary.cpp.

◆ empty_see_through_interval()

bool frechet::reach::empty_see_through_interval ( Pointer p )

test intersection of intervals. Assumes a SEE_THROUGH segment.

l,h pointer must point FORWARD, resp. BACKWARD

Parameters

p	a segment interval

Returns: true if a>b

Definition at line 203 of file boundary.cpp.

◆ max() [1/3]

Pointer frechet::reach::max	(	const Pointer	a,
		const Pointer	b
	)

maximum of two reachability intervals; compare lower bound, then upper bound

Parameters

a	a pointer to a reachability interval
b	a pointer to a reachability interval

Returns: pointer to lowest interval

Definition at line 70 of file boundary.cpp.

◆ max() [2/3]

Pointer frechet::reach::max ( const PointerInterval & ival )

maximum of two reachability intervals; compare lower bound, then upper bound

Parameters

ival	an interval of l,h reachability intervals

Returns: pointer to lowest interval

Definition at line 81 of file boundary.cpp.

◆ max() [3/3]

Pointer frechet::reach::max	(	const PointerInterval &	a,
		const PointerInterval &	b
	)

maximum of two reachability intervals; compare lower bound, then upper bound

Parameters

a	an interval of l,h reachability intervals
b	an interval of l,h reachability intervals

Returns: pointer to lowest interval

Definition at line 86 of file boundary.cpp.

◆ min() [1/3]

Pointer frechet::reach::min	(	const Pointer	a,
		const Pointer	b
	)

minimum of two reachability intervals; compare lower bound, then upper bound

Parameters

a	a pointer to a reachability interval
b	a pointer to a reachability interval

Returns: pointer to lowest interval

Definition at line 49 of file boundary.cpp.

◆ min() [2/3]

Pointer frechet::reach::min ( const PointerInterval & ival )

minimum of two reachability intervals; compare lower bound, then upper bound

Parameters

ival	an interval of l,h reachability intervals

Returns: pointer to lowest interval

Definition at line 60 of file boundary.cpp.

◆ min() [3/3]

Pointer frechet::reach::min	(	const PointerInterval &	a,
		const PointerInterval &	b
	)

minimum of two reachability intervals; compare lower bound, then upper bound

Parameters

a	an interval of l,h reachability intervals
b	an interval of l,h reachability intervals

Returns: pointer to lowest interval

Definition at line 65 of file boundary.cpp.

◆ newGraph() [1/3]

GraphPtr frechet::reach::newGraph ( const GraphModel::ptr model )

Definition at line 12 of file graph_cl.cpp.

◆ newGraph() [2/3]

GraphPtr frechet::reach::newGraph	(	const GraphModel::ptr	model,
		IndexRange	hmask
	)

Definition at line 20 of file graph_cl.cpp.

◆ newGraph() [3/3]

GraphPtr frechet::reach::newGraph	(	const GraphModel::ptr	model,
		Structure &	str
	)

Definition at line 28 of file graph_cl.cpp.

◆ operator++() [1/2]

Orientation& frechet::reach::operator++ ( Orientation & ori )

inline

pre-increment an orientation variable. Note that an orientation variable can only be incremented once from HORIZONTAL to VERTICAL. Incrementing VERTICAL causes an undefined result.

Parameters

ori	an orientation

Returns: reference after incrementing

Definition at line 50 of file boundary.h.

◆ operator++() [2/2]

Direction& frechet::reach::operator++ ( Direction & dir )

inline

pre-increment a direction variable. Note that a direction variable can only be incremented once from FIRST to SECOND. Incrementing SECOND causes an undefined result.

Parameters

dir	a direction

Returns: reference after incrementing

Definition at line 150 of file boundary.h.

◆ operator<<() [1/2]

std::ostream & frechet::reach::operator<<	(	std::ostream &	out,
		const BoundaryList &	list
	)

print operator for debugging

Definition at line 272 of file boundary.cpp.

◆ operator<<() [2/2]

std::ostream & frechet::reach::operator<<	(	std::ostream &	out,
		const Structure &	str
	)

print operator used for debugging; prints diagnostic info about a reachability structure

Parameters

out	output stream
str	reachability structur

Returns: same as out

Definition at line 1051 of file structure.cpp.

◆ operator|()

Bias frechet::reach::operator\|	(	Bias	a,
		Bias	b
	)

union operator

Parameters

a	a bias
b	another bias

Returns: combined bias

Definition at line 105 of file graph_model.cpp.

◆ operator|=()

Bias & frechet::reach::operator\|=	(	Bias &	a,
		Bias	b
	)

union operator

Parameters

a	a bias, updated on return
b	another bias

Returns: reference to this, after being updated

Definition at line 109 of file graph_model.cpp.

◆ opposite() [1/2]

Orientation frechet::reach::opposite ( Orientation ori )

inline

Parameters

ori	an orientation

Returns: the opposite to the given orientation

Definition at line 39 of file boundary.h.

◆ opposite() [2/2]

Direction frechet::reach::opposite ( Direction dir )

inline

Parameters

dir	a Direction

Returns: the opposite direction

Definition at line 139 of file boundary.h.

Detailed Description

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ BoundaryList

◆ GraphPtr

◆ Placements

◆ Pointer

Enumeration Type Documentation

◆ Bias

◆ Direction

◆ Orientation

◆ Type

Function Documentation

◆ compare_interval() [1/2]

◆ compare_interval() [2/2]

◆ compare_pointers()

◆ empty_interval() [1/2]

◆ empty_interval() [2/2]

◆ empty_see_through_interval()

◆ max() [1/3]

◆ max() [2/3]

◆ max() [3/3]

◆ min() [1/3]

◆ min() [2/3]

◆ min() [3/3]

◆ newGraph() [1/3]

◆ newGraph() [2/3]

◆ newGraph() [3/3]

◆ operator++() [1/2]

◆ operator++() [2/2]

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ operator|()

◆ operator|=()

◆ opposite() [1/2]

◆ opposite() [2/2]