Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::fs::Components Class Reference

Detailed Description

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

Author
Peter Schäfer

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::IntervalPairIntervalArray
 

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 IntervalArrayintervals () 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...
 

Member Typedef Documentation

◆ DisjointSet

typedef boost::disjoint_sets_with_storage frechet::fs::Components::DisjointSet

union-find structure, or disjoint set

Definition at line 31 of file components.h.

◆ IntervalArray

maps components to their component bounding boxes. Bounding boxes are represented by a pair of intervals.

Definition at line 34 of file components.h.

Constructor & Destructor Documentation

◆ Components()

Components::Components ( int  n,
int  m 
)

default constrcutor

Parameters
nnumber of vertexes in P
mnumber of vertexes in Q

Definition at line 24 of file components.cpp.

Member Function Documentation

◆ assignComponent()

component_id_t Components::assignComponent ( const FreeSpace fs,
int  i,
int  j 
)
private

compute component ID for a cell

Parameters
fsfree-space diagram
igrid column
jgrid row
Returns
component ID for the cell

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.

◆ begin()

data::BitSet::iterator frechet::fs::Components::begin ( ) const
inline
Returns
iterator to the beginning of the component set

Definition at line 89 of file components.h.

◆ calculateComponents()

void Components::calculateComponents ( FreeSpace fs)

calculate connected components

Parameters
fsthe 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.

◆ clear()

void Components::clear ( )

clear the component set

Definition at line 34 of file components.cpp.

◆ componentID()

component_id_t Components::componentID ( int  i,
int  j 
)
private

get the component for a cell

Parameters
igrid column
jgrid row
Returns
the component ID of a cell

component ID servers as identifier for the Union-Find structure and as index into intervals array.

Definition at line 20 of file components.cpp.

◆ count()

component_id_t frechet::fs::Components::count ( ) const
inline
Returns
total number of connected components

Definition at line 86 of file components.h.

◆ end()

data::BitSet::iterator frechet::fs::Components::end ( ) const
inline
Returns
iterator past the end of the component set

Definition at line 91 of file components.h.

◆ first()

data::BitSet::iterator frechet::fs::Components::first ( ) const
inline
Returns
iterator to the first entry of the component set

Definition at line 94 of file components.h.

◆ intervals()

const IntervalArray& frechet::fs::Components::intervals ( ) const
inline
Returns
bounding boxes for components

Definition at line 99 of file components.h.

◆ last()

data::BitSet::iterator frechet::fs::Components::last ( ) const
inline
Returns
iterator to the last entry of the component set

Definition at line 96 of file components.h.

◆ normalize()

void Components::normalize ( )
private

normalize union-find structure. for each component, find the smallest representative.

Definition at line 207 of file components.cpp.

◆ representative()

component_id_t Components::representative ( int  i,
int  j 
)

find the component ID of a cell

Parameters
igrid column
jgrid row
Returns
the cell's component ID, or NO_COMPONENT

Definition at line 202 of file components.cpp.

Member Data Documentation

◆ disjointSet

DisjointSet frechet::fs::Components::disjointSet
private

disjoint set of component IDs.

Definition at line 39 of file components.h.

◆ intervalArray

IntervalArray frechet::fs::Components::intervalArray
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.

◆ intervalSet

data::BitSet frechet::fs::Components::intervalSet
private

contains the valid representatives (a subset of all cells)

Definition at line 48 of file components.h.

◆ m

int frechet::fs::Components::m
private

number of vertexes in Q. Number of grid rows is m-1.

Definition at line 38 of file components.h.

◆ n

int frechet::fs::Components::n
private

number of vertexes in P. Number of grid columns is n-1.

Definition at line 37 of file components.h.

◆ NO_COMPONENT

const component_id_t Components::NO_COMPONENT = (component_id_t)SIZE_MAX
static

empty cells have an invalid component ID

Definition at line 60 of file components.h.


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