src/2geom/quadtree.cpp

   1 #include <2geom/quadtree.h>
   2
   3 namespace Geom{
   4 Quad* QuadTree::search(Rect const &r) {
   5     return search(r[0].min(), r[1].min(),
   6                   r[0].max(), r[1].max());
   7 }
   8
   9 void QuadTree::insert(Rect const &r, int shape) {
  10     insert(r[0].min(), r[1].min(),
  11            r[0].max(), r[1].max(), shape);
  12 }
  13
  14
  15 Quad* QuadTree::search(double x0, double y0, double x1, double y1) {
  16     Quad *q = root;
  17
  18     double bxx0 = bx1, bxx1 = bx1;
  19     double byy0 = by1, byy1 = by1;
  20     while(q) {
  21         double cx = (bxx0 + bxx1)/2;
  22         double cy = (byy0 + byy1)/2;
  23         unsigned i = 0;
  24         if(x0 >= cx) {
  25             i += 1;
  26             bxx0 = cx; // zoom in a quad
  27         } else if(x1 <= cx) {
  28             bxx1 = cx;
  29         } else
  30             break;
  31         if(y0 >= cy) {
  32             i += 2;
  33             byy0 = cy;
  34         } else if(y1 <= cy) {
  35             byy1 = cy;
  36         } else
  37             break;
  38
  39         assert(i < 4);
  40         Quad *qq = q->children[i];
  41         if(qq == 0) break; // last non-null
  42         q = qq;
  43     }
  44     return q;
  45 }
  46
  47
  48 /*
  49 Comments by Vangelis (use with caution :P )
  50
  51 Insert Rect (x0, y0), (x1, y1) in the QuadTree Q.
  52
  53 ===================================================================================
  54 * QuadTree Q has: Quadtree's Quad root R, QuadTree's bounding box B.
  55
  56 * Each Quad has a Quad::data where we store the id of the Rect that belong to
  57 this Quad. (In reality we'll store a pointer to the shape).
  58
  59 * Each Quad has 4 Quad children: 0, 1, 2, 3. Each child Quad represents one of the following quarters
  60 of the bounding box B:
  61
  62 +---------------------+
  63 |          |          |
  64 |  NW=0    |  NE=1    |
  65 |          |          |
  66 |          |          |
  67 +---------------------+
  68 |          |          |
  69 |  SW=2    |  SE=3    |
  70 |          |          |
  71 |          |          |
  72 +---------------------+
  73
  74 Each Quad can further be divided in 4 Quads as above and so on. Below there is an example
  75
  76        Root
  77       / || \
  78     /  /  \  \
  79    0  1   2   3
  80      /\
  81   / | | \
  82   0 1 2 3
  83
  84 +---------------------+
  85 |          | 1-0 | 1-1|
  86 |    0     |     |    |
  87 |          |-----|----|
  88 |          | 1-2 | 1-3|
  89 |          |     |    |
  90 +---------------------+
  91 |          |          |
  92 |          |          |
  93 |     2    |     3    |
  94 |          |          |
  95 +---------------------+
  96
  97
  98
  99 ===================================================================================
 100 Insert Rect (x0, y0), (x1, y1) in the QuadTree Q. Algorithm:
 101 1) check if Rect is bigger than QuadTree's bounding box
 102 2) find in which Quad we should add the Rect:
 103
 104
 105
 106 -----------------------------------------------------------------------------------
 107 How we find in which Quad we should add the Rect R:
 108
 109 Q = Quadtree's Quad root
 110 B = QuadTree's bounding box B
 111 WHILE (Q) {
 112     IF ( Rect cannot fit in one unique quarter of B ){
 113         Q = current Quad ;
 114         BREAK;
 115     }
 116     IF ( Rect can fit in the quarter I ) {
 117         IF (Q.children[I] doesn't exist) {
 118             create the Quad Q.children[I];
 119         }
 120         B = bounding box of the Quad Q.children[I] ;
 121         Q = Q.children[I] ;
 122         CHECK(R, B) ;
 123     }
 124 }
 125 add Rect R to Q ;
 126
 127
 128 */
 129
 130 void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) {
 131     // loop until a quad would break the box.
 132
 133     // empty root => empty QuadTree. Create initial bounding box (0,0), (1,1)
 134     if(root == 0) {
 135         root = new Quad;
 136
 137         bx0 = 0;
 138         bx1 = 1;
 139         by0 = 0;
 140         by1 = 1;
 141     }
 142     Quad *q = root;
 143
 144     //A temp bounding box. Same as root's bounting box (ie of the whole QuadTree)
 145     double bxx0 = bx0, bxx1 = bx1;
 146     double byy0 = by0, byy1 = by1;
 147
 148     while((bxx0 > x0) ||
 149           (bxx1 < x1) ||
 150           (byy0 > y0) ||
 151           (byy1 < y1)) {
 152         // QuadTree has small size, can't accomodate new rect. Double the size:
 153         unsigned i = 0;
 154
 155         if(bxx0 > x0) {
 156             bxx0 = 2*bxx0 - bxx1;
 157             i += 1;
 158         } else {
 159             bxx1 = 2*bxx1 - bxx0;
 160         }
 161         if(byy0 > y0) {
 162             byy0 = 2*byy0 - byy1;
 163             i += 2;
 164         } else {
 165             byy1 = 2*byy1 - byy0;
 166         }
 167         q = new Quad;
 168         //check if root is empty (no rects, no quad children)
 169         if( clean_root() ){
 170             root = q;
 171         }
 172         else{
 173             q->children[i] = root;
 174             root = q;
 175         }
 176         bx0 = bxx0;
 177         bx1 = bxx1;
 178         by0 = byy0;
 179         by1 = byy1;
 180     }
 181
 182     while(q) {
 183         // Find the center of the temp bounding box
 184         double cx = (bxx0 + bxx1)/2;
 185         double cy = (byy0 + byy1)/2;
 186         unsigned i = 0;
 187         assert(x0 >= bxx0);
 188         assert(x1 <= bxx1);
 189         assert(y0 >= byy0);
 190         assert(y1 <= byy1);
 191
 192         if(x0 >= cx) {
 193             i += 1;
 194             bxx0 = cx; // zoom in a quad
 195         } else if(x1 <= cx) {
 196             bxx1 = cx;
 197         } else{
 198             // rect does not fit in one unique quarter (in X axis) of the temp bounding box
 199             break;
 200         }
 201         if(y0 >= cy) {
 202             i += 2;
 203             byy0 = cy;
 204         } else if(y1 <= cy) {
 205             byy1 = cy;
 206         } else{
 207             // rect does not fit in one unique quarter (in Y axis) of the temp bounding box
 208             break;
 209         }
 210
 211         // check if rect's bounding box has size 1x1. This means that rect is defined by 2 points
 212         // that are in the same place.
 213         if( ( fabs(bxx0 - bxx1) < 1.0 ) && ( fabs(byy0 - byy1) < 1.0 )){
 214             bxx0 = floor(bxx0);
 215             bxx1 = floor(bxx1);
 216             byy0 = floor(byy0);
 217             byy1 = floor(byy1);
 218             break;
 219         }
 220
 221         /*
 222         1 rect does fit in one unique quarter of the temp bounding box. And we have found which.
 223         2 temp bounding box = bounding box of this quarter.
 224         3 "Go in" this quarter (create if doesn't exist)
 225         */
 226         assert(i < 4);
 227         Quad *qq = q->children[i];
 228         if(qq == 0) {
 229             qq = new Quad;
 230             q->children[i] = qq;
 231         }
 232         q = qq;
 233     }
 234     q->data.push_back(shape);
 235 }
 236 void QuadTree::erase(Quad *q, int shape) {
 237     for(Quad::iterator i = q->data.begin();  i != q->data.end(); i++) {
 238         if(*i == shape) {
 239             q->data.erase(i);
 240             if(q->data.empty()) {
 241
 242             }
 243         }
 244     }
 245     return;
 246 }
 247
 248 /*
 249 Returns:
 250 false:  if root isn't empty
 251 true:   if root is empty it cleans root
 252 */
 253 bool QuadTree::clean_root() {
 254     assert(root);
 255
 256     // false if root *has* rects assigned to it.
 257     bool all_clean = root->data.empty();
 258
 259     // if root has children we get false
 260     for(unsigned i = 0; i < 4; i++)
 261     {
 262         if(root->children[i])
 263         {
 264             all_clean = false;
 265         }
 266     }
 267
 268     if(all_clean)
 269     {
 270         delete root;
 271         root=0;
 272         return true;
 273     }
 274     return false;
 275 }
 276
 277 };
 278
 279 /*
 280   Local Variables:
 281   mode:c++
 282   c-file-style:"stroustrup"
 283   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 284   indent-tabs-mode:nil
 285   fill-column:99
 286   End:
 287 */
 288 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :