Detailed Description

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

Allows to query for feasible paths in O(1).

Implements the Divide-and-Conquer algorithm for calculating the Reachability Structure recursively.

Interval structure is identical for Left and Right, respectively Bottom and Top.

See also: [alt95]

Author: Peter Schäfer

Definition at line 32 of file structure.h.

#include <structure.h>

Classes
struct	SingleCellAuxData
	aux. data structure that is used to construct an initial reachability cell More...

Public Types
typedef boost::shared_ptr< Structure >	ptr
	smart pointer to a Structure object More...

typedef void(*	assert_hook) (Structure , const Rect , Structure , const Rect , Orientation)
	hooks for Unit Tests. Only used in debug mode. More...

Public Member Functions
	Structure (int concurrency=1, volatile bool *cancelFlag=nullptr)
	empty constructor More...

	Structure (const FreeSpace::ptr fs, int concurrency=1, volatile bool *cancelFlag=nullptr)
	default constructor More...

	Structure (const Structure &that)
	copy constructor More...

	Structure (Structure &&that)
	move constructor More...

Structure &	operator= (const Structure &that)
	assigment operator More...

Structure &	operator= (Structure &&that)
	move assigment operator More...

void	copy (const Structure &that)
	assigment function More...

void	swap (Structure &that)
	swap content with another object More...

virtual	~Structure ()
	destructor; releases all memory More...

const FreeSpace::ptr	freeSpace () const

BoundaryList &	boundary (Orientation ori, Direction dir)

const BoundaryList &	boundary (Orientation ori, Direction dir) const

BoundaryList &	first (Orientation ori)

BoundaryList &	second (Orientation ori)

const BoundaryList &	first (Orientation ori) const

const BoundaryList &	second (Orientation ori) const

BoundaryList &	horizontal (Direction dir)
	first or second part of the reachability structure More...

BoundaryList &	vertical (Direction dir)
	first or second part of the reachability structure More...

BoundaryList &	left ()

BoundaryList &	right ()

BoundaryList &	bottom ()

BoundaryList &	top ()

const BoundaryList &	left () const

const BoundaryList &	right () const

const BoundaryList &	bottom () const

const BoundaryList &	top () const

Pointer	calculate ()
	compute the reachability structure from the underlying free-space diagram. Uses a divide-and-conquere algorithms that recursively merges reachability structures. Uses parallel threads, optionally. If there is a feasible path, find the starting interval of the path. Works for both, closed and open curves. More...

Pointer	calculateDouble ()
	compute the reachability structure for a closed curve, based on a double-free-space-diagram. More...

Pointer	calculateSingle ()
	compute the reachability structure for an open curve, based on a single free-space-diagram. More...

void	calculateColumns (int i, int j)
	compute a region of the reachability structure. may span the double free-space!. More...

void	singleCell (int i, int j)
	create a BoundarySegment from one cell of the free-space-diagram More...

void	calculateDouble (Orientation fringe)
	compute the reachability structure for a closed curve, based on a double-free-space-diagram. More...

Pointer	findStartingPoint (Orientation edge)
	after the reachability structure is computed, find the starting interval of a feasible path. Works for closed and open curves. More...

void	shift (Point offset)
	shift the reachability structure by a given offset. The shifted second copy is then merged to compute a double-reachability structure. More...

Pointer	next (Pointer p) const
	used when traversing reachability segments. Traversal direction is discussed in frechet::reach::Direction. More...

Pointer	prev (Pointer p) const
	used when traversing reachability segments. Traversal direction is discussed in frechet::reach::Direction. More...

void	synchIntervals (Orientation fringe, Structure &that)
	before mergin two reachabiliry structures, its intervals must be synchronized More...

void	takeOwnership ()
	for debugging: fill in owner pointers More...

Static Public Member Functions
static int	freeSpaceArrangement (data::Interval LF, data::Interval RF)
	compute the arrangement of free-space intervals for one cell More...

static bool	assertPointerInterval (Pointer p, const PointerInterval &ival)
	for debugging and unit tests, check if reachability intervals are consistent More...

Static Public Attributes
static assert_hook	after_single_cell = nullptr

static assert_hook	before_merge = nullptr

static assert_hook	after_merge = nullptr

Private Member Functions
Pointer	prevReachable (Pointer p)
	find previous reachable segment More...

Pointer	nextReachable (Pointer p)
	find next reachable segment More...

void	calcRecursive (const Rect &r)
	Divide & Conquer algorithm. Merge regions recursively. Makes use of paralel threads. More...

void	doCalcRecursive (const Rect &r)
	Merge regions recursively. Uses only one thread. More...

void	merge (Orientation fringe, Structure &that, const Rect &r1, const Rect &r2)
	merge this structure with another structure More...

Pointer	split (Pointer seg, double y, Pointer twin)
	split a reachabiliy segment Adjust l,h pointers into that segment. More...

void	split2 (Pointer &a, double x, Pointer &b)
	split a reachabiliy segment and its opposite segment More...

void	crossLink (Pointer i1, Pointer i2, Pointer j1, Pointer j2)
	set up links between four opposite segments. This pointer chain will be used to traverse a reachability structure horizontally. More...

void	merge (BoundaryList &list, Pointer a, Pointer b)
	merge two adjacent segments. b := a union b More...

void	mergeConsecutive (Orientation ori)
	could be used to merge indentical intervals. Reduces the number of intervals (and thus the complexity of the algorithm). Causes some trouble later, with fine-grained segmentation in simple polygons algorithm. More...

void	scanAndMerge (Pointer K, Orientation fringe)
	scan and merge one segment More...

void	markNonAccesible (Orientation fringe, Structure &that)
	mark non-accesible segments More...

void	markNonAccesible (Pointer p, Pointer p2)
	mark one non-accesible segment More...

void	updatePointers (Pointer K, Pointer l, Pointer h, Pointer K1)
	update all l,h, pointers that point into a segment More...

void	createSingleCellSegments (SingleCellAuxData &aux, Orientation ori, double y0)
	create segments for a single cell of the reachability structure More...

void	linkSingleCellSegments (SingleCellAuxData &aux, Orientation ori)
	set up the l,h pointers within a single cell More...

void	clipSeeThroughPointer (Pointer p)
	adjust the see-through pointers. For see-through segments l:=nullptr, resp. h:=nullptr More...

PointerInterval	reachableInterval (Pointer seg[5])
	find a reachable interval More...

void	create2Segments (Pointer &first, Pointer &second, data::Interval ival, Orientation ori, Type t1, Type t2)
	create a pair of reachability segments, on opposite sides of the structure More...

void	copySegments (BoundaryList &list, Pointer seg[5])
	construct part of a single-sell segment More...

void	testCancelFlag ()
	check for user interrupion The canceFlag should be polled in regular intervals. If the user requested an interruption, throw an exception to abort current computation. More...

Static Private Member Functions
static int	freeSpaceArrangement (SingleCellAuxData &aux, Orientation ori)
	compute the arrangement of free-space intervals for one cell More...

static bool	assertSynchedIntervals (Pointer i1, Pointer i2, Pointer i3, Pointer i4)
	for debugging and unit tests, check if reachability intervals are consistent More...

Private Attributes
const FreeSpace::ptr	fs
	the underlying free-space; may be nullptr More...

BoundaryList	_boundary [2][2]
	Boundaries [HORIZONTAL,VERTICAL] [FIRST,SECOND]. More...

int	concurrency
	number of parallel threads to use More...

volatile bool *	cancelFlag
	used when running ia a background thread to indicate cancellation by the user More...

Friends
class	StructureIterator

class	GraphModel

class	CalculateTask

class	MergeTask

Member Typedef Documentation

◆ assert_hook

typedef void(* frechet::reach::Structure::assert_hook) (Structure *, const Rect *, Structure *, const Rect *, Orientation)

hooks for Unit Tests. Only used in debug mode.

Definition at line 468 of file structure.h.

◆ ptr

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

smart pointer to a Structure object

Definition at line 50 of file structure.h.

Constructor & Destructor Documentation

◆ Structure() [1/4]

frechet::reach::Structure::Structure	(	int	concurrency = `1`,
		volatile bool *	cancelFlag = `nullptr`
	)

empty constructor

Parameters

concurrency	number of threads for parallel execution
cancelFlag	indicates user interruption

◆ Structure() [2/4]

frechet::reach::Structure::Structure	(	const FreeSpace::ptr	fs,
		int	concurrency = `1`,
		volatile bool *	cancelFlag = `nullptr`
	)

default constructor

Parameters

fs	underlying free-space
concurrency	number of threads for parallel execution
cancelFlag	indicates user interruption

◆ Structure() [3/4]

Structure::Structure ( const Structure & that )

copy constructor

Parameters

that	object to copy from

Definition at line 24 of file structure.cpp.

◆ Structure() [4/4]

Structure::Structure ( Structure && that )

move constructor

Parameters

that	object to move data from; empty on return

Definition at line 30 of file structure.cpp.

◆ ~Structure()

Structure::~Structure ( )

virtual

destructor; releases all memory

Definition at line 127 of file structure.cpp.

Member Function Documentation

◆ assertPointerInterval()

bool Structure::assertPointerInterval	(	Pointer	p,
		const PointerInterval &	ival
	)

static

for debugging and unit tests, check if reachability intervals are consistent

Returns: true if intervals are consistent

Definition at line 958 of file structure.cpp.

◆ assertSynchedIntervals()

bool Structure::assertSynchedIntervals	(	Pointer	i1,
		Pointer	i2,
		Pointer	i3,
		Pointer	i4
	)

staticprivate

for debugging and unit tests, check if reachability intervals are consistent

Returns: true if intervals are consistent

Definition at line 992 of file structure.cpp.

◆ bottom() [1/2]

BoundaryList& frechet::reach::Structure::bottom ( )

inline

Returns: bottom boundary of the reachability structure

Definition at line 165 of file structure.h.

◆ bottom() [2/2]

const BoundaryList& frechet::reach::Structure::bottom ( ) const

inline

Returns: immutable reference to bottom boundary of the reachability structure

Definition at line 174 of file structure.h.

◆ boundary() [1/2]

BoundaryList& frechet::reach::Structure::boundary	(	Orientation	ori,
		Direction	dir
	)

inline

Parameters

ori	horizontal or vertical
dir	first(=bottom,left) or second (=top,right)

Returns: one of the four boundaries of the reachability structure

Definition at line 113 of file structure.h.

◆ boundary() [2/2]

const BoundaryList& frechet::reach::Structure::boundary	(	Orientation	ori,
		Direction	dir
	)		const

inline

Parameters

ori	horizontal or vertical
dir	first(=bottom,left) or second (=top,right)

Returns: immutable reference to one of the four boundaries of the reachability structure

Definition at line 122 of file structure.h.

◆ calcRecursive()

void Structure::calcRecursive ( const Rect & r )

private

Divide & Conquer algorithm. Merge regions recursively. Makes use of paralel threads.

Parameters

r	region to merge (columns,rows in free-space)

Definition at line 273 of file structure.cpp.

◆ calculate()

Pointer Structure::calculate ( )

compute the reachability structure from the underlying free-space diagram. Uses a divide-and-conquere algorithms that recursively merges reachability structures. Uses parallel threads, optionally. If there is a feasible path, find the starting interval of the path. Works for both, closed and open curves.

Returns: starting interval of feasible path, of nullptr if there is none

Definition at line 130 of file structure.cpp.

◆ calculateColumns()

void Structure::calculateColumns	(	int	i,
		int	j
	)

compute a region of the reachability structure. may span the double free-space!.

Parameters

i	first column
j	last column, exclusive

Definition at line 180 of file structure.cpp.

◆ calculateDouble() [1/2]

frechet::reach::Pointer Structure::calculateDouble ( )

compute the reachability structure for a closed curve, based on a double-free-space-diagram.

Returns: starting interval of feasible path, of nullptr if there is none

Definition at line 167 of file structure.cpp.

◆ calculateDouble() [2/2]

void Structure::calculateDouble ( Orientation fringe )

compute the reachability structure for a closed curve, based on a double-free-space-diagram.

Parameters

fringe duplicate reachability structure along the horizontal edge, or the vertical edge

We assume a second copy of the free-space. Since left and right parts are identical, we can calculate the right half simply by shifting.

Definition at line 211 of file structure.cpp.

◆ calculateSingle()

Pointer Structure::calculateSingle ( )

compute the reachability structure for an open curve, based on a single free-space-diagram.

Returns: starting interval of feasible path, of nullptr if there is none

Definition at line 142 of file structure.cpp.

◆ clipSeeThroughPointer()

void Structure::clipSeeThroughPointer ( Pointer p )

private

adjust the see-through pointers. For see-through segments l:=nullptr, resp. h:=nullptr

Parameters

p	points to a reachability segment

Definition at line 603 of file str_singlecell.cpp.

◆ copy()

void Structure::copy ( const Structure & that )

assigment function

Parameters

that	object to copy from

DO NOT copy FreeSpace. (use calculate to assign it. or don't)

CLONE structure with deep copies. Important: adjust h/l pointers, too. For that, we need to keep track of cloned copies. BoundarySegment.temp.clone is used to keep track of cloned segments temporarily.

Definition at line 44 of file structure.cpp.

◆ copySegments()

void Structure::copySegments	(	BoundaryList &	list,
		Pointer	seg[5]
	)

private

construct part of a single-sell segment

Parameters

list	list to append
seg	boundary segments that will be assembled into the list

Definition at line 634 of file str_singlecell.cpp.

◆ create2Segments()

void Structure::create2Segments	(	Pointer &	first,
		Pointer &	second,
		data::Interval	ival,
		Orientation	ori,
		Type	t1,
		Type	t2
	)

private

create a pair of reachability segments, on opposite sides of the structure

Parameters

first	holds the first segment on return
second	holds the second segment on return
ival	free-space interval, identical to both segments
ori	horizontal or vertical
t1	reachability label for first segment
t2	reachability label for second segment

Definition at line 627 of file str_singlecell.cpp.

◆ createSingleCellSegments()

void Structure::createSingleCellSegments	(	SingleCellAuxData &	aux,
		Orientation	ori,
		double	y0
	)

private

create segments for a single cell of the reachability structure

Parameters

aux	aux. data
ori	horizontal or vertical intervals?
y0	lower bound

Definition at line 224 of file str_singlecell.cpp.

◆ crossLink()

void Structure::crossLink	(	Pointer	i1,
		Pointer	i2,
		Pointer	j1,
		Pointer	j2
	)

private

set up links between four opposite segments. This pointer chain will be used to traverse a reachability structure horizontally.

Parameters

i1	segment on the outer left edge
i2	segment on the center left edge
j1	segment on the center right edge
j2	segment on the outer right edge

    ---  ---    ---  ---
     |    |      |    |
     |<-->|<---->|<-->|
     |    |      |    |
    ---  ---    ---  ---
    L1   R1     L2   R2
    left        right region
    region

Definition at line 496 of file structure.cpp.

◆ doCalcRecursive()

void Structure::doCalcRecursive ( const Rect & r )

private

Merge regions recursively. Uses only one thread.

Parameters

r	region to merge (columns,rows in free-space)

Definition at line 371 of file structure.cpp.

◆ findStartingPoint()

Pointer Structure::findStartingPoint ( Orientation edge )

after the reachability structure is computed, find the starting interval of a feasible path. Works for closed and open curves.

Parameters

edge	look for starting point on horizontal edge, of vertical edge

Returns: starting interval of feasible path, of nullptr if there is none

                         h  .. v    ..  l
   +-----------------+ +-----------------+
   |                 | |                 |
   |                 | |                 |
   |                 | |                 |
   +-----------------+ +-----------------+
       u ->

     v =  u + offset

Note: interval structures on B1 and T2 are identical (and not affected by merge). Interval overlap only when identical. So, all we have to check for is u->l <= v <= u->h

Definition at line 248 of file structure.cpp.

◆ first() [1/2]

BoundaryList& frechet::reach::Structure::first ( Orientation ori )

inline

Parameters

ori	horizontal or vertical

Returns: bottom or left boundary of the reachability structure

Definition at line 129 of file structure.h.

◆ first() [2/2]

const BoundaryList& frechet::reach::Structure::first ( Orientation ori ) const

inline

Parameters

ori	horizontal or vertical

Returns: immutable reference to bottom or left boundary of the reachability structure

Definition at line 140 of file structure.h.

◆ freeSpace()

const FreeSpace::ptr frechet::reach::Structure::freeSpace ( ) const

inline

Returns: pointer to the underlying free-space

Definition at line 106 of file structure.h.

◆ freeSpaceArrangement() [1/2]

static int frechet::reach::Structure::freeSpaceArrangement	(	data::Interval	LF,
		data::Interval	RF
	)

static

compute the arrangement of free-space intervals for one cell

Parameters

LF	left free-space interval
RF	right free-space interval

Returns: a value in [0..15], encoding an arrangement

◆ freeSpaceArrangement() [2/2]

int Structure::freeSpaceArrangement	(	SingleCellAuxData &	aux,
		Orientation	ori
	)

staticprivate

compute the arrangement of free-space intervals for one cell

Parameters

aux	aux. data
ori	horizontal or vertical intervals?

Returns: a value in [0..15], encoding an arrangement

Definition at line 56 of file str_singlecell.cpp.

◆ horizontal()

BoundaryList& frechet::reach::Structure::horizontal ( Direction dir )

inline

first or second part of the reachability structure

Parameters

dir	first=bottom, second=top

Returns: bottom or top boundary of the reachability structure

Definition at line 152 of file structure.h.

◆ left() [1/2]

BoundaryList& frechet::reach::Structure::left ( )

inline

Returns: left boundary of the reachability structure

Definition at line 161 of file structure.h.

◆ left() [2/2]

const BoundaryList& frechet::reach::Structure::left ( ) const

inline

Returns: immutable reference to left boundary of the reachability structure

Definition at line 170 of file structure.h.

◆ linkSingleCellSegments()

void Structure::linkSingleCellSegments	(	SingleCellAuxData &	aux,
		Orientation	ori
	)

private

set up the l,h pointers within a single cell

Parameters

aux	aux. data
ori	horizontal or vertical intervals?

Definition at line 424 of file str_singlecell.cpp.

◆ markNonAccesible() [1/2]

void Structure::markNonAccesible	(	Orientation	fringe,
		Structure &	that
	)

private

mark non-accesible segments

Parameters

fringe	along horizonal edge, or vertical egde
that	structure to merge with

             T1                        T2
            +-----------------+       +-----------------+
        L1  |                 |    L2 |                 |
            |                 |       |                 |
            |                 | R1    |                 | R2
            |                 |       |                 |
            |                 |       |                 |
            |K1              K|<----->|I              I2|
            |                 |       |                 |
            +-----------------+       +-----------------+
              B1                        B2

Definition at line 671 of file structure.cpp.

◆ markNonAccesible() [2/2]

void frechet::reach::Structure::markNonAccesible	(	Pointer	p,
		Pointer	p2
	)

private

mark one non-accesible segment

Parameters

p	pointer to a reachability segment
p2	pointer to a reachability segment

◆ merge() [1/2]

void frechet::reach::Structure::merge	(	Orientation	fringe,
		Structure &	that,
		const Rect &	r1,
		const Rect &	r2
	)

private

merge this structure with another structure

Parameters

fringe	merge along the horizontal edge, or along the vertical edge?
that	structure to merge with
r1	region of this structue (columns,rows in free-space)
r2	region of that structure (columns,rows in free-space)

◆ merge() [2/2]

void Structure::merge	(	BoundaryList &	list,
		Pointer	a,
		Pointer	b
	)

private

merge two adjacent segments. b := a union b

Parameters

list	list containing both segment
a	left neighbor; will be removed
b	will be extended to hold a union b

Definition at line 906 of file structure.cpp.

◆ mergeConsecutive()

void Structure::mergeConsecutive ( Orientation ori )

private

could be used to merge indentical intervals. Reduces the number of intervals (and thus the complexity of the algorithm). Causes some trouble later, with fine-grained segmentation in simple polygons algorithm.

Parameters

ori	horizontal or vertical

Deprecated:: not used

Definition at line 563 of file structure.cpp.

◆ next()

Pointer Structure::next ( Pointer p ) const

used when traversing reachability segments. Traversal direction is discussed in frechet::reach::Direction.

Parameters

p	a pointer to a reachability segment

Returns: pointer to next neighbor, or null

Definition at line 916 of file structure.cpp.

◆ nextReachable()

Pointer Structure::nextReachable ( Pointer p )

private

find next reachable segment

Parameters

p	a pointer to a reachability segment

Returns: next segment in traversal order that is REACHABLE

Definition at line 610 of file structure.cpp.

◆ operator=() [1/2]

Structure & Structure::operator= ( const Structure & that )

assigment operator

Parameters

that	object to copy from

Returns: reference to this object, after assignment

Definition at line 93 of file structure.cpp.

◆ operator=() [2/2]

Structure & Structure::operator= ( Structure && that )

move assigment operator

Parameters

that	object to move data from; empty on return

Returns: reference to this object, after assignment

Definition at line 87 of file structure.cpp.

◆ prev()

Pointer Structure::prev ( Pointer p ) const

used when traversing reachability segments. Traversal direction is discussed in frechet::reach::Direction.

Parameters

p	a pointer to a reachability segment

Returns: pointer to previous neighbor, or null

Definition at line 933 of file structure.cpp.

◆ prevReachable()

Pointer Structure::prevReachable ( Pointer p )

private

find previous reachable segment

Parameters

p	a pointer to a reachability segment

Returns: previous segment in traversal order that is REACHABLE

Definition at line 602 of file structure.cpp.

◆ reachableInterval()

PointerInterval Structure::reachableInterval ( Pointer seg[5] )

private

find a reachable interval

Parameters

seg	list of segments on the opposite edge

Returns: an interval of reachable segments

Definition at line 615 of file str_singlecell.cpp.

◆ right() [1/2]

BoundaryList& frechet::reach::Structure::right ( )

inline

Returns: right boundary of the reachability structure

Definition at line 163 of file structure.h.

◆ right() [2/2]

const BoundaryList& frechet::reach::Structure::right ( ) const

inline

Returns: immutable reference to right boundary of the reachability structure

Definition at line 172 of file structure.h.

◆ scanAndMerge()

void Structure::scanAndMerge	(	Pointer	K,
		Orientation	fringe
	)

private

scan and merge one segment

Parameters

K	pointer to a reachability segment, see [alt95]
fringe	merge along horizonal edge, or vertical egde

             T1                        T2
            +-----------------+       +-----------------+
        L1  |                 |    L2 |                 |
            |                 |       |                 |
            |                 | R1    |                 | R2
            |                 |       |                 |
            |                 |       |                 |
            |             h(K)|<----->|I                |
            | K               |       |K'               |
            +-----------------+       +-----------------+
              B1                        B2

Next we scan through B1 u L1 and extend pointers. For each r- or s- interval L we update type and pointers as follows:

Definition at line 747 of file structure.cpp.

◆ second() [1/2]

BoundaryList& frechet::reach::Structure::second ( Orientation ori )

inline

Parameters

ori	horizontal or vertical

Returns: top or right boundary of the reachability structure

Definition at line 134 of file structure.h.

◆ second() [2/2]

const BoundaryList& frechet::reach::Structure::second ( Orientation ori ) const

inline

Parameters

ori	horizontal or vertical

Returns: mmutable reference to top or right boundary of the reachability structure

Definition at line 145 of file structure.h.

◆ shift()

void Structure::shift ( Point offset )

shift the reachability structure by a given offset. The shifted second copy is then merged to compute a double-reachability structure.

Parameters

offset horizontal and vertical offset

Definition at line 111 of file structure.cpp.

◆ singleCell()

void Structure::singleCell	(	int	i,
		int	j
	)

create a BoundarySegment from one cell of the free-space-diagram

Parameters

i	column in free-space
j	row in free-space

Creation of segments and linking of l,h pointers must be done in two steps (the segments must exists before we can link the l,h pointers)

Definition at line 10 of file str_singlecell.cpp.

◆ split()

Pointer Structure::split	(	Pointer	seg,
		double	y,
		Pointer	twin
	)

private

split a reachabiliy segment Adjust l,h pointers into that segment.

Parameters

seg	segment to split
y	point in interval where to split
twin	pointer to opposite segment (remains unmodified, but used to track incoming pointers)

Returns: pointer to the newly created segment, below the old one

          ---       ---
           |         | old segment
           |         |
           |   ==>  --- y
           |         |
           |         | new segment
          ---       ---

Definition at line 846 of file structure.cpp.

◆ split2()

void Structure::split2	(	Pointer &	a,
		double	x,
		Pointer &	b
	)

private

split a reachabiliy segment and its opposite segment

Parameters

a	segment to split
x	point in interval where to split
b	opposite segment to split

    ---      ---           ---      ---
     |        |             |        |
     |        |     ==>    ---      ---
     |        |             |        |
    ---      ---           ---      ---
   left     right
   twin     twin

Definition at line 479 of file structure.cpp.

◆ swap()

void Structure::swap ( Structure & that )

swap content with another object

Parameters

that	to swap data with; on return, holds contents of this object

Definition at line 99 of file structure.cpp.

◆ synchIntervals()

void Structure::synchIntervals	(	Orientation	fringe,
		Structure &	that
	)

before mergin two reachabiliry structures, its intervals must be synchronized

Parameters

fringe	synchronize along the horizontal edge, or along the verical edge
that	reachability structure to synchronize with

Definition at line 398 of file structure.cpp.

◆ takeOwnership()

void Structure::takeOwnership ( )

for debugging: fill in owner pointers

Definition at line 592 of file structure.cpp.

◆ testCancelFlag()

void Structure::testCancelFlag ( )

private

check for user interrupion The canceFlag should be polled in regular intervals. If the user requested an interruption, throw an exception to abort current computation.

Exceptions

InterruptedException thrown when the user requests an interruption. Caught by application logic.

Definition at line 951 of file structure.cpp.

◆ top() [1/2]

BoundaryList& frechet::reach::Structure::top ( )

inline

Returns: top boundary of the reachability structure

Definition at line 167 of file structure.h.

◆ top() [2/2]

const BoundaryList& frechet::reach::Structure::top ( ) const

inline

Returns: immutable reference to top boundary of the reachability structure

Definition at line 176 of file structure.h.

◆ updatePointers()

void Structure::updatePointers	(	Pointer	K,
		Pointer	l,
		Pointer	h,
		Pointer	K1
	)

private

update all l,h, pointers that point into a segment

Parameters

K	target segment
l	start of range of incoming segments
h	end of range of incoming segments
K1	opposite to K

Definition at line 618 of file structure.cpp.

◆ vertical()

BoundaryList& frechet::reach::Structure::vertical ( Direction dir )

inline

first or second part of the reachability structure

Parameters

dir	first=left, second=right

Returns: left or right boundary of the reachability structure

Definition at line 158 of file structure.h.

Friends And Related Function Documentation

◆ CalculateTask

friend class CalculateTask

friend

Definition at line 46 of file structure.h.

◆ GraphModel

friend class GraphModel

friend

Definition at line 45 of file structure.h.

◆ MergeTask

friend class MergeTask

friend

Definition at line 47 of file structure.h.

◆ StructureIterator

friend class StructureIterator

friend

Definition at line 44 of file structure.h.

Member Data Documentation

◆ _boundary

BoundaryList frechet::reach::Structure::_boundary[2][2]

private

Boundaries [HORIZONTAL,VERTICAL] [FIRST,SECOND].

Definition at line 38 of file structure.h.

◆ after_merge

Structure::assert_hook Structure::after_merge = nullptr

static

Definition at line 473 of file structure.h.

◆ after_single_cell

Structure::assert_hook Structure::after_single_cell = nullptr

static

Definition at line 473 of file structure.h.

◆ before_merge

Structure::assert_hook Structure::before_merge = nullptr

static

Definition at line 473 of file structure.h.

◆ cancelFlag

volatile bool* frechet::reach::Structure::cancelFlag

private

used when running ia a background thread to indicate cancellation by the user

Definition at line 42 of file structure.h.

◆ concurrency

int frechet::reach::Structure::concurrency

private

number of parallel threads to use

Definition at line 40 of file structure.h.

◆ fs

const FreeSpace::ptr frechet::reach::Structure::fs

private

the underlying free-space; may be nullptr

Definition at line 36 of file structure.h.

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

include/frechet/reachability/structure.h
src/frechet/reachability/str_singlecell.cpp
src/frechet/reachability/structure.cpp

Detailed Description

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Member Typedef Documentation

◆ assert_hook

◆ ptr

Constructor & Destructor Documentation

◆ Structure() [1/4]

◆ Structure() [2/4]

◆ Structure() [3/4]

◆ Structure() [4/4]

◆ ~Structure()

Member Function Documentation

◆ assertPointerInterval()

◆ assertSynchedIntervals()

◆ bottom() [1/2]

◆ bottom() [2/2]

◆ boundary() [1/2]

◆ boundary() [2/2]

◆ calcRecursive()

◆ calculate()

◆ calculateColumns()

◆ calculateDouble() [1/2]

◆ calculateDouble() [2/2]

◆ calculateSingle()

◆ clipSeeThroughPointer()

◆ copy()

◆ copySegments()

◆ create2Segments()

◆ createSingleCellSegments()

◆ crossLink()

◆ doCalcRecursive()

◆ findStartingPoint()

◆ first() [1/2]

◆ first() [2/2]

◆ freeSpace()

◆ freeSpaceArrangement() [1/2]

◆ freeSpaceArrangement() [2/2]

◆ horizontal()

◆ left() [1/2]

◆ left() [2/2]

◆ linkSingleCellSegments()

◆ markNonAccesible() [1/2]

◆ markNonAccesible() [2/2]

◆ merge() [1/2]

◆ merge() [2/2]

◆ mergeConsecutive()

◆ next()

◆ nextReachable()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ prev()

◆ prevReachable()

◆ reachableInterval()

◆ right() [1/2]

◆ right() [2/2]

◆ scanAndMerge()

◆ second() [1/2]

◆ second() [2/2]

◆ shift()

◆ singleCell()

◆ split()

◆ split2()

◆ swap()

◆ synchIntervals()

◆ takeOwnership()

◆ testCancelFlag()

◆ top() [1/2]

◆ top() [2/2]

◆ updatePointers()

◆ vertical()

Friends And Related Function Documentation

◆ CalculateTask