Inkscape

quadtree.cpp

Go to the documentation of this file.

#include <2geom/quadtree.h>

namespace Geom{
Quad* QuadTree::search(Rect const &r) {
    return search(r[0].min(), r[1].min(),
                  r[0].max(), r[1].max());
}

void QuadTree::insert(Rect const &r, int shape) {
    insert(r[0].min(), r[1].min(),
           r[0].max(), r[1].max(), shape);
}


Quad* QuadTree::search(double x0, double y0, double x1, double y1) {
    Quad *q = root;
        
    double bxx0 = bx1, bxx1 = bx1;
    double byy0 = by1, byy1 = by1;
    while(q) {
        double cx = (bxx0 + bxx1)/2;
        double cy = (byy0 + byy1)/2;
        unsigned i = 0;
        if(x0 >= cx) {
            i += 1;
            bxx0 = cx; // zoom in a quad
        } else if(x1 <= cx) {
            bxx1 = cx;
        } else
            break;
        if(y0 >= cy) {
            i += 2;
            byy0 = cy;
        } else if(y1 <= cy) {
            byy1 = cy;
        } else
            break;
        
        assert(i < 4);
        Quad *qq = q->children[i];
        if(qq == 0) break; // last non-null
        q = qq;
    }
    return q;
}


/*
Comments by Vangelis (use with caution :P )

Insert Rect (x0, y0), (x1, y1) in the QuadTree Q.

===================================================================================
* QuadTree Q has: Quadtree's Quad root R, QuadTree's bounding box B. 

* Each Quad has a Quad::data where we store the id of the Rect that belong to 
this Quad. (In reality we'll store a pointer to the shape).

* Each Quad has 4 Quad children: 0, 1, 2, 3. Each child Quad represents one of the following quarters
of the bounding box B:

+---------------------+
|          |          |
|  NW=0    |  NE=1    |
|          |          |
|          |          |
+---------------------+
|          |          |
|  SW=2    |  SE=3    |
|          |          |
|          |          |
+---------------------+ 

Each Quad can further be divided in 4 Quads as above and so on. Below there is an example 
 
       Root
      / || \
    /  /  \  \
   0  1   2   3
     /\
  / | | \
  0 1 2 3

+---------------------+
|          | 1-0 | 1-1|
|    0     |     |    |
|          |-----|----|
|          | 1-2 | 1-3|
|          |     |    |
+---------------------+
|          |          |
|          |          |
|     2    |     3    |
|          |          |
+---------------------+ 



===================================================================================
Insert Rect (x0, y0), (x1, y1) in the QuadTree Q. Algorithm:
1) check if Rect is bigger than QuadTree's bounding box
2) find in which Quad we should add the Rect:



-----------------------------------------------------------------------------------
How we find in which Quad we should add the Rect R:

Q = Quadtree's Quad root
B = QuadTree's bounding box B
WHILE (Q) {
    IF ( Rect cannot fit in one unique quarter of B ){
        Q = current Quad ;
        BREAK;
    }
    IF ( Rect can fit in the quarter I ) {
        IF (Q.children[I] doesn't exist) {
            create the Quad Q.children[I];
        }
        B = bounding box of the Quad Q.children[I] ;
        Q = Q.children[I] ;
        CHECK(R, B) ;
    }
}
add Rect R to Q ;


*/
    
void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) {
    // loop until a quad would break the box.

    // empty root => empty QuadTree. Create initial bounding box (0,0), (1,1)
    if(root == 0) {
        root = new Quad;
            
        bx0 = 0;
        bx1 = 1;
        by0 = 0;
        by1 = 1;
    }
    Quad *q = root;

    //A temp bounding box. Same as root's bounting box (ie of the whole QuadTree)
    double bxx0 = bx0, bxx1 = bx1;
    double byy0 = by0, byy1 = by1;

    while((bxx0 > x0) ||
          (bxx1 < x1) ||
          (byy0 > y0) ||
          (byy1 < y1)) { 
        // QuadTree has small size, can't accomodate new rect. Double the size:
        unsigned i = 0;

        if(bxx0 > x0) {
            bxx0 = 2*bxx0 - bxx1;
            i += 1;
        } else {
            bxx1 = 2*bxx1 - bxx0;
        }
        if(byy0 > y0) {
            byy0 = 2*byy0 - byy1;
            i += 2;
        } else {
            byy1 = 2*byy1 - byy0;
        }
        q = new Quad;
        //check if root is empty (no rects, no quad children)
        if( clean_root() ){
            root = q;
        }
        else{
            q->children[i] = root;
            root = q;
        }
        bx0 = bxx0;
        bx1 = bxx1;
        by0 = byy0;
        by1 = byy1;
    }

    while(q) {
        // Find the center of the temp bounding box
        double cx = (bxx0 + bxx1)/2;
        double cy = (byy0 + byy1)/2;
        unsigned i = 0;
        assert(x0 >= bxx0);
        assert(x1 <= bxx1);
        assert(y0 >= byy0);
        assert(y1 <= byy1);

        if(x0 >= cx) {
            i += 1;
            bxx0 = cx; // zoom in a quad
        } else if(x1 <= cx) {
            bxx1 = cx;
        } else{
            // rect does not fit in one unique quarter (in X axis) of the temp bounding box
            break;
        }
        if(y0 >= cy) {
            i += 2;
            byy0 = cy;
        } else if(y1 <= cy) {
            byy1 = cy;
        } else{
            // rect does not fit in one unique quarter (in Y axis) of the temp bounding box
            break;
        }

        // check if rect's bounding box has size 1x1. This means that rect is defined by 2 points
        // that are in the same place.
        if( ( fabs(bxx0 - bxx1) < 1.0 ) && ( fabs(byy0 - byy1) < 1.0 )){
            bxx0 = floor(bxx0);
            bxx1 = floor(bxx1);
            byy0 = floor(byy0);
            byy1 = floor(byy1);
            break;
        }

        /*
        1 rect does fit in one unique quarter of the temp bounding box. And we have found which.
        2 temp bounding box = bounding box of this quarter. 
        3 "Go in" this quarter (create if doesn't exist)
        */
        assert(i < 4);
        Quad *qq = q->children[i];
        if(qq == 0) {
            qq = new Quad;
            q->children[i] = qq;
        }
        q = qq;
    }
    q->data.push_back(shape);
}
void QuadTree::erase(Quad *q, int shape) {
    for(Quad::iterator i = q->data.begin();  i != q->data.end(); i++) {
        if(*i == shape) {
            q->data.erase(i);
            if(q->data.empty()) {

            }
        }
    }
    return;
}

/*
Returns:
false:  if root isn't empty
true:   if root is empty it cleans root
*/
bool QuadTree::clean_root() { 
    assert(root);

    // false if root *has* rects assigned to it.
    bool all_clean = root->data.empty(); 

    // if root has children we get false
    for(unsigned i = 0; i < 4; i++)
    {
        if(root->children[i])
        {
            all_clean = false;
        }
    }

    if(all_clean)
    {
        delete root;
        root=0;
        return true;
    }
    return false;
}

};

/*
  Local Variables:
  mode:c++
  c-file-style:"stroustrup"
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  indent-tabs-mode:nil
  fill-column:99
  End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :