Geom::QuadTree Class Reference
#include <quadtree.h>

Public Member Functions | |
| QuadTree () | |
| Quad * | search (double x0, double y0, double x1, double y1) |
| void | insert (double x0, double y0, double x1, double y1, int shape) |
| Quad * | search (Geom::Rect const &r) |
| void | insert (Geom::Rect const &r, int shape) |
| void | erase (Quad *q, int shape) |
Public Attributes | |
| Quad * | root |
| double | scale |
| double | bx0 |
| double | bx1 |
| double | by0 |
| double | by1 |
Private Member Functions | |
| bool | clean_root () |
Detailed Description
Definition at line 70 of file quadtree.h.
Constructor & Destructor Documentation
| Geom::QuadTree::QuadTree | ( | ) | [inline] |
Definition at line 77 of file quadtree.h.
Member Function Documentation
| bool Geom::QuadTree::clean_root | ( | ) | [private] |
Definition at line 253 of file quadtree.cpp.
References Geom::Quad::children, Geom::Quad::data, Barcode::Code39Ext::i, and root.
Referenced by insert().
00253 { 00254 assert(root); 00255 00256 // false if root *has* rects assigned to it. 00257 bool all_clean = root->data.empty(); 00258 00259 // if root has children we get false 00260 for(unsigned i = 0; i < 4; i++) 00261 { 00262 if(root->children[i]) 00263 { 00264 all_clean = false; 00265 } 00266 } 00267 00268 if(all_clean) 00269 { 00270 delete root; 00271 root=0; 00272 return true; 00273 } 00274 return false; 00275 }
| void Geom::QuadTree::erase | ( | Quad * | q, | |
| int | shape | |||
| ) |
Definition at line 236 of file quadtree.cpp.
References Geom::Quad::data, and Barcode::Code39Ext::i.
| void Geom::QuadTree::insert | ( | Geom::Rect const & | r, | |
| int | shape | |||
| ) |
Definition at line 9 of file quadtree.cpp.
References insert(), Geom::max(), and Geom::min().
Definition at line 130 of file quadtree.cpp.
References bx0, bx1, by0, by1, Geom::Quad::children, clean_root(), Geom::Quad::data, Barcode::Code39Ext::i, samplify::q, and root.
Referenced by insert().
00130 { 00131 // loop until a quad would break the box. 00132 00133 // empty root => empty QuadTree. Create initial bounding box (0,0), (1,1) 00134 if(root == 0) { 00135 root = new Quad; 00136 00137 bx0 = 0; 00138 bx1 = 1; 00139 by0 = 0; 00140 by1 = 1; 00141 } 00142 Quad *q = root; 00143 00144 //A temp bounding box. Same as root's bounting box (ie of the whole QuadTree) 00145 double bxx0 = bx0, bxx1 = bx1; 00146 double byy0 = by0, byy1 = by1; 00147 00148 while((bxx0 > x0) || 00149 (bxx1 < x1) || 00150 (byy0 > y0) || 00151 (byy1 < y1)) { 00152 // QuadTree has small size, can't accomodate new rect. Double the size: 00153 unsigned i = 0; 00154 00155 if(bxx0 > x0) { 00156 bxx0 = 2*bxx0 - bxx1; 00157 i += 1; 00158 } else { 00159 bxx1 = 2*bxx1 - bxx0; 00160 } 00161 if(byy0 > y0) { 00162 byy0 = 2*byy0 - byy1; 00163 i += 2; 00164 } else { 00165 byy1 = 2*byy1 - byy0; 00166 } 00167 q = new Quad; 00168 //check if root is empty (no rects, no quad children) 00169 if( clean_root() ){ 00170 root = q; 00171 } 00172 else{ 00173 q->children[i] = root; 00174 root = q; 00175 } 00176 bx0 = bxx0; 00177 bx1 = bxx1; 00178 by0 = byy0; 00179 by1 = byy1; 00180 } 00181 00182 while(q) { 00183 // Find the center of the temp bounding box 00184 double cx = (bxx0 + bxx1)/2; 00185 double cy = (byy0 + byy1)/2; 00186 unsigned i = 0; 00187 assert(x0 >= bxx0); 00188 assert(x1 <= bxx1); 00189 assert(y0 >= byy0); 00190 assert(y1 <= byy1); 00191 00192 if(x0 >= cx) { 00193 i += 1; 00194 bxx0 = cx; // zoom in a quad 00195 } else if(x1 <= cx) { 00196 bxx1 = cx; 00197 } else{ 00198 // rect does not fit in one unique quarter (in X axis) of the temp bounding box 00199 break; 00200 } 00201 if(y0 >= cy) { 00202 i += 2; 00203 byy0 = cy; 00204 } else if(y1 <= cy) { 00205 byy1 = cy; 00206 } else{ 00207 // rect does not fit in one unique quarter (in Y axis) of the temp bounding box 00208 break; 00209 } 00210 00211 // check if rect's bounding box has size 1x1. This means that rect is defined by 2 points 00212 // that are in the same place. 00213 if( ( fabs(bxx0 - bxx1) < 1.0 ) && ( fabs(byy0 - byy1) < 1.0 )){ 00214 bxx0 = floor(bxx0); 00215 bxx1 = floor(bxx1); 00216 byy0 = floor(byy0); 00217 byy1 = floor(byy1); 00218 break; 00219 } 00220 00221 /* 00222 1 rect does fit in one unique quarter of the temp bounding box. And we have found which. 00223 2 temp bounding box = bounding box of this quarter. 00224 3 "Go in" this quarter (create if doesn't exist) 00225 */ 00226 assert(i < 4); 00227 Quad *qq = q->children[i]; 00228 if(qq == 0) { 00229 qq = new Quad; 00230 q->children[i] = qq; 00231 } 00232 q = qq; 00233 } 00234 q->data.push_back(shape); 00235 }
| Quad * Geom::QuadTree::search | ( | Geom::Rect const & | r | ) |
Definition at line 4 of file quadtree.cpp.
References Geom::max(), Geom::min(), and search().
Definition at line 15 of file quadtree.cpp.
References bx1, by1, Geom::Quad::children, Barcode::Code39Ext::i, samplify::q, and root.
Referenced by search().
00015 { 00016 Quad *q = root; 00017 00018 double bxx0 = bx1, bxx1 = bx1; 00019 double byy0 = by1, byy1 = by1; 00020 while(q) { 00021 double cx = (bxx0 + bxx1)/2; 00022 double cy = (byy0 + byy1)/2; 00023 unsigned i = 0; 00024 if(x0 >= cx) { 00025 i += 1; 00026 bxx0 = cx; // zoom in a quad 00027 } else if(x1 <= cx) { 00028 bxx1 = cx; 00029 } else 00030 break; 00031 if(y0 >= cy) { 00032 i += 2; 00033 byy0 = cy; 00034 } else if(y1 <= cy) { 00035 byy1 = cy; 00036 } else 00037 break; 00038 00039 assert(i < 4); 00040 Quad *qq = q->children[i]; 00041 if(qq == 0) break; // last non-null 00042 q = qq; 00043 } 00044 return q; 00045 }
Member Data Documentation
Definition at line 74 of file quadtree.h.
Referenced by insert().
Definition at line 74 of file quadtree.h.
Definition at line 75 of file quadtree.h.
Referenced by insert().
Definition at line 75 of file quadtree.h.
Definition at line 72 of file quadtree.h.
Referenced by clean_root(), insert(), and search().
Definition at line 73 of file quadtree.h.
The documentation for this class was generated from the following files:
