1 #include <boost/iterator/counting_iterator.hpp> 21 return intervalArray.offset(i,j);
28 intervalArray(std::
max(n-1,0),std::
max(m-1,0)),
29 intervalSet(intervalArray.n * intervalArray.m)
37 if ((
n > 0) && (
m > 0)) {
61 for(i=0; i < (fs.
n-1); ++i)
62 for(j=0; j < (fs.
m-1); ++j)
117 bool connectLeft = (i > 0) && cl.
L;
118 bool connectBottom = (j > 0) && cl.
B;
121 if (!connectLeft && !connectBottom) {
138 if (connectLeft && connectBottom) {
140 if (leftRep!=bottomRep)
143 else if (connectLeft) {
147 Q_ASSERT(connectBottom);
153 Q_ASSERT((newRep==leftRep) || (newRep==bottomRep) || (newRep==thisRep));
155 if (newRep==leftRep) {
158 if (connectBottom && (bottomRep!=leftRep)) {
164 else if (newRep==bottomRep) {
167 if (connectLeft && (leftRep!=bottomRep)) {
174 Q_ASSERT(newRep==thisRep);
210 if ((
n > 0) && (
m > 0))
212 boost::make_counting_iterator(0),
213 boost::make_counting_iterator((
n-1)*(
m-1)));
DisjointSet disjointSet
disjoint set of component IDs.
global definitions for all algorithms.
a pair of horizonal / vertical intervals.
boost::disjoint_sets_with_storage DisjointSet
union-find structure, or disjoint set
data::IntervalPair bounds
void clear()
assign false to all bits
int m
number of vertexes in Q. Number of grid rows is m-1.
int n
number of vertexes in P. Number of grid columns is n-1.
component_id_t componentID(int i, int j)
get the component for a cell
Components(int n, int m)
default constrcutor
void calculateComponents(FreeSpace &fs)
calculate connected components
const int m
number of vertexes in Q
data::BitSet intervalSet
contains the valid representatives (a subset of all cells)
bool cellEmptyBounds(int i, int j) const
test if the bounding box of a cell is empty
size_t offset(int i, int j) const
compute linear offset
The FreeSpace class models the Free-Space Diagram calculated from two curves.
holds data for one cell of the free-space diagram
component_id_t representative(int i, int j)
find the component ID of a cell
void normalize()
normalize union-find structure. for each component, find the smallest representative.
IntervalPair translated(double i, double j) const
translate both intervals
component_id_t assignComponent(const FreeSpace &fs, int i, int j)
compute component ID for a cell
void clear()
clear the component set
const int n
number of vertexes in P
unsigned int component_id_t
used as identifier for free-space components
T & at(int i, int j)
array accessor
static const component_id_t NO_COMPONENT
empty cells have an invalid component ID
IntervalArray intervalArray
has an entry for every cell (nxm)
Cell & cell(int x, int y)
double max(double a, double b)
maximum function with checks for NAN