diff options
Diffstat (limited to 'src/2geom/quadtree.cpp')
| -rw-r--r-- | src/2geom/quadtree.cpp | 161 |
1 files changed, 153 insertions, 8 deletions
diff --git a/src/2geom/quadtree.cpp b/src/2geom/quadtree.cpp index e322a091b..211590bae 100644 --- a/src/2geom/quadtree.cpp +++ b/src/2geom/quadtree.cpp @@ -43,9 +43,94 @@ Quad* QuadTree::search(double x0, double y0, double x1, double y1) { } 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; @@ -55,14 +140,18 @@ void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) { 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)) { // too small initial size - double + (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; @@ -76,15 +165,22 @@ void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) { byy1 = 2*byy1 - byy0; } q = new Quad; - q->children[i] = root; - root = q; + //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; @@ -92,21 +188,41 @@ void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) { 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 + } 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 + } 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) { @@ -129,6 +245,35 @@ void QuadTree::erase(Quad *q, int shape) { 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; +} + }; /* |