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 void QuadTree::insert(double x0, double y0, double x1, double y1, int shape) {
  48     // loop until a quad would break the box.
  49     if(root == 0) {
  50         root = new Quad;
  51
  52         bx0 = 0;
  53         bx1 = 1;
  54         by0 = 0;
  55         by1 = 1;
  56     }
  57     Quad *q = root;
  58
  59     double bxx0 = bx0, bxx1 = bx1;
  60     double byy0 = by0, byy1 = by1;
  61     while((bxx0 > x0) ||
  62           (bxx1 < x1) ||
  63           (byy0 > y0) ||
  64           (byy1 < y1)) { // too small initial size - double
  65         unsigned i = 0;
  66         if(bxx0 > x0) {
  67             bxx0 = 2*bxx0 - bxx1;
  68             i += 1;
  69         } else {
  70             bxx1 = 2*bxx1 - bxx0;
  71         }
  72         if(byy0 > y0) {
  73             byy0 = 2*byy0 - byy1;
  74             i += 2;
  75         } else {
  76             byy1 = 2*byy1 - byy0;
  77         }
  78         q = new Quad;
  79         q->children[i] = root;
  80         root = q;
  81         bx0 = bxx0;
  82         bx1 = bxx1;
  83         by0 = byy0;
  84         by1 = byy1;
  85     }
  86
  87     while(q) {
  88         double cx = (bxx0 + bxx1)/2;
  89         double cy = (byy0 + byy1)/2;
  90         unsigned i = 0;
  91         assert(x0 >= bxx0);
  92         assert(x1 <= bxx1);
  93         assert(y0 >= byy0);
  94         assert(y1 <= byy1);
  95         if(x0 >= cx) {
  96             i += 1;
  97             bxx0 = cx; // zoom in a quad
  98         } else if(x1 <= cx) {
  99             bxx1 = cx;
 100         } else
 101             break;
 102         if(y0 >= cy) {
 103             i += 2;
 104             byy0 = cy;
 105         } else if(y1 <= cy) {
 106             byy1 = cy;
 107         } else
 108             break;
 109
 110         assert(i < 4);
 111         Quad *qq = q->children[i];
 112         if(qq == 0) {
 113             qq = new Quad;
 114             q->children[i] = qq;
 115         }
 116         q = qq;
 117     }
 118     q->data.push_back(shape);
 119 }
 120 void QuadTree::erase(Quad *q, int shape) {
 121     for(Quad::iterator i = q->data.begin();  i != q->data.end(); i++) {
 122         if(*i == shape) {
 123             q->data.erase(i);
 124             if(q->data.empty()) {
 125
 126             }
 127         }
 128     }
 129     return;
 130 }
 131
 132 };
 133
 134 /*
 135   Local Variables:
 136   mode:c++
 137   c-file-style:"stroustrup"
 138   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 139   indent-tabs-mode:nil
 140   fill-column:99
 141   End:
 142 */
 143 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :