Quadtree: Quadtree/src/headers/SimpleQuadtree.h Source File

00001 #ifndef SIMPLE_QUADTREE_H
00002 #define SIMPLE_QUADTREE_H
00003 
00004 #include <math.h>
00005 #include "dmath.h"
00006 #include "debug.h"
00007 
00008 #include "Order2StatisticalConcept.h"
00009 #include "quadtree_common.h"
00010 
00011 namespace za_co_codespot
00012 {
00013         namespace datastructures
00014         {
00015                 using math::sqr;
00016 
00031 template <typename T>
00032 class SimpleQuadtree
00033 {
00034         //Make sure T is the correct type
00035         BOOST_CONCEPT_ASSERT((Order2StatisticalConcept<T>));
00036 
00037         //Make sure this implementation conforms to the compile time interface
00038         //This is for the developer 
00039 #ifdef CODE_SPOT_CO_ZA_DEBUG
00040         BOOST_CONCEPT_ASSERT((QuadtreeConcept<NaiveQuadtree<T>, T>));
00041 #endif
00042 public:
00043 
00044         SimpleQuadtree(const T ar[], unsigned int width, unsigned int height, const T & threshold);
00045         ~SimpleQuadtree();
00046 
00047         inline unsigned int getWidth() const;
00048         inline unsigned int getHeight() const;
00049 
00050         const T& operator()(unsigned int x, unsigned int y) const;
00051         unsigned int getLevel(unsigned int x, unsigned int y) const;
00052         unsigned int getNodeCount() const;
00053         
00054 private:
00055 
00056         enum NodeType
00057         {
00058                 LEAF, VERTICAL_BRANCH, HORISONTAL_BRANCH, RECTANGULAR_BRANCH
00059         };
00060 
00066         class Node
00067         {
00068         public:
00069                 Node(T value); //leaf!
00070 
00071                 Node(const T ar[], const T sum_table[], const T sqr_sum_table[],
00072                         unsigned int width, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, 
00073                         const T& threshold_sqr, NodeType nodeType); //branch
00074 
00075                 ~Node(); //need not be virtual, since there is no enheritance
00076                 
00077                 inline const T& getValue(unsigned int x, unsigned int y) const;
00078                 inline unsigned int getLevel(unsigned int x, unsigned int y) const;
00079                 unsigned int getNodeCount() const;
00080                 inline NodeType getNodeType() const;
00081 
00082         private:
00083                 Node();
00084 
00085                 T mValue;//We use this only if the node is in fact a leaf node
00086                 
00087                 unsigned int mMidX;
00088                 unsigned int mMidY;
00089                 
00090                 unsigned int mChildCount;
00091 
00092                 //We use this to know which data types to use.
00093                 NodeType mNodeType;
00094 
00095                 /*
00096                         We do not use this if this is a leaf node, and we do not use all 
00097                         of it if it is not a rectangular node. (See the documentation of 
00098                         the NaiveQuadtree for definitions oif these node types).
00099                 */
00100                 Node * mChildren[4];
00101         };
00102 
00103         static inline T getVariance(const T sqr_sum_table[], unsigned int width, T mean, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1);
00104         static inline T getMean(const T sum_table[], unsigned int width, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1);
00105         static inline Node * initializeChild(const T ar[], const T sum_table[], const T sqr_sum_table[], unsigned int width, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, const T & threshold_sqr);
00106 
00107         static inline const T& access(const T ar[], unsigned int x, unsigned int y, unsigned int width);
00108         static inline T& access(T ar[], unsigned int x, unsigned int y, unsigned int width);
00109 
00110         //make area sum tables in one go
00111         static void make_sum_tables(const T ar[], T sum_table[], T sqr_sum_table[], unsigned int width, unsigned int height);
00112 
00113         unsigned int mWidth;
00114         unsigned int mHeight;
00115         Node * mRoot;
00116 };
00117 
00118 //-------------------------------------------------------------------------------------
00119 // Implementation
00120 
00121 template<typename T>
00122 SimpleQuadtree<T>::Node::Node(T value):
00123         mValue(value),
00124         mNodeType(LEAF),
00125         mChildCount(0)
00126 {}
00127 
00128 template<typename T>
00129 SimpleQuadtree<T>::Node::~Node()
00130 {
00131         for (unsigned int k = 0; k < mChildCount; k++)
00132         {
00133                 delete mChildren[k];
00134         }       
00135 }
00136 
00137 template <typename T>
00138 unsigned int SimpleQuadtree<T>::Node::getNodeCount() const
00139 {
00140         unsigned int sum = 1; // 1 for this node
00141 
00142         for(unsigned int k = 0; k < mChildCount; k++)
00143         {
00144                 sum += mChildren[k]->getNodeCount();
00145         }
00146 
00147         return sum;
00148 }
00149 
00150 template <typename T>
00151 SimpleQuadtree<T>::Node::Node(
00152         const T ar[], const T sum_table[], const T sqr_sum_table[], 
00153         unsigned int width, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, 
00154         const T & threshold_sqr, NodeType nodeType):
00155         mMidX((x0 + x1) / 2),
00156         mMidY((y0 + y1) / 2),
00157         mValue(0),      
00158         mNodeType(nodeType)
00159 {
00160         assert(x0 != x1 + 1);
00161         assert(y0 != y1 + 1);
00162 
00163         switch(mNodeType)
00164         {
00165         case RECTANGULAR_BRANCH:
00166                 mChildCount = 4;
00167 
00168                 mChildren[0] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, x0, y0, mMidX, mMidY, threshold_sqr);
00169                 mChildren[1] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, mMidX, y0, x1, mMidY, threshold_sqr);
00170                 mChildren[2] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, x0, mMidY, mMidX, y1, threshold_sqr);
00171                 mChildren[3] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, mMidX, mMidY, x1, y1, threshold_sqr);
00172 
00173                 break;
00174 
00175         case HORISONTAL_BRANCH:
00176                 mChildCount = 2;
00177 
00178                 mChildren[0] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, x0, y0, mMidX, y1, threshold_sqr);
00179                 mChildren[1] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, mMidX, y0, x1, y1, threshold_sqr);
00180                 
00181                 break;
00182 
00183         case VERTICAL_BRANCH:
00184                 mChildCount = 2;
00185 
00186                 mChildren[0] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, x0, y0, x1, mMidY, threshold_sqr);
00187                 mChildren[1] = SimpleQuadtree<T>::initializeChild(ar, sum_table, sqr_sum_table, width, x0, mMidY, x1, y1, threshold_sqr);
00188                 
00189                 break;
00190 
00191         case LEAF:
00192                 mChildCount = 0;
00193 
00194                 assert(UNREACHABLE);//Leaf nodes are constructed with another constructor
00195                 break;
00196         default:
00197                 assert(UNREACHABLE);//No other types of nodes.
00198                 break;
00199         }
00200 }
00201 
00202 template <typename T>
00203 const T& SimpleQuadtree<T>::Node::getValue(unsigned int x, unsigned int y) const
00204 {
00205         switch(mNodeType)
00206         {
00207         case RECTANGULAR_BRANCH:
00208                 if (x < mMidX)
00209                 {
00210                         if (y < mMidY)
00211                         {
00212                                 return mChildren[0]->getValue(x,y);
00213                         }
00214                         else
00215                         {
00216                                 return mChildren[2]->getValue(x,y);
00217                         }
00218                 }
00219                 else
00220                 {
00221                         if (y < mMidY)
00222                         {
00223                                 return mChildren[1]->getValue(x,y);
00224                         }
00225                         else
00226                         {
00227                                 return mChildren[3]->getValue(x,y);
00228                         }
00229                 }
00230 
00231                 break;
00232         
00233         case LEAF:
00234                 return mValue;
00235 
00236                 break;
00237 
00238         case HORISONTAL_BRANCH:
00239                 if (x < mMidX)
00240                 {
00241                         return mChildren[0]->getValue(x,y);
00242                 }
00243                 else
00244                 {
00245                         return mChildren[1]->getValue(x,y);
00246                 }
00247 
00248                 break;
00249 
00250         case VERTICAL_BRANCH:
00251                 if (y < mMidY)
00252                 {
00253                         return mChildren[0]->getValue(x,y);
00254                 }
00255                 else
00256                 {
00257                         return mChildren[1]->getValue(x,y);
00258                 }
00259 
00260                 break;  
00261 
00262         default:
00263                 assert(UNREACHABLE);
00264                 return mValue;
00265                 break;
00266         }
00267         
00268 }
00269 
00270 template <typename T>
00271 unsigned int SimpleQuadtree<T>::Node::getLevel(unsigned int x, unsigned int y) const
00272 {
00273         switch(mNodeType)
00274         {
00275         case LEAF:
00276                 return 0;
00277                 
00278                 break;
00279 
00280         case HORISONTAL_BRANCH:
00281                 if (x < mMidX)
00282                 {
00283                         return mChildren[0]->getLevel(x,y) + 1;
00284                 }
00285                 else
00286                 {
00287                         return mChildren[1]->getLevel(x,y) + 1;
00288                 }
00289 
00290                 break;
00291 
00292         case VERTICAL_BRANCH:
00293                 if (y < mMidY)
00294                 {
00295                         return mChildren[0]->getLevel(x,y) + 1;
00296                 }
00297                 else
00298                 {
00299                         return mChildren[1]->getLevel(x,y) + 1;
00300                 }
00301 
00302                 break;
00303 
00304         case RECTANGULAR_BRANCH:
00305                 if (x < mMidX)
00306                 {
00307                         if (y < mMidY)
00308                         {
00309                                 return mChildren[0]->getLevel(x,y) + 1;
00310                         }
00311                         else
00312                         {
00313                                 return mChildren[2]->getLevel(x,y) + 1;
00314                         }
00315                 }
00316                 else
00317                 {
00318                         if (y < mMidY)
00319                         {
00320                                 return mChildren[1]->getLevel(x,y) + 1;
00321                         }
00322                         else
00323                         {
00324                                 return mChildren[3]->getLevel(x,y) + 1;
00325                         }
00326                 }
00327 
00328                 break;
00329 
00330         default:
00331                 assert(UNREACHABLE);
00332         }
00333 
00334         assert(UNREACHABLE);
00335 }
00336 
00337 template <typename T>
00338 SimpleQuadtree<T>::SimpleQuadtree(const T ar[], unsigned int width, unsigned int height, const T & threshold):
00339         mWidth(width),
00340         mHeight(height)
00341 {
00342         T * sum_table = new T[(width + 1) * (height + 1)];
00343         T * sqr_sum_table = new T[(width + 1) * (height + 1)];
00344         make_sum_tables(ar, sum_table, sqr_sum_table, width, height);
00345 
00346         mRoot = initializeChild(ar, sum_table, sqr_sum_table, width, 0, 0, width, height, sqr(threshold));
00347 
00348         delete[] sum_table;
00349         delete[] sqr_sum_table;
00350 }
00351 
00352 template <typename T>
00353 SimpleQuadtree<T>::~SimpleQuadtree()
00354 {
00355         delete mRoot;
00356         mRoot = 0;
00357 }
00358 
00359 template <typename T>
00360 unsigned int SimpleQuadtree<T>::getWidth() const
00361 {
00362         return mWidth;
00363 }
00364 
00365 template <typename T>
00366 unsigned int SimpleQuadtree<T>::getHeight() const
00367 {
00368         return mHeight;
00369 }
00370 
00371 #ifndef access
00372 template <typename T>
00373 const T& SimpleQuadtree<T>::access(const T ar[], unsigned int x, unsigned int y, unsigned int width)
00374 {
00375         return ar[y*width + x];
00376 }
00377 
00378 template <typename T>
00379 T& SimpleQuadtree<T>::access(T ar[], unsigned int x, unsigned int y, unsigned int width)
00380 {
00381         return ar[y*width + x];
00382 }
00383 #endif
00384 
00385 template <typename T>
00386 void SimpleQuadtree<T>::make_sum_tables(const T ar[], T sum_table[], T sqr_sum_table[], unsigned int width, unsigned int height)
00387 {
00388         unsigned int new_table_width = width + 1;
00389 
00390         for(unsigned int i = 0; i < width + 1; i++)
00391         {
00392                 access(sum_table, i, 0, new_table_width) = 0;
00393                 access(sqr_sum_table, i, 0, new_table_width) = 0;
00394         }
00395 
00396         for(unsigned int j = 1; j < height + 1; j++)
00397         {
00398                 access(sum_table, 0, j, new_table_width) = 0;
00399                 access(sqr_sum_table, 0, j, new_table_width) = 0;
00400         }
00401 
00402         for(unsigned int i = 1; i < width + 1; i++)
00403         {
00404                 for(unsigned int j = 1; j < height + 1; j++)
00405                 {
00406                         access(sum_table, i, j, new_table_width) = 
00407                                 access(sum_table, i, j - 1, new_table_width) 
00408                                 + access(sum_table, i - 1, j, new_table_width)
00409                                 - access(sum_table, i - 1, j - 1, new_table_width)
00410                                 + access(ar, i - 1, j - 1, width);
00411 
00412                         access(sqr_sum_table, i, j, new_table_width) = 
00413                                 access(sqr_sum_table, i, j - 1, new_table_width) 
00414                                 + access(sqr_sum_table, i - 1, j, new_table_width)
00415                                 - access(sqr_sum_table, i - 1, j - 1, new_table_width)
00416                                 + sqr(access(ar, i - 1, j - 1, width));
00417                 }
00418         }
00419 }
00420 
00421 template <typename T>
00422 T SimpleQuadtree<T>::getMean(const T sum_table[], unsigned int width, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1)
00423 {
00424         assert(x0 <= x1);
00425         assert(y0 <= y1);
00426 
00427         T sum;
00428         unsigned int new_table_width = width + 1;
00429 
00430         sum = access(sum_table, x1+1, y1+1, new_table_width) - access(sum_table, x1+1, y0, new_table_width)
00431                                 - access(sum_table, x0, y1+1, new_table_width) + access(sum_table, x0, y0, new_table_width);
00432 
00433         return sum / ((x1 - x0 + 1) * (y1 - y0 + 1));
00434 }
00435 
00436 template <typename T>
00437 T SimpleQuadtree<T>::getVariance(const T sqr_sum_table[], unsigned int width, T mean, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1)
00438 {
00439         assert(x0 <= x1);
00440         assert(y0 <= y1);
00441 
00442         T sum;
00443         unsigned int new_table_width = width + 1;
00444 
00445         sum = access(sqr_sum_table, x1+1, y1+1, new_table_width) - access(sqr_sum_table, x1+1, y0, new_table_width)
00446                                 - access(sqr_sum_table, x0, y1+1, new_table_width) + access(sqr_sum_table, x0, y0, new_table_width);
00447         
00448         return sum / ((x1 - x0 + 1) * (y1 - y0 + 1)) - sqr(mean);
00449 }
00450 
00451 template <typename T>
00452 const T& SimpleQuadtree<T>::operator()(unsigned int x, unsigned int y) const
00453 {
00454         return mRoot->getValue(x,y);
00455 }
00456 
00457 template <typename T>
00458 unsigned int SimpleQuadtree<T>::getLevel(unsigned int x, unsigned int y) const
00459 {
00460         return mRoot->getLevel(x, y);
00461 }
00462 
00463 template<typename T>
00464 typename SimpleQuadtree<T>::Node * SimpleQuadtree<T>::initializeChild(const T ar[], const T sum_table[], const T sqr_sum_table[], unsigned int width, unsigned int x0, unsigned int y0, unsigned int x1, unsigned int y1, const T & threshold_sqr)
00465 {
00466         if (x0 + 1 == x1)
00467         {
00468                 if (y0 + 1 == y1)
00469                 { 
00470                         return new Node(access(ar, x0, y0, width));
00471                 }
00472                 else
00473                 {//vert
00474                         return new Node(ar, sum_table, sqr_sum_table, width, x0, y0, x1, y1, threshold_sqr, VERTICAL_BRANCH);
00475                 }
00476         }
00477         else
00478         {
00479                 if (y0 + 1 == y1)
00480                 { //hor
00481                         return new Node(ar, sum_table, sqr_sum_table, width, x0, y0, x1, y1, threshold_sqr, HORISONTAL_BRANCH);
00482                 }
00483         }
00484 
00485         T mean(getMean(sum_table, width, x0, y0, x1 - 1, y1 - 1));
00486         T variance(getVariance(sqr_sum_table, width, mean, x0, y0, x1 - 1, y1 - 1));
00487 
00488         if(variance <= threshold_sqr)
00489         {
00490                 return new Node(mean);
00491         }
00492         else
00493         {
00494                 return new Node(ar, sum_table, sqr_sum_table, width, x0, y0, x1, y1, threshold_sqr, RECTANGULAR_BRANCH);
00495         }
00496 
00497         assert(0);
00498 }
00499 
00500 template<typename T>
00501 unsigned int SimpleQuadtree<T>::getNodeCount() const
00502 {
00503         return mRoot->getNodeCount();
00504 }
00505 
00506 } //end namespace datastructures
00507 } //end namespace za_co_codespot
00508 
00509 #endif //SIMPLE_QUADTREE_H