Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::reach::Structure Class Reference

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< Structureptr
 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...
 
Structureoperator= (const Structure &that)
 assigment operator More...
 
Structureoperator= (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
 
BoundaryListboundary (Orientation ori, Direction dir)
 
const BoundaryListboundary (Orientation ori, Direction dir) const
 
BoundaryListfirst (Orientation ori)
 
BoundaryListsecond (Orientation ori)
 
const BoundaryListfirst (Orientation ori) const
 
const BoundaryListsecond (Orientation ori) const
 
BoundaryListhorizontal (Direction dir)
 first or second part of the reachability structure More...
 
BoundaryListvertical (Direction dir)
 first or second part of the reachability structure More...
 
BoundaryListleft ()
 
BoundaryListright ()
 
BoundaryListbottom ()
 
BoundaryListtop ()
 
const BoundaryListleft () const
 
const BoundaryListright () const
 
const BoundaryListbottom () const
 
const BoundaryListtop () 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
concurrencynumber of threads for parallel execution
cancelFlagindicates user interruption

◆ Structure() [2/4]

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

default constructor

Parameters
fsunderlying free-space
concurrencynumber of threads for parallel execution
cancelFlagindicates user interruption

◆ Structure() [3/4]

Structure::Structure ( const Structure that)

copy constructor

Parameters
thatobject to copy from

Definition at line 24 of file structure.cpp.

◆ Structure() [4/4]

Structure::Structure ( Structure &&  that)

move constructor

Parameters
thatobject 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
orihorizontal or vertical
dirfirst(=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
orihorizontal or vertical
dirfirst(=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
rregion 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
ifirst column
jlast 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
fringeduplicate 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
ppoints to a reachability segment

Definition at line 603 of file str_singlecell.cpp.

◆ copy()

void Structure::copy ( const Structure that)

assigment function

Parameters
thatobject 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
listlist to append
segboundary 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
firstholds the first segment on return
secondholds the second segment on return
ivalfree-space interval, identical to both segments
orihorizontal or vertical
t1reachability label for first segment
t2reachability 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
auxaux. data
orihorizontal or vertical intervals?
y0lower 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
i1segment on the outer left edge
i2segment on the center left edge
j1segment on the center right edge
j2segment 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
rregion 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
edgelook 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
orihorizontal 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
orihorizontal 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
LFleft free-space interval
RFright 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
auxaux. data
orihorizontal 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
dirfirst=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
auxaux. data
orihorizontal 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
fringealong horizonal edge, or vertical egde
thatstructure 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
ppointer to a reachability segment
p2pointer 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
fringemerge along the horizontal edge, or along the vertical edge?
thatstructure to merge with
r1region of this structue (columns,rows in free-space)
r2region 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
listlist containing both segment
aleft neighbor; will be removed
bwill 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
orihorizontal 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
pa 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
pa 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
thatobject 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
thatobject 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
pa 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
pa 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
seglist 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
Kpointer to a reachability segment, see [alt95]
fringemerge 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
orihorizontal 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
orihorizontal 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
offsethorizontal 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
icolumn in free-space
jrow 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
segsegment to split
ypoint in interval where to split
twinpointer 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
asegment to split
xpoint in interval where to split
bopposite 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
thatto 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
fringesynchronize along the horizontal edge, or along the verical edge
thatreachability 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
InterruptedExceptionthrown 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
Ktarget segment
lstart of range of incoming segments
hend of range of incoming segments
K1opposite 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
dirfirst=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: