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

Detailed Description

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

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

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

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

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

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

  1. without offset
  2. with identically calculated offset

Avoid calculating offsets back and fort.

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

Author
Peter Schäfer

Definition at line 44 of file fs_path.h.

#include <fs_path.h>

Inherited by frechet::poly::PolygonFSPath.

Public Types

typedef boost::shared_ptr< FSPathptr
 smart pointer to an FSPath object More...
 

Public Member Functions

 FSPath (FreeSpace::ptr afs)
 constructor with free-space More...
 
virtual ~FSPath ()
 destructor More...
 
bool empty () const
 
Curve getPath (int i) const
 get the feasible path for display on screen. May be split into two parts. More...
 
void mapFromP (Segment pseg, Curve result[2]) const
 for a line segment in P, find the mapped part of the feasible path More...
 
void mapFromQ (Segment pseg, Curve result[2]) const
 
void mapToP (Curve path[2]) const
 
void mapToQ (Curve path[2]) const
 
Point mapFromP (int p) const
 
Point mapFromQ (int q) const
 
double mapFromPToQ (int p) const
 
double mapFromQToP (int q) const
 
const frechet::data::Intervalleft (int i, int j) const
 
const frechet::data::Intervalbottom (int i, int j) const
 
const CurvefixPoints () const
 
void clearReachability ()
 
virtual void clear ()
 
void calculateReachability (Point start, Point end, bool allow_wrap, double prec=PRECISION)
 update L^R and B from Free-Space diagram More...
 
void update (Point start, double epsilon)
 compute a feasible path from the free-space diagram More...
 
Point toPoint (Pointer segment)
 pick a point from a reachability interval More...
 
bool isReachable (int i, int j, double prec=PRECISION) const
 follow the reachable intervals and test whether a point is reachable from the start More...
 
bool isReachable (Point a, double prec=PRECISION) const
 follow the reachable intervals and test whether a point is reachable from the start More...
 
Point startPoint () const
 

Static Public Member Functions

static Interval opposite (const Interval &LR, const Interval &RF)
 
static void propagate (const Interval &RF, const Interval &TF, const Interval &LR, const Interval &BR, Interval &RR, Interval &TR)
 propagate the reachable intervals within one cell. from bottom and left to right and top More...
 

Static Public Attributes

static const double PRECISION = 1e-9
 floating point precision More...
 

Protected Member Functions

 FSPath ()
 constructor for derived classes only More...
 
void calculatePath ()
 calculate the feasible path More...
 
void findPathSegment (Point a, Point b, Curve curve[2], int &cc)
 compute one segment of the feasible path. THe path is completed from top-right backwards to bottom-left. More...
 
bool propagateHorizontalEdge (Point a, double bx, double prec=PRECISION)
 propagate the reachable intervals along the horizontal axis More...
 
bool propagateVerticalEdge (Point a, double by, double prec=PRECISION)
 propagate the reachable intervals along the vertical axis More...
 
void propagateInner (int i, int j, double bx, double by)
 propagate the reachable intervals within one cell. The cell is located in the inner part of the free-space diagram. More...
 
void propagateBottom (int i, int j, double bx, double by)
 propagate the reachable intervals within one cell. The cell is located at the bottom of the free-space diagram. More...
 
int next_hor (int i)
 
int next_vert (int j)
 
bool left_contains (int i, int j, double y, double prec=PRECISION) const
 test the reachability interval on the left of a cell More...
 
bool bottom_contains (int i, int j, double x, double prec=PRECISION) const
 test the reachability interval on the bottom of a cell More...
 
void propagateColumn (int i, int j0, double bx, double by, bool allow_wrap)
 propagate the reachable intervals along a column of the free-space diagram. More...
 
void propagateBottom (int i, int j0, double bx, double by, bool allow_wrap)
 propagate the reachable intervals along a bottom row of the free-space diagram. More...
 

Static Protected Member Functions

static double mapToSegment (double a, Point p1, Point p2)
 map a relative offset to a line segment. For values in [0..1] the resulting point is one the line segment. For value <0 or >1 the resulting point would be off the line segment. More...
 
static void append (std::vector< double > &map, double x)
 append a value to a vector, avoiding duplicates More...
 
static int binSearchX (const Curve &curve, int x)
 find a point by its x coordinate More...
 
static int binSearchY (const Curve &curve, int y)
 find a point by its y coordinate More...
 
static void copy (Curve &dest, const Curve &source, int i, int j)
 copy parts of a curve More...
 
static bool are_consistent (Curve path0, Curve path1, int n, int m)
 test if two curves are consistent with being a feasible path. Both curves must be monotone (asecning x and y-coordinates), wrap at the right or top edge. Used for debuggin and unit tests. More...
 

Protected Attributes

FreeSpace::ptr fs
 underlying free-space More...
 
bool wrapTop
 free-space wraps at top, Q is closed More...
 
bool wrapRight
 free-space wraps right, P is closed More...
 
Array2D< IntervalLR
 reachable intervals More...
 
Array2D< IntervalBR
 
Curve fix
 fix points More...
 
Curve path [2]
 Path curves(s) More...
 

Member Typedef Documentation

◆ ptr

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

smart pointer to an FSPath object

Definition at line 65 of file fs_path.h.

Constructor & Destructor Documentation

◆ FSPath() [1/2]

FSPath::FSPath ( FreeSpace::ptr  afs)

constructor with free-space

Parameters
afsthe underlying free-space

Definition at line 26 of file fs_path.cpp.

◆ ~FSPath()

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

destructor

Definition at line 75 of file fs_path.h.

◆ FSPath() [2/2]

FSPath::FSPath ( )
protected

constructor for derived classes only

Definition at line 19 of file fs_path.cpp.

Member Function Documentation

◆ append()

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

append a value to a vector, avoiding duplicates

Parameters
mapa vector of values
xnew value

Definition at line 49 of file fs_path.cpp.

◆ are_consistent()

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

test if two curves are consistent with being a feasible path. Both curves must be monotone (asecning x and y-coordinates), wrap at the right or top edge. Used for debuggin and unit tests.

Parameters
path0first part of feasible path
path1second part of feasible path
nnumber of vertexes on P
mnumber of vertexes on Q
Returns
true, if the two parts are properly monotone

Definition at line 845 of file fs_path.cpp.

◆ binSearchX()

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

find a point by its x coordinate

Parameters
curvea polygonal curve, assumed to be sorted
xx-coordinate of a point
Returns
index of x, or -i-1 for the index where x should be inserted

Definition at line 158 of file fs_path.cpp.

◆ binSearchY()

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

find a point by its y coordinate

Parameters
curvea polygonal curve, assumed to be sorted
yy-coordinate of a point
Returns
index of y, or -i-1 for the index where x should be inserted

Definition at line 174 of file fs_path.cpp.

◆ bottom()

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

Definition at line 114 of file fs_path.h.

◆ bottom_contains()

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

test the reachability interval on the bottom of a cell

Parameters
icolumn in free-space
jrow in free-space
xpoint to test
precnumerical precision for comparing intervals
Returns
true if x is contained in the bottom reachable interval in cell (i,j)

Definition at line 645 of file fs_path.cpp.

◆ calculatePath()

void FSPath::calculatePath ( )
protected

calculate the feasible path

Definition at line 674 of file fs_path.cpp.

◆ calculateReachability()

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

update L^R and B from Free-Space diagram

Parameters
startstart location in free-space diagram (column and row)
enddestination location in free-space diagram (column and row)
allow_wrapallow to wrap at edges of free-space
precnumerical precision for comparing intervals

Definition at line 429 of file fs_path.cpp.

◆ clear()

void FSPath::clear ( )
virtual

Definition at line 222 of file fs_path.cpp.

◆ clearReachability()

void FSPath::clearReachability ( )

Definition at line 213 of file fs_path.cpp.

◆ copy()

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

copy parts of a curve

Parameters
destdestination curve
sourceinput curve
istart index to copy from
jend index

Definition at line 190 of file fs_path.cpp.

◆ empty()

bool frechet::reach::FSPath::empty ( ) const
inline
Returns
true, if there is no feasible path

Definition at line 80 of file fs_path.h.

◆ findPathSegment()

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

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

Parameters
adestination point (bottom-left)
bstart point (top-right)
curveholds the new segments on return
ccholds the number of curve segments on return

Definition at line 705 of file fs_path.cpp.

◆ fixPoints()

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

Definition at line 118 of file fs_path.h.

◆ getPath()

Curve FSPath::getPath ( int  i) const

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

Parameters
i0 or 1
Returns
first or second part of the feasible path

Definition at line 36 of file fs_path.cpp.

◆ isReachable() [1/2]

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

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

Parameters
icolumn in free-space
jrow in free-space
precnumerical precision for comparing intervals
Returns
true, if q is reachable from p

◆ isReachable() [2/2]

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

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

Parameters
apoint in free-space
precnumerical precision for comparing intervals
Returns
true, if q is reachable from p

◆ left()

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

Definition at line 110 of file fs_path.h.

◆ left_contains()

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

test the reachability interval on the left of a cell

Parameters
icolumn in free-space
jrow in free-space
ypoint to test
precnumerical precision for comparing intervals
Returns
true if y is contained in the left reachable interval in cell (i,j)

Definition at line 637 of file fs_path.cpp.

◆ mapFromP() [1/2]

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

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

Parameters
psegline segment in P
resulton return, holds the feasible path segment that maps to the P line segment

Definition at line 55 of file fs_path.cpp.

◆ mapFromP() [2/2]

Point FSPath::mapFromP ( int  p) const

Definition at line 822 of file fs_path.cpp.

◆ mapFromPToQ()

double FSPath::mapFromPToQ ( int  p) const

Definition at line 811 of file fs_path.cpp.

◆ mapFromQ() [1/2]

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

Definition at line 90 of file fs_path.cpp.

◆ mapFromQ() [2/2]

Point FSPath::mapFromQ ( int  q) const

Definition at line 833 of file fs_path.cpp.

◆ mapFromQToP()

double FSPath::mapFromQToP ( int  q) const

Definition at line 817 of file fs_path.cpp.

◆ mapToP()

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

Definition at line 125 of file fs_path.cpp.

◆ mapToQ()

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

Definition at line 142 of file fs_path.cpp.

◆ mapToSegment()

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

map a relative offset to a line segment. For values in [0..1] the resulting point is one the line segment. For value <0 or >1 the resulting point would be off the line segment.

Parameters
arelative offset on line segment
p1start of line
p2end of line
Returns
mapped point

Definition at line 44 of file fs_path.cpp.

◆ next_hor()

int FSPath::next_hor ( int  i)
protected
Returns
the next column, possible wrapping around the right edge

Definition at line 198 of file fs_path.cpp.

◆ next_vert()

int FSPath::next_vert ( int  j)
protected
Returns
the next row, possible wrapping around the top edge

Definition at line 205 of file fs_path.cpp.

◆ opposite()

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

Calculate reachability interval opposite to a given interval.

Parameters
LRLeft (or bottom) Rechability
RFRight (or top) Free-Space
Returns
result RR Right Reachability

Definition at line 398 of file fs_path.cpp.

◆ propagate()

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

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

Parameters
RFfree-space interval on the right edge of the cell
TFfree-space interval on the top edge of the cell
LRreachable interval on the left edge
BRreachable interval on the bottom edge
RRholds on return the reachable interval on the right edge
TRholds on return the reachable interval on the top edge

Definition at line 406 of file fs_path.cpp.

◆ propagateBottom() [1/2]

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

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

Parameters
icolumn in free-space
jrow in free-space
bxx-coordinate of destination point
byy-coordinate of destination point

Definition at line 367 of file fs_path.cpp.

◆ propagateBottom() [2/2]

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

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

Parameters
icolumn in free-space
j0bottom row in free-space
bxx-coordinate of destination point
byy-coordinate of destination point
allow_wrapif true, wrap at the top edge

Definition at line 605 of file fs_path.cpp.

◆ propagateColumn()

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

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

Parameters
icolumn in free-space
j0bottom row in free-space
bxx-coordinate of destination point
byy-coordinate of destination point
allow_wrapif true, wrap at the top edge

Definition at line 574 of file fs_path.cpp.

◆ propagateHorizontalEdge()

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

propagate the reachable intervals along the horizontal axis

Parameters
astart point
bxdestination coordinate
precnumerical precision for comparing intervals
Returns
false, if the start point is not reachable

Definition at line 229 of file fs_path.cpp.

◆ propagateInner()

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

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

Parameters
icolumn in free-space
jrow in free-space
bxx-coordinate of destination point,
byy-coordinate of destination point

Definition at line 321 of file fs_path.cpp.

◆ propagateVerticalEdge()

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

propagate the reachable intervals along the vertical axis

Parameters
astart point
bydestination coordinate
precnumerical precision for comparing intervals
Returns
false, if the start point is not reachable

Definition at line 275 of file fs_path.cpp.

◆ startPoint()

Point frechet::reach::FSPath::startPoint ( ) const
inline
Returns
start of feasible path

Definition at line 168 of file fs_path.h.

◆ toPoint()

Point FSPath::toPoint ( Pointer  segment)

pick a point from a reachability interval

Parameters
segmentinterval of a reachability structure
Returns
a point within the interval, a candidate for a feasible path

Definition at line 541 of file fs_path.cpp.

◆ update()

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

compute a feasible path from the free-space diagram

Parameters
startstart point
epsilon

Definition at line 484 of file fs_path.cpp.

Member Data Documentation

◆ BR

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

Definition at line 54 of file fs_path.h.

◆ fix

Curve frechet::reach::FSPath::fix
protected

fix points

Definition at line 56 of file fs_path.h.

◆ fs

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

underlying free-space

Definition at line 48 of file fs_path.h.

◆ LR

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

reachable intervals

Definition at line 54 of file fs_path.h.

◆ path

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

Path curves(s)

Definition at line 58 of file fs_path.h.

◆ PRECISION

const double FSPath::PRECISION = 1e-9
static

floating point precision

Definition at line 61 of file fs_path.h.

◆ wrapRight

bool frechet::reach::FSPath::wrapRight
protected

free-space wraps right, P is closed

Definition at line 52 of file fs_path.h.

◆ wrapTop

bool frechet::reach::FSPath::wrapTop
protected

free-space wraps at top, Q is closed

Definition at line 50 of file fs_path.h.


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