![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
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
Avoid calculating offsets back and fort.
Alternatively, use a fixed point representation like FixedPoint { int i; double mantissa; }
#include <fs_path.h>
Inherited by frechet::poly::PolygonFSPath.
Public Types | |
typedef boost::shared_ptr< FSPath > | ptr |
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::Interval & | left (int i, int j) const |
const frechet::data::Interval & | bottom (int i, int j) const |
const Curve & | fixPoints () 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< Interval > | LR |
reachable intervals More... | |
Array2D< Interval > | BR |
Curve | fix |
fix points More... | |
Curve | path [2] |
Path curves(s) More... | |
typedef boost::shared_ptr<FSPath> frechet::reach::FSPath::ptr |
FSPath::FSPath | ( | FreeSpace::ptr | afs | ) |
constructor with free-space
afs | the underlying free-space |
Definition at line 26 of file fs_path.cpp.
|
inlinevirtual |
|
protected |
constructor for derived classes only
Definition at line 19 of file fs_path.cpp.
|
staticprotected |
append a value to a vector, avoiding duplicates
map | a vector of values |
x | new value |
Definition at line 49 of file fs_path.cpp.
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.
path0 | first part of feasible path |
path1 | second part of feasible path |
n | number of vertexes on P |
m | number of vertexes on Q |
Definition at line 845 of file fs_path.cpp.
|
staticprotected |
find a point by its x coordinate
curve | a polygonal curve, assumed to be sorted |
x | x-coordinate of a point |
Definition at line 158 of file fs_path.cpp.
|
staticprotected |
find a point by its y coordinate
curve | a polygonal curve, assumed to be sorted |
y | y-coordinate of a point |
Definition at line 174 of file fs_path.cpp.
|
inline |
|
protected |
test the reachability interval on the bottom of a cell
i | column in free-space |
j | row in free-space |
x | point to test |
prec | numerical precision for comparing intervals |
Definition at line 645 of file fs_path.cpp.
|
protected |
calculate the feasible path
Definition at line 674 of file fs_path.cpp.
void FSPath::calculateReachability | ( | Point | start, |
Point | end, | ||
bool | allow_wrap, | ||
double | prec = PRECISION |
||
) |
update L^R and B from Free-Space diagram
start | start location in free-space diagram (column and row) |
end | destination location in free-space diagram (column and row) |
allow_wrap | allow to wrap at edges of free-space |
prec | numerical precision for comparing intervals |
Definition at line 429 of file fs_path.cpp.
|
virtual |
Definition at line 222 of file fs_path.cpp.
void FSPath::clearReachability | ( | ) |
Definition at line 213 of file fs_path.cpp.
copy parts of a curve
dest | destination curve |
source | input curve |
i | start index to copy from |
j | end index |
Definition at line 190 of file fs_path.cpp.
|
inline |
compute one segment of the feasible path. THe path is completed from top-right backwards to bottom-left.
a | destination point (bottom-left) |
b | start point (top-right) |
curve | holds the new segments on return |
cc | holds the number of curve segments on return |
Definition at line 705 of file fs_path.cpp.
|
inline |
Curve FSPath::getPath | ( | int | i | ) | const |
get the feasible path for display on screen. May be split into two parts.
i | 0 or 1 |
Definition at line 36 of file fs_path.cpp.
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
i | column in free-space |
j | row in free-space |
prec | numerical precision for comparing intervals |
follow the reachable intervals and test whether a point is reachable from the start
a | point in free-space |
prec | numerical precision for comparing intervals |
|
inline |
|
protected |
test the reachability interval on the left of a cell
i | column in free-space |
j | row in free-space |
y | point to test |
prec | numerical precision for comparing intervals |
Definition at line 637 of file fs_path.cpp.
for a line segment in P, find the mapped part of the feasible path
pseg | line segment in P |
result | on return, holds the feasible path segment that maps to the P line segment |
Definition at line 55 of file fs_path.cpp.
Point FSPath::mapFromP | ( | int | p | ) | const |
Definition at line 822 of file fs_path.cpp.
double FSPath::mapFromPToQ | ( | int | p | ) | const |
Definition at line 811 of file fs_path.cpp.
Definition at line 90 of file fs_path.cpp.
Point FSPath::mapFromQ | ( | int | q | ) | const |
Definition at line 833 of file fs_path.cpp.
double FSPath::mapFromQToP | ( | int | q | ) | const |
Definition at line 817 of file fs_path.cpp.
void FSPath::mapToP | ( | Curve | path[2] | ) | const |
Definition at line 125 of file fs_path.cpp.
void FSPath::mapToQ | ( | Curve | path[2] | ) | const |
Definition at line 142 of file fs_path.cpp.
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.
a | relative offset on line segment |
p1 | start of line |
p2 | end of line |
Definition at line 44 of file fs_path.cpp.
|
protected |
Definition at line 198 of file fs_path.cpp.
|
protected |
Definition at line 205 of file fs_path.cpp.
Calculate reachability interval opposite to a given interval.
LR | Left (or bottom) Rechability |
RF | Right (or top) Free-Space |
Definition at line 398 of file fs_path.cpp.
|
static |
propagate the reachable intervals within one cell. from bottom and left to right and top
RF | free-space interval on the right edge of the cell |
TF | free-space interval on the top edge of the cell |
LR | reachable interval on the left edge |
BR | reachable interval on the bottom edge |
RR | holds on return the reachable interval on the right edge |
TR | holds on return the reachable interval on the top edge |
Definition at line 406 of file fs_path.cpp.
|
protected |
propagate the reachable intervals within one cell. The cell is located at the bottom of the free-space diagram.
i | column in free-space |
j | row in free-space |
bx | x-coordinate of destination point |
by | y-coordinate of destination point |
Definition at line 367 of file fs_path.cpp.
|
protected |
propagate the reachable intervals along a bottom row of the free-space diagram.
i | column in free-space |
j0 | bottom row in free-space |
bx | x-coordinate of destination point |
by | y-coordinate of destination point |
allow_wrap | if true, wrap at the top edge |
Definition at line 605 of file fs_path.cpp.
|
protected |
propagate the reachable intervals along a column of the free-space diagram.
i | column in free-space |
j0 | bottom row in free-space |
bx | x-coordinate of destination point |
by | y-coordinate of destination point |
allow_wrap | if true, wrap at the top edge |
Definition at line 574 of file fs_path.cpp.
propagate the reachable intervals along the horizontal axis
a | start point |
bx | destination coordinate |
prec | numerical precision for comparing intervals |
Definition at line 229 of file fs_path.cpp.
|
protected |
propagate the reachable intervals within one cell. The cell is located in the inner part of the free-space diagram.
i | column in free-space |
j | row in free-space |
bx | x-coordinate of destination point, |
by | y-coordinate of destination point |
Definition at line 321 of file fs_path.cpp.
propagate the reachable intervals along the vertical axis
a | start point |
by | destination coordinate |
prec | numerical precision for comparing intervals |
Definition at line 275 of file fs_path.cpp.
|
inline |
pick a point from a reachability interval
segment | interval of a reachability structure |
Definition at line 541 of file fs_path.cpp.
void FSPath::update | ( | Point | start, |
double | epsilon | ||
) |
compute a feasible path from the free-space diagram
start | start point |
epsilon |
Definition at line 484 of file fs_path.cpp.
|
protected |
|
protected |
|
static |
|
protected |
|
protected |