logo

Inkscape

  • Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

quadtree.cpp

Go to the documentation of this file.
00001 #include <2geom/quadtree.h>
00002 
00003 namespace Geom{
00004 Quad* QuadTree::search(Rect const &r) {
00005     return search(r[0].min(), r[1].min(),
00006                   r[0].max(), r[1].max());
00007 }
00008 
00009 void QuadTree::insert(Rect const &r, int shape) {
00010     insert(r[0].min(), r[1].min(),
00011            r[0].max(), r[1].max(), shape);
00012 }
00013 
00014 
00015 Quad* QuadTree::search(double x0, double y0, double x1, double y1) {
00016     Quad *q = root;
00017         
00018     double bxx0 = bx1, bxx1 = bx1;
00019     double byy0 = by1, byy1 = by1;
00020     while(q) {
00021         double cx = (bxx0 + bxx1)/2;
00022         double cy = (byy0 + byy1)/2;
00023         unsigned i = 0;
00024         if(x0 >= cx) {
00025             i += 1;
00026             bxx0 = cx; // zoom in a quad
00027         } else if(x1 <= cx) {
00028             bxx1 = cx;
00029         } else
00030             break;
00031         if(y0 >= cy) {
00032             i += 2;
00033             byy0 = cy;
00034         } else if(y1 <= cy) {
00035             byy1 = cy;
00036         } else
00037             break;
00038         
00039         assert(i < 4);
00040         Quad *qq = q->children[i];
00041         if(qq == 0) break; // last non-null
00042         q = qq;
00043     }
00044     return q;
00045 }
00046 
00047 
00048 /*
00049 Comments by Vangelis (use with caution :P )
00050 
00051 Insert Rect (x0, y0), (x1, y1) in the QuadTree Q.
00052 
00053 ===================================================================================
00054 * QuadTree Q has: Quadtree's Quad root R, QuadTree's bounding box B. 
00055 
00056 * Each Quad has a Quad::data where we store the id of the Rect that belong to 
00057 this Quad. (In reality we'll store a pointer to the shape).
00058 
00059 * Each Quad has 4 Quad children: 0, 1, 2, 3. Each child Quad represents one of the following quarters
00060 of the bounding box B:
00061 
00062 +---------------------+
00063 |          |          |
00064 |  NW=0    |  NE=1    |
00065 |          |          |
00066 |          |          |
00067 +---------------------+
00068 |          |          |
00069 |  SW=2    |  SE=3    |
00070 |          |          |
00071 |          |          |
00072 +---------------------+ 
00073 
00074 Each Quad can further be divided in 4 Quads as above and so on. Below there is an example 
00075  
00076        Root
00077       / || \
00078     /  /  \  \
00079    0  1   2   3
00080      /\
00081   / | | \
00082   0 1 2 3
00083 
00084 +---------------------+
00085 |          | 1-0 | 1-1|
00086 |    0     |     |    |
00087 |          |-----|----|
00088 |          | 1-2 | 1-3|
00089 |          |     |    |
00090 +---------------------+
00091 |          |          |
00092 |          |          |
00093 |     2    |     3    |
00094 |          |          |
00095 +---------------------+ 
00096 
00097 
00098 
00099 ===================================================================================
00100 Insert Rect (x0, y0), (x1, y1) in the QuadTree Q. Algorithm:
00101 1) check if Rect is bigger than QuadTree's bounding box
00102 2) find in which Quad we should add the Rect:
00103 
00104 
00105 
00106 -----------------------------------------------------------------------------------
00107 How we find in which Quad we should add the Rect R:
00108 
00109 Q = Quadtree's Quad root
00110 B = QuadTree's bounding box B
00111 WHILE (Q) {
00112     IF ( Rect cannot fit in one unique quarter of B ){
00113         Q = current Quad ;
00114         BREAK;
00115     }
00116     IF ( Rect can fit in the quarter I ) {
00117         IF (Q.children[I] doesn't exist) {
00118             create the Quad Q.children[I];
00119         }
00120         B = bounding box of the Quad Q.children[I] ;
00121         Q = Q.children[I] ;
00122         CHECK(R, B) ;
00123     }
00124 }
00125 add Rect R to Q ;
00126 
00127 
00128 */
00129     
00130 void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) {
00131     // loop until a quad would break the box.
00132 
00133     // empty root => empty QuadTree. Create initial bounding box (0,0), (1,1)
00134     if(root == 0) {
00135         root = new Quad;
00136             
00137         bx0 = 0;
00138         bx1 = 1;
00139         by0 = 0;
00140         by1 = 1;
00141     }
00142     Quad *q = root;
00143 
00144     //A temp bounding box. Same as root's bounting box (ie of the whole QuadTree)
00145     double bxx0 = bx0, bxx1 = bx1;
00146     double byy0 = by0, byy1 = by1;
00147 
00148     while((bxx0 > x0) ||
00149           (bxx1 < x1) ||
00150           (byy0 > y0) ||
00151           (byy1 < y1)) { 
00152         // QuadTree has small size, can't accomodate new rect. Double the size:
00153         unsigned i = 0;
00154 
00155         if(bxx0 > x0) {
00156             bxx0 = 2*bxx0 - bxx1;
00157             i += 1;
00158         } else {
00159             bxx1 = 2*bxx1 - bxx0;
00160         }
00161         if(byy0 > y0) {
00162             byy0 = 2*byy0 - byy1;
00163             i += 2;
00164         } else {
00165             byy1 = 2*byy1 - byy0;
00166         }
00167         q = new Quad;
00168         //check if root is empty (no rects, no quad children)
00169         if( clean_root() ){
00170             root = q;
00171         }
00172         else{
00173             q->children[i] = root;
00174             root = q;
00175         }
00176         bx0 = bxx0;
00177         bx1 = bxx1;
00178         by0 = byy0;
00179         by1 = byy1;
00180     }
00181 
00182     while(q) {
00183         // Find the center of the temp bounding box
00184         double cx = (bxx0 + bxx1)/2;
00185         double cy = (byy0 + byy1)/2;
00186         unsigned i = 0;
00187         assert(x0 >= bxx0);
00188         assert(x1 <= bxx1);
00189         assert(y0 >= byy0);
00190         assert(y1 <= byy1);
00191 
00192         if(x0 >= cx) {
00193             i += 1;
00194             bxx0 = cx; // zoom in a quad
00195         } else if(x1 <= cx) {
00196             bxx1 = cx;
00197         } else{
00198             // rect does not fit in one unique quarter (in X axis) of the temp bounding box
00199             break;
00200         }
00201         if(y0 >= cy) {
00202             i += 2;
00203             byy0 = cy;
00204         } else if(y1 <= cy) {
00205             byy1 = cy;
00206         } else{
00207             // rect does not fit in one unique quarter (in Y axis) of the temp bounding box
00208             break;
00209         }
00210 
00211         // check if rect's bounding box has size 1x1. This means that rect is defined by 2 points
00212         // that are in the same place.
00213         if( ( fabs(bxx0 - bxx1) < 1.0 ) && ( fabs(byy0 - byy1) < 1.0 )){
00214             bxx0 = floor(bxx0);
00215             bxx1 = floor(bxx1);
00216             byy0 = floor(byy0);
00217             byy1 = floor(byy1);
00218             break;
00219         }
00220 
00221         /*
00222         1 rect does fit in one unique quarter of the temp bounding box. And we have found which.
00223         2 temp bounding box = bounding box of this quarter. 
00224         3 "Go in" this quarter (create if doesn't exist)
00225         */
00226         assert(i < 4);
00227         Quad *qq = q->children[i];
00228         if(qq == 0) {
00229             qq = new Quad;
00230             q->children[i] = qq;
00231         }
00232         q = qq;
00233     }
00234     q->data.push_back(shape);
00235 }
00236 void QuadTree::erase(Quad *q, int shape) {
00237     for(Quad::iterator i = q->data.begin();  i != q->data.end(); i++) {
00238         if(*i == shape) {
00239             q->data.erase(i);
00240             if(q->data.empty()) {
00241 
00242             }
00243         }
00244     }
00245     return;
00246 }
00247 
00248 /*
00249 Returns:
00250 false:  if root isn't empty
00251 true:   if root is empty it cleans root
00252 */
00253 bool QuadTree::clean_root() { 
00254     assert(root);
00255 
00256     // false if root *has* rects assigned to it.
00257     bool all_clean = root->data.empty(); 
00258 
00259     // if root has children we get false
00260     for(unsigned i = 0; i < 4; i++)
00261     {
00262         if(root->children[i])
00263         {
00264             all_clean = false;
00265         }
00266     }
00267 
00268     if(all_clean)
00269     {
00270         delete root;
00271         root=0;
00272         return true;
00273     }
00274     return false;
00275 }
00276 
00277 };
00278 
00279 /*
00280   Local Variables:
00281   mode:c++
00282   c-file-style:"stroustrup"
00283   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
00284   indent-tabs-mode:nil
00285   fill-column:99
00286   End:
00287 */
00288 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :