quadtree.h

Go to the documentation of this file.
00001 
00035 #include <vector>
00036 #include <cassert>
00037 
00038 #include <2geom/d2.h>
00039 
00040 namespace Geom{
00041 
00042 class Quad{
00043 public:
00044     Quad* children[4];
00045     std::vector<int> data;
00046     Quad() {
00047         for(int i = 0; i < 4; i++)
00048             children[i] = 0;
00049     }
00050     typedef std::vector<int>::iterator iterator;
00051     Rect bounds(unsigned i, double x, double y, double d) {
00052         double dd = d/2;
00053         switch(i % 4) {
00054             case 0:
00055                 return Rect(Interval(x, x+dd), Interval(y, y+dd));
00056             case 1:
00057                 return Rect(Interval(x+dd, x+d), Interval(y, y+dd));
00058             case 2:
00059                 return Rect(Interval(x, x+dd), Interval(y+dd, y+d));
00060             case 3:
00061                 return Rect(Interval(x+dd, x+d), Interval(y+dd, y+d));
00062             default: 
00063                 /* just to suppress warning message
00064                  * this case should be never reached */
00065                 assert(false);
00066         }        
00067     }
00068 };
00069 
00070 class QuadTree{
00071 public:
00072     Quad* root;
00073     double scale;
00074     double bx0, bx1;
00075     double by0, by1;
00076 
00077     QuadTree() : root(0), scale(1) {}
00078 
00079     Quad* search(double x0, double y0, double x1, double y1);
00080     void insert(double x0, double y0, double x1, double y1, int shape);
00081     Quad* search(Geom::Rect const &r);
00082     void insert(Geom::Rect const &r, int shape);
00083     void erase(Quad *q, int shape);
00084 private:
00085     bool clean_root();
00086 };
00087 
00088 };
00089 
00090 /*
00091   Local Variables:
00092   mode:c++
00093   c-file-style:"stroustrup"
00094   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
00095   indent-tabs-mode:nil
00096   fill-column:99
00097   End:
00098 */
00099 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
Inkscape

quadtree.h
