Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
components.cpp
Go to the documentation of this file.
1 #include <boost/iterator/counting_iterator.hpp>
2 
3 #include <components.h>
4 #include <types.h>
5 #include <freespace.h>
6 #include <limits.h>
7 
8 #include <QDebug>
9 #include <iostream>
10 
11 using namespace frechet;
12 using namespace data;
13 using namespace fs;
14 
21  return intervalArray.offset(i,j);
22 }
23 
24 Components::Components(int an, int am) :
25  n(an), m(am),
26  disjointSet(),
27  //countID(0),
28  intervalArray(std::max(n-1,0),std::max(m-1,0)),
29  intervalSet(intervalArray.n * intervalArray.m)
30 {
31  clear();
32 }
33 
36 
37  if ((n > 0) && (m > 0)) {
38  disjointSet = DisjointSet((n-1)*(m-1));
39  // TODO disjointSet.clear()
40  //intervals.resize((n-1)*(m-1));
41  }
42 }
43 
44 //size_t frechet::Components::newComponent()
45 //{
46 // disjointSet.make_set(++countID);
47 // intervals.resize(countID+1);
48 // return countID;
49 //}
50 
57 {
58  clear();
59 
60  int i,j;
61  for(i=0; i < (fs.n-1); ++i)
62  for(j=0; j < (fs.m-1); ++j)
63  if (fs.cellEmptyBounds(i,j))
64  {
65  component_id_t thisRep=componentID(i,j);
66  disjointSet.make_set(thisRep); // singleton component without an interval
67  intervalSet -= thisRep;
68  //intervalArray.at(i,j).clear();
69  }
70  else {
71  component_id_t thisRep = assignComponent(fs,i,j);
72  Q_ASSERT(intervalSet[thisRep]);
73  }
74 
75  //normalize(); // DONT this destroys the relation between disjointSet and intervals set
76 
77  // now, let's list all components and their intervals
78 /* std::cout << "===========================\n";
79  Array2DSet<IntervalPair>::iterator it = intervals.begin();
80  for( ; it.valid(); )
81  {
82  Q_ASSERT(*it == intervals.at(it.offset()));
83  Q_ASSERT(*it == intervals.at(it.i(),it.j()));
84  std::cout << " ["<<it.offset()<<"] "
85  << " ("<<it.i()<<","<<it.j()<<") "
86  << *it
87  << "\n";
88  ++it;
89  }
90  std::cout << "===========================\n";
91  // disjointSet and interval set must be in synch
92  for(i=0; i < (fs.n-1); ++i)
93  {
94  for(j=0; j < (fs.m-1); ++j)
95  if (! fs.cellEmpty(i,j)) {
96  size_t rep = representative(i,j);
97  if (!intervals.contains(rep)) {
98  std::cout << rep << " gone missing " << intervals.at(rep) << "\n";
99  }
100  }
101  }
102  std::cout << "\n";
103 */
104 }
105 
111 {
112  const Cell& cl = fs.cell(i,j);
113 
114  component_id_t thisRep = componentID(i,j);
115  disjointSet.make_set(thisRep);
116 
117  bool connectLeft = (i > 0) && cl.L;
118  bool connectBottom = (j > 0) && cl.B;
119 
120  IntervalPair thisBounds = cl.bounds.translated(i,j);
121  if (!connectLeft && !connectBottom) {
122  // singleton component
124  intervalArray.at(i,j) = thisBounds;
125  return thisRep;
126  }
127 
129  if (connectLeft) {
130  leftRep = representative(i-1,j); // component REPRESENTATIVE of left neighbor
131  Q_ASSERT(intervalSet[leftRep]); // representatives MUST be in the interval set, too
132  }
133  if (connectBottom) {
134  bottomRep = representative(i,j-1); // component REPRESENTATIVE of bottom neighbor
135  Q_ASSERT(intervalSet[bottomRep]);
136  }
137 
138  if (connectLeft && connectBottom) {
139  disjointSet.link(leftRep,thisRep);
140  if (leftRep!=bottomRep)
141  disjointSet.union_set(leftRep,bottomRep);
142  }
143  else if (connectLeft) {
144  disjointSet.link(leftRep,thisRep);
145  }
146  else /*if (connectBottom)*/ {
147  Q_ASSERT(connectBottom);
148  disjointSet.link(bottomRep,thisRep);
149  }
150 
151  component_id_t newRep = disjointSet.find_set(thisRep);
152 
153  Q_ASSERT((newRep==leftRep) || (newRep==bottomRep) || (newRep==thisRep));
154 
155  if (newRep==leftRep) {
156  Q_ASSERT(intervalSet[leftRep]);
157  IntervalPair& ival = intervalArray[leftRep];
158  if (connectBottom && (bottomRep!=leftRep)) {
159  intervalSet -= bottomRep;
160  ival += intervalArray[bottomRep];
161  }
162  ival += thisBounds;
163  }
164  else if (newRep==bottomRep) {
165  Q_ASSERT(intervalSet[bottomRep]);
166  IntervalPair& ival = intervalArray[bottomRep];
167  if (connectLeft && (leftRep!=bottomRep)) {
168  intervalSet -= leftRep;
169  ival += intervalArray[leftRep];
170  }
171  ival += thisBounds;
172  }
173  else {
174  Q_ASSERT(newRep==thisRep);
175  intervalSet += thisRep;
176  IntervalPair& ival = intervalArray[thisRep] = thisBounds;
177  Q_ASSERT(intervalSet[thisRep]);
178  if (connectBottom) {
179  intervalSet -= bottomRep;
180  ival += intervalArray[bottomRep];
181  }
182  if (connectLeft) {
183  intervalSet -= leftRep;
184  ival += intervalArray[leftRep];
185  }
186  }
187 
188  Q_ASSERT(!connectLeft || (representative(i-1,j)==newRep));
189  Q_ASSERT(!connectBottom || (representative(i,j-1)==newRep));
190  Q_ASSERT(representative(i,j)==newRep);
191 
192  // intervals[newRep] contains now the union of all three (or two) intervals
193  Q_ASSERT(representative(i,j)==newRep && intervalSet[newRep]);
194  Q_ASSERT(!connectLeft || (representative(i-1,j)==newRep &&
195  (leftRep==newRep || !intervalSet[leftRep])));
196  Q_ASSERT(!connectBottom || (representative(i,j-1)==newRep &&
197  (bottomRep==newRep || !intervalSet[bottomRep])));
198  Q_ASSERT(intervalSet[newRep]);
199  return newRep;
200 }
201 
203  return disjointSet.find_set(componentID(i,j));
204  // representative of the component
205 }
206 
208 {
209  // normalize components
210  if ((n > 0) && (m > 0))
211  disjointSet.normalize_sets(
212  boost::make_counting_iterator(0),
213  boost::make_counting_iterator((n-1)*(m-1)));
214 
215 }
DisjointSet disjointSet
disjoint set of component IDs.
Definition: components.h:39
global definitions for all algorithms.
data::Interval B
Definition: freespace.h:31
a pair of horizonal / vertical intervals.
Definition: interval.h:456
boost::disjoint_sets_with_storage DisjointSet
union-find structure, or disjoint set
Definition: components.h:31
data::IntervalPair bounds
Definition: freespace.h:40
void clear()
assign false to all bits
Definition: bitset.cpp:67
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
data::Interval L
Definition: freespace.h:31
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
const int m
number of vertexes in Q
Definition: freespace.h:89
data::BitSet intervalSet
contains the valid representatives (a subset of all cells)
Definition: components.h:48
bool cellEmptyBounds(int i, int j) const
test if the bounding box of a cell is empty
Definition: freespace.cpp:174
size_t offset(int i, int j) const
compute linear offset
Definition: array2d.h:226
The FreeSpace class models the Free-Space Diagram calculated from two curves.
Definition: freespace.h:83
holds data for one cell of the free-space diagram
Definition: freespace.h:27
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
IntervalPair translated(double i, double j) const
translate both intervals
Definition: interval.h:530
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
const int n
number of vertexes in P
Definition: freespace.h:88
unsigned int component_id_t
used as identifier for free-space components
Definition: types.h:74
T & at(int i, int j)
array accessor
Definition: array2d.h:54
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
Cell & cell(int x, int y)
Definition: freespace.h:160
double max(double a, double b)
maximum function with checks for NAN
Definition: numeric.h:233