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 :