Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
components.h
Go to the documentation of this file.
1 #ifndef COMPONENTS_H
2 #define COMPONENTS_H
3 
4 #include <boost/pending/disjoint_sets.hpp>
5 #include <interval.h>
6 #include <array2d.h>
7 #include <bitset.h>
8 
9 namespace frechet { namespace fs {
10 
11 class FreeSpace;
12 class Cell;
13 
27 class Components {
28 
29 public:
31  typedef boost::disjoint_sets_with_storage<> DisjointSet;
35 
36 private:
37  int n;
38  int m;
40  //size_t countID;
42 
49 
56  component_id_t componentID(int i, int j);
57 
58 public:
66  Components(int n, int m);
70  void clear();
77  component_id_t representative(int i, int j);
78 
84 
86  component_id_t count() const { return intervalSet.count(); }
87 
91  data::BitSet::iterator end() const { return intervalSet.end(); }
92 
97 
99  const IntervalArray& intervals() const { return intervalArray; }
100 
101 private:
109  component_id_t assignComponent(const FreeSpace& fs, int i, int j);
114  void normalize();
115 };
116 
117 } } // namespace
118 
119 #endif // COMPONENTS_H
DisjointSet disjointSet
disjoint set of component IDs.
Definition: components.h:39
an iterator over a BitSet
Definition: bitset.h:93
data::BitSet::iterator first() const
Definition: components.h:94
iterator begin() const
Definition: bitset.cpp:128
global definitions for all algorithms.
iterator first() const
Definition: bitset.h:170
boost::disjoint_sets_with_storage DisjointSet
union-find structure, or disjoint set
Definition: components.h:31
component_id_t count() const
Definition: components.h:86
int m
number of vertexes in Q. Number of grid rows is m-1.
Definition: components.h:38
int n
number of vertexes in P. Number of grid columns is n-1.
Definition: components.h:37
iterator last() const
Definition: bitset.h:172
data::BitSet::iterator end() const
Definition: components.h:91
const IntervalArray & intervals() const
Definition: components.h:99
component_id_t componentID(int i, int j)
get the component for a cell
Definition: components.cpp:20
Components(int n, int m)
default constrcutor
Definition: components.cpp:24
void calculateComponents(FreeSpace &fs)
calculate connected components
Definition: components.cpp:56
Free-Space connected components and their projections to the domain axes.
Definition: components.h:27
iterator end() const
Definition: bitset.h:167
data::BitSet::iterator last() const
Definition: components.h:96
data::Array2D< data::IntervalPair > IntervalArray
Definition: components.h:34
data::BitSet::iterator begin() const
Definition: components.h:89
A simple bit vector of fixed size.
Definition: bitset.h:16
data::BitSet intervalSet
contains the valid representatives (a subset of all cells)
Definition: components.h:48
The FreeSpace class models the Free-Space Diagram calculated from two curves.
Definition: freespace.h:83
component_id_t representative(int i, int j)
find the component ID of a cell
Definition: components.cpp:202
void normalize()
normalize union-find structure. for each component, find the smallest representative.
Definition: components.cpp:207
int count() const
This methods is expensive, as it scans the whole array.
Definition: bitset.cpp:58
component_id_t assignComponent(const FreeSpace &fs, int i, int j)
compute component ID for a cell
Definition: components.cpp:110
void clear()
clear the component set
Definition: components.cpp:34
unsigned int component_id_t
used as identifier for free-space components
Definition: types.h:74
static const component_id_t NO_COMPONENT
empty cells have an invalid component ID
Definition: components.h:60
IntervalArray intervalArray
has an entry for every cell (nxm)
Definition: components.h:46