![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
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.
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 |
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.
typedef boost::shared_ptr<Structure> frechet::reach::Structure::ptr |
smart pointer to a Structure object
Definition at line 50 of file structure.h.
frechet::reach::Structure::Structure | ( | int | concurrency = 1 , |
volatile bool * | cancelFlag = nullptr |
||
) |
empty constructor
concurrency | number of threads for parallel execution |
cancelFlag | indicates user interruption |
frechet::reach::Structure::Structure | ( | const FreeSpace::ptr | fs, |
int | concurrency = 1 , |
||
volatile bool * | cancelFlag = nullptr |
||
) |
default constructor
fs | underlying free-space |
concurrency | number of threads for parallel execution |
cancelFlag | indicates user interruption |
Structure::Structure | ( | const Structure & | that | ) |
Structure::Structure | ( | Structure && | that | ) |
move constructor
that | object to move data from; empty on return |
Definition at line 30 of file structure.cpp.
|
virtual |
destructor; releases all memory
Definition at line 127 of file structure.cpp.
|
static |
for debugging and unit tests, check if reachability intervals are consistent
Definition at line 958 of file structure.cpp.
|
staticprivate |
for debugging and unit tests, check if reachability intervals are consistent
Definition at line 992 of file structure.cpp.
|
inline |
Definition at line 165 of file structure.h.
|
inline |
Definition at line 174 of file structure.h.
|
inline |
ori | horizontal or vertical |
dir | first(=bottom,left) or second (=top,right) |
Definition at line 113 of file structure.h.
|
inline |
ori | horizontal or vertical |
dir | first(=bottom,left) or second (=top,right) |
Definition at line 122 of file structure.h.
|
private |
Divide & Conquer algorithm. Merge regions recursively. Makes use of paralel threads.
r | region to merge (columns,rows in free-space) |
Definition at line 273 of file structure.cpp.
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.
Definition at line 130 of file structure.cpp.
void Structure::calculateColumns | ( | int | i, |
int | j | ||
) |
compute a region of the reachability structure. may span the double free-space!.
i | first column |
j | last column, exclusive |
Definition at line 180 of file structure.cpp.
frechet::reach::Pointer Structure::calculateDouble | ( | ) |
compute the reachability structure for a closed curve, based on a double-free-space-diagram.
Definition at line 167 of file structure.cpp.
void Structure::calculateDouble | ( | Orientation | fringe | ) |
compute the reachability structure for a closed curve, based on a double-free-space-diagram.
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.
Pointer Structure::calculateSingle | ( | ) |
compute the reachability structure for an open curve, based on a single free-space-diagram.
Definition at line 142 of file structure.cpp.
|
private |
adjust the see-through pointers. For see-through segments l:=nullptr, resp. h:=nullptr
p | points to a reachability segment |
Definition at line 603 of file str_singlecell.cpp.
void Structure::copy | ( | const Structure & | that | ) |
assigment function
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.
|
private |
construct part of a single-sell segment
list | list to append |
seg | boundary segments that will be assembled into the list |
Definition at line 634 of file str_singlecell.cpp.
|
private |
create a pair of reachability segments, on opposite sides of the structure
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.
|
private |
create segments for a single cell of the reachability structure
aux | aux. data |
ori | horizontal or vertical intervals? |
y0 | lower bound |
Definition at line 224 of file str_singlecell.cpp.
set up links between four opposite segments. This pointer chain will be used to traverse a reachability structure horizontally.
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.
|
private |
Merge regions recursively. Uses only one thread.
r | region to merge (columns,rows in free-space) |
Definition at line 371 of file structure.cpp.
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.
edge | look for starting point on horizontal edge, of vertical edge |
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.
|
inline |
ori | horizontal or vertical |
Definition at line 129 of file structure.h.
|
inline |
ori | horizontal or vertical |
Definition at line 140 of file structure.h.
|
inline |
Definition at line 106 of file structure.h.
|
static |
compute the arrangement of free-space intervals for one cell
LF | left free-space interval |
RF | right free-space interval |
|
staticprivate |
compute the arrangement of free-space intervals for one cell
aux | aux. data |
ori | horizontal or vertical intervals? |
Definition at line 56 of file str_singlecell.cpp.
|
inline |
first or second part of the reachability structure
dir | first=bottom, second=top |
Definition at line 152 of file structure.h.
|
inline |
Definition at line 161 of file structure.h.
|
inline |
Definition at line 170 of file structure.h.
|
private |
set up the l,h pointers within a single cell
aux | aux. data |
ori | horizontal or vertical intervals? |
Definition at line 424 of file str_singlecell.cpp.
|
private |
mark non-accesible segments
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.
mark one non-accesible segment
p | pointer to a reachability segment |
p2 | pointer to a reachability segment |
|
private |
merge this structure with another structure
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) |
|
private |
merge two adjacent segments. b := a union b
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.
|
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.
ori | horizontal or vertical |
Definition at line 563 of file structure.cpp.
used when traversing reachability segments. Traversal direction is discussed in frechet::reach::Direction.
p | a pointer to a reachability segment |
Definition at line 916 of file structure.cpp.
find next reachable segment
p | a pointer to a reachability segment |
Definition at line 610 of file structure.cpp.
assigment operator
that | object to copy from |
Definition at line 93 of file structure.cpp.
move assigment operator
that | object to move data from; empty on return |
Definition at line 87 of file structure.cpp.
used when traversing reachability segments. Traversal direction is discussed in frechet::reach::Direction.
p | a pointer to a reachability segment |
Definition at line 933 of file structure.cpp.
find previous reachable segment
p | a pointer to a reachability segment |
Definition at line 602 of file structure.cpp.
|
private |
find a reachable interval
seg | list of segments on the opposite edge |
Definition at line 615 of file str_singlecell.cpp.
|
inline |
Definition at line 163 of file structure.h.
|
inline |
Definition at line 172 of file structure.h.
|
private |
scan and merge one segment
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.
|
inline |
ori | horizontal or vertical |
Definition at line 134 of file structure.h.
|
inline |
ori | horizontal or vertical |
Definition at line 145 of file structure.h.
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.
offset | horizontal and vertical offset |
Definition at line 111 of file structure.cpp.
void Structure::singleCell | ( | int | i, |
int | j | ||
) |
create a BoundarySegment from one cell of the free-space-diagram
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 a reachabiliy segment Adjust l,h pointers into that segment.
seg | segment to split |
y | point in interval where to split |
twin | pointer to opposite segment (remains unmodified, but used to track incoming pointers) |
--- --- | | old segment | | | ==> --- y | | | | new segment --- ---
Definition at line 846 of file structure.cpp.
split a reachabiliy segment and its opposite segment
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.
void Structure::swap | ( | Structure & | that | ) |
swap content with another object
that | to swap data with; on return, holds contents of this object |
Definition at line 99 of file structure.cpp.
void Structure::synchIntervals | ( | Orientation | fringe, |
Structure & | that | ||
) |
before mergin two reachabiliry structures, its intervals must be synchronized
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.
void Structure::takeOwnership | ( | ) |
for debugging: fill in owner pointers
Definition at line 592 of file structure.cpp.
|
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.
InterruptedException | thrown when the user requests an interruption. Caught by application logic. |
Definition at line 951 of file structure.cpp.
|
inline |
Definition at line 167 of file structure.h.
|
inline |
Definition at line 176 of file structure.h.
update all l,h, pointers that point into a segment
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.
|
inline |
first or second part of the reachability structure
dir | first=left, second=right |
Definition at line 158 of file structure.h.
|
friend |
Definition at line 46 of file structure.h.
|
friend |
Definition at line 45 of file structure.h.
|
friend |
Definition at line 47 of file structure.h.
|
friend |
Definition at line 44 of file structure.h.
|
private |
Boundaries [HORIZONTAL,VERTICAL] [FIRST,SECOND].
Definition at line 38 of file structure.h.
|
static |
Definition at line 473 of file structure.h.
|
static |
Definition at line 473 of file structure.h.
|
static |
Definition at line 473 of file structure.h.
|
private |
used when running ia a background thread to indicate cancellation by the user
Definition at line 42 of file structure.h.
|
private |
number of parallel threads to use
Definition at line 40 of file structure.h.
|
private |
the underlying free-space; may be nullptr
Definition at line 36 of file structure.h.