![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
Free-Space connected components and their projections to the domain axes.
Used by the k-Frechet algorithm. Atfer computing the free-space diagram, we find connected components and project their bounding box to the x- and y-axis.
For finding connected component, we use a union-find structure. Free-space cells are connected if their adjacent free intervals are not empty.
Each component is identified by a unique ID of type component_id_t
Definition at line 27 of file components.h.
#include <components.h>
Public Types | |
typedef boost::disjoint_sets_with_storage | DisjointSet |
union-find structure, or disjoint set More... | |
typedef data::Array2D< data::IntervalPair > | IntervalArray |
Public Member Functions | |
Components (int n, int m) | |
default constrcutor More... | |
void | clear () |
clear the component set More... | |
component_id_t | representative (int i, int j) |
find the component ID of a cell More... | |
void | calculateComponents (FreeSpace &fs) |
calculate connected components More... | |
component_id_t | count () const |
data::BitSet::iterator | begin () const |
data::BitSet::iterator | end () const |
data::BitSet::iterator | first () const |
data::BitSet::iterator | last () const |
const IntervalArray & | intervals () const |
Static Public Attributes | |
static const component_id_t | NO_COMPONENT = (component_id_t)SIZE_MAX |
empty cells have an invalid component ID More... | |
Private Member Functions | |
component_id_t | componentID (int i, int j) |
get the component for a cell More... | |
component_id_t | assignComponent (const FreeSpace &fs, int i, int j) |
compute component ID for a cell More... | |
void | normalize () |
normalize union-find structure. for each component, find the smallest representative. More... | |
Private Attributes | |
int | n |
number of vertexes in P. Number of grid columns is n-1. More... | |
int | m |
number of vertexes in Q. Number of grid rows is m-1. More... | |
DisjointSet | disjointSet |
disjoint set of component IDs. More... | |
IntervalArray | intervalArray |
has an entry for every cell (nxm) More... | |
data::BitSet | intervalSet |
contains the valid representatives (a subset of all cells) More... | |
typedef boost::disjoint_sets_with_storage frechet::fs::Components::DisjointSet |
union-find structure, or disjoint set
Definition at line 31 of file components.h.
maps components to their component bounding boxes. Bounding boxes are represented by a pair of intervals.
Definition at line 34 of file components.h.
Components::Components | ( | int | n, |
int | m | ||
) |
default constrcutor
n | number of vertexes in P |
m | number of vertexes in Q |
Definition at line 24 of file components.cpp.
|
private |
compute component ID for a cell
fs | free-space diagram |
i | grid column |
j | grid row |
Examine one cell in the free-space diagram. Find connected neighbors and update the union-find set.
Definition at line 110 of file components.cpp.
|
inline |
Definition at line 89 of file components.h.
void Components::calculateComponents | ( | FreeSpace & | fs | ) |
calculate connected components
fs | the underlying Free-space diagram |
initially each cell is identified by their grid location. Then we start finding connected components using the union-find set.
Definition at line 56 of file components.cpp.
void Components::clear | ( | ) |
clear the component set
Definition at line 34 of file components.cpp.
|
private |
get the component for a cell
i | grid column |
j | grid row |
component ID servers as identifier for the Union-Find structure and as index into intervals array.
Definition at line 20 of file components.cpp.
|
inline |
Definition at line 86 of file components.h.
|
inline |
Definition at line 91 of file components.h.
|
inline |
Definition at line 94 of file components.h.
|
inline |
Definition at line 99 of file components.h.
|
inline |
Definition at line 96 of file components.h.
|
private |
normalize union-find structure. for each component, find the smallest representative.
Definition at line 207 of file components.cpp.
component_id_t Components::representative | ( | int | i, |
int | j | ||
) |
find the component ID of a cell
i | grid column |
j | grid row |
Definition at line 202 of file components.cpp.
|
private |
disjoint set of component IDs.
Definition at line 39 of file components.h.
|
private |
has an entry for every cell (nxm)
Alternatively, we could use a hash map <component_id_t,IntervalPair> and save some memory. Memory requirements are modest, however.
Definition at line 46 of file components.h.
|
private |
contains the valid representatives (a subset of all cells)
Definition at line 48 of file components.h.
|
private |
number of vertexes in Q. Number of grid rows is m-1.
Definition at line 38 of file components.h.
|
private |
number of vertexes in P. Number of grid columns is n-1.
Definition at line 37 of file components.h.
|
static |
empty cells have an invalid component ID
Definition at line 60 of file components.h.