Image Component Library (ICL)
|
00001 /******************************************************************** 00002 ** Image Component Library (ICL) ** 00003 ** ** 00004 ** Copyright (C) 2006-2013 CITEC, University of Bielefeld ** 00005 ** Neuroinformatics Group ** 00006 ** Website: www.iclcv.org and ** 00007 ** http://opensource.cit-ec.de/projects/icl ** 00008 ** ** 00009 ** File : ICLMath/src/ICLMath/QuadTree.h ** 00010 ** Module : ICLMath ** 00011 ** Authors: Christof Elbrechter ** 00012 ** ** 00013 ** ** 00014 ** GNU LESSER GENERAL PUBLIC LICENSE ** 00015 ** This file may be used under the terms of the GNU Lesser General ** 00016 ** Public License version 3.0 as published by the ** 00017 ** ** 00018 ** Free Software Foundation and appearing in the file LICENSE.GPL ** 00019 ** included in the packaging of this file. Please review the ** 00020 ** following information to ensure the license requirements will ** 00021 ** be met: http://www.gnu.org/licenses/lgpl-3.0.txt ** 00022 ** ** 00023 ** The development of this software was supported by the ** 00024 ** Excellence Cluster EXC 277 Cognitive Interaction Technology. ** 00025 ** The Excellence Cluster EXC 277 is a grant of the Deutsche ** 00026 ** Forschungsgemeinschaft (DFG) in the context of the German ** 00027 ** Excellence Initiative. ** 00028 ** ** 00029 ********************************************************************/ 00030 00031 #pragma once 00032 00033 00034 #include <algorithm> 00035 #include <set> 00036 00037 #include <ICLMath/FixedVector.h> 00038 #include <ICLUtils/VisualizationDescription.h> 00039 #include <ICLUtils/Rect32f.h> 00040 #include <ICLUtils/Range.h> 00041 #include <ICLUtils/StringUtils.h> 00042 00043 namespace icl{ 00044 00045 namespace math{ 00046 00047 00049 00173 template<class Scalar, int CAPACITY=4, int SF=1, int ALLOC_CHUNK_SIZE=1024> 00174 class QuadTree{ 00175 public: 00176 00177 // 2D-point type, internally used 00178 typedef FixedColVector<Scalar,2> Pt; 00179 00180 protected: 00181 00183 00185 struct AABB{ 00186 Pt center; 00187 Pt halfSize; 00188 00190 AABB(){} 00191 00193 AABB(const Pt ¢er, const Pt &halfSize): 00194 center(center),halfSize(halfSize){} 00195 00197 bool contains(const Pt &p) const{ 00198 return ( p[0] >= center[0] - halfSize[0] 00199 && p[1] >= center[1] - halfSize[1] 00200 && p[0] <= center[0] + halfSize[0] 00201 && p[1] <= center[1] + halfSize[1]); 00202 } 00203 00205 bool intersects(const AABB &o) const{ 00206 return (fabs(center[0] - o.center[0]) < (halfSize[0] + o.halfSize[0]) 00207 && fabs(center[1] - o.center[1]) < (halfSize[1] + o.halfSize[1])); 00208 } 00209 00210 00211 utils::Rect32f rect() const { 00212 return utils::Rect32f(double(center[0])/SF - double(halfSize[0])/SF, double(center[1])/SF - double(halfSize[1])/SF, 00213 double(halfSize[0])/SF*2, double(halfSize[1])/SF*2); 00214 } 00215 }; 00216 00218 00220 struct Node{ 00221 AABB boundary; 00222 Pt points[CAPACITY]; 00223 Pt *next; 00224 Node *children; 00225 Node *parent; 00226 00228 Node(){} 00229 00231 Node(const AABB &boundary){ 00232 init(0,boundary); 00233 } 00235 00236 void init(Node *parent, const AABB &boundary){ 00237 this->boundary = boundary; 00238 this->next = this->points; 00239 this->children = 0; 00240 this->parent = parent; 00241 } 00242 00244 00247 void query(const AABB &boundary, std::vector<Pt> &found) const{ 00248 if (!this->boundary.intersects(boundary)){ 00249 return; 00250 } 00251 for(const Pt *p=points; p<next ; ++p){ 00252 if(boundary.contains(*p)){ 00253 found.push_back(Pt((*p)[0]/SF,(*p)[1]/SF)); 00254 } 00255 } 00256 if(!children) return; 00257 00258 children[0].query(boundary,found); 00259 children[1].query(boundary,found); 00260 children[2].query(boundary,found); 00261 children[3].query(boundary,found); 00262 } 00263 00265 00268 void split(Node *children){ 00269 const Pt half = boundary.halfSize/2;//*0.5; 00270 00271 const Pt &c = boundary.center; 00272 this->children = children; 00273 this->children[0].init(this,AABB(Pt(c[0]-half[0],c[1]-half[1]),half)); 00274 this->children[1].init(this,AABB(Pt(c[0]+half[0],c[1]-half[1]),half)); 00275 this->children[2].init(this,AABB(Pt(c[0]-half[0],c[1]+half[1]),half)); 00276 this->children[3].init(this,AABB(Pt(c[0]+half[0],c[1]+half[1]),half)); 00277 } 00278 00280 void vis(utils::VisualizationDescription &d) const{ 00281 d.rect(boundary.rect()); 00282 if(children){ 00283 children[0].vis(d); 00284 children[1].vis(d); 00285 children[2].vis(d); 00286 children[3].vis(d); 00287 } 00288 } 00289 00290 void printStructure(int indent){ 00291 for(int i=0;i<indent;++i) std::cout << " "; 00292 if(children){ 00293 std::cout << "Branch ("; 00294 }else{ 00295 std::cout << "Leaf ("; 00296 } 00297 std::cout << "AABB=" << boundary.rect() << ", "; 00298 std::cout << "Content=" <<(int)(next-points) << "/" << CAPACITY; 00299 std::cout << ")"; 00300 if(children){ 00301 std::cout << " {" << std::endl; 00302 children[0].printStructure(indent+1); 00303 children[1].printStructure(indent+1); 00304 children[2].printStructure(indent+1); 00305 children[3].printStructure(indent+1); 00306 for(int i=0;i<indent;++i) std::cout << " "; 00307 std::cout << "}" << std::endl;; 00308 } 00309 else std::cout << std::endl; 00310 00311 } 00312 00313 }; 00314 00316 00318 struct Allocator{ 00319 00321 std::vector<Node*> allocated; 00322 00324 int curr; 00325 00327 Allocator(){ grow(); } 00328 00330 void grow(){ 00331 allocated.push_back(new Node[ALLOC_CHUNK_SIZE*4]); 00332 curr = 0; 00333 } 00334 00336 void clear(){ 00337 for(size_t i=1;i<allocated.size();++i){ 00338 delete [] allocated[i]; 00339 } 00340 allocated.resize(1); 00341 curr = 0; 00342 } 00343 00345 Node *next(){ 00346 if(curr == ALLOC_CHUNK_SIZE) grow(); 00347 return allocated.back()+4*curr++; 00348 } 00349 00351 ~Allocator(){ 00352 for(size_t i=0;i<allocated.size();++i){ 00353 delete [] allocated[i]; 00354 } 00355 } 00356 00358 std::vector<Pt> all() const{ 00359 std::vector<Pt> pts; 00360 for(size_t i=0;i<allocated.size()-1;++i){ 00361 const Node *ns = allocated[i]; 00362 for(size_t j=0;j<allocated.size();++j){ 00363 for(const Pt* p = ns[j].points; p != ns[j].next;++p){ 00364 pts.push_back(Pt((*p)[0]/SF,(*p)[1]/SF)); 00365 } 00366 } 00367 } 00368 const Node *ns = allocated.back(); 00369 for(int i=0;i<curr*4;++i){ 00370 for(const Pt* p = ns[i].points; p != ns[i].next;++p){ 00371 pts.push_back(Pt((*p)[0]/SF,(*p)[1]/SF)); 00372 } 00373 } 00374 return pts; 00375 } 00376 }; 00377 00379 Node *root; 00380 00382 Allocator alloc; 00383 00385 int num; 00386 00387 public: 00389 QuadTree(const Scalar &minX, const Scalar &minY, const Scalar &width, const Scalar &height):num(0){ 00390 this->root = new Node(AABB(Pt(SF*minX+SF*width/2, SF*minY+SF*height/2), 00391 Pt(SF*width/2,SF*height/2))); 00392 } 00393 00395 QuadTree(const utils::Rect32f &bounds):num(0){ 00396 this->root = new Node(AABB(Pt(SF*bounds.x+SF*bounds.width/2, SF*bounds.y+SF*bounds.height/2), 00397 Pt(SF*bounds.width/2,SF*bounds.height/2))); 00398 } 00399 00401 QuadTree(const utils::Rect &bounds):num(0){ 00402 this->root = new Node(AABB(Pt(SF*bounds.x+SF*bounds.width/2, SF*bounds.y+SF*bounds.height/2), 00403 Pt(SF*bounds.width/2,SF*bounds.height/2))); 00404 } 00405 00407 QuadTree(const Scalar &width, const Scalar &height):num(0){ 00408 this->root = new Node(AABB(Pt(SF*width/2,SF*height/2), 00409 Pt(SF*width/2,SF*height/2))); 00410 } 00411 00413 QuadTree(const utils::Size32f &size):num(0){ 00414 this->root = new Node(AABB(Pt(SF*size.width/2,SF*size.height/2), 00415 Pt(SF*size.width/2,SF*size.height/2))); 00416 } 00417 00419 QuadTree(const utils::Size &size):num(0){ 00420 this->root = new Node(AABB(Pt(SF*size.width/2,SF*size.height/2), 00421 Pt(SF*size.width/2,SF*size.height/2))); 00422 } 00423 00425 00426 ~QuadTree(){ 00427 // the root node is not part of the allocator 00428 delete root; 00429 } 00430 00431 protected: 00432 00434 const Pt &nn_approx_internal(const Pt &p, double &currMinDist, const Pt *&currNN) const throw (utils::ICLException){ 00435 // 1st find cell, that continas p 00436 const Node *n = root; 00437 while(n->children){ 00438 n = (n->children + (p[0] > n->boundary.center[0]) + 2 * (p[1] > n->boundary.center[1])); 00439 } 00440 00441 // this cell could be empty, in this case, the parent must contain good points 00442 if(n->next == n->points){ 00443 n = n->parent; 00444 if(!n) throw utils::ICLException("no nn found for given point " + utils::str(p)); 00445 } 00446 00447 double sqrMinDist = utils::sqr(currMinDist); 00448 00449 for(const Pt *x=n->points; x < n->next; ++x){ 00450 Scalar dSqr = utils::sqr(x->operator[](0)-p[0]) + utils::sqr(x->operator[](1)-p[1]); 00451 if(dSqr < sqrMinDist){ 00452 sqrMinDist = dSqr; 00453 currNN = x; 00454 } 00455 } 00456 currMinDist = sqrt(sqrMinDist); 00457 00458 if(!currNN){ 00459 throw utils::ICLException("no nn found for given point " + utils::str(p)); 00460 } 00461 return *currNN; 00462 } 00463 public: 00464 00465 00467 00476 Pt nn_approx(const Pt &p) const throw (utils::ICLException){ 00477 double currMinDist = sqrt(utils::Range<Scalar>::limits().maxVal-1); 00478 const Pt *currNN = 0; 00479 nn_approx_internal(Pt(SF*p[0],SF*p[1]),currMinDist,currNN); 00480 return Pt((*currNN)[0]/SF,(*currNN)[1]/SF) ; 00481 } 00482 00484 00502 Pt nn(const Pt &pIn) const throw (utils::ICLException){ 00503 const Pt p(SF*pIn[0],SF*pIn[1]); 00504 std::vector<const Node*> stack; 00505 stack.reserve(128); 00506 stack.push_back(root); 00507 double currMinDist = sqrt(utils::Range<Scalar>::limits().maxVal-1); 00508 const Pt *currNN = 0; 00509 00510 nn_approx_internal(p,currMinDist,currNN); 00511 00512 while(stack.size()){ 00513 const Node *n = stack.back(); 00514 stack.pop_back(); 00515 if(n->children){ 00516 const AABB b(p, Pt(currMinDist,currMinDist)); 00517 if(b.intersects(n->children[0].boundary)) stack.push_back(n->children); 00518 if(b.intersects(n->children[1].boundary)) stack.push_back(n->children+1); 00519 if(b.intersects(n->children[2].boundary)) stack.push_back(n->children+2); 00520 if(b.intersects(n->children[3].boundary)) stack.push_back(n->children+3); 00521 } 00522 Scalar sqrMinDist = utils::sqr(currMinDist); 00523 00524 for(const Pt *x=n->points; x < n->next; ++x){ 00525 Scalar dSqr = utils::sqr(x->operator[](0)-p[0]) + utils::sqr(x->operator[](1)-p[1]); 00526 if(dSqr < sqrMinDist){ 00527 sqrMinDist = dSqr; 00528 currNN = x; 00529 } 00530 } 00531 currMinDist = sqrt(sqrMinDist); 00532 } 00533 return Pt((*currNN)[0]/SF, (*currNN)[1]/SF); 00534 } 00535 00537 const utils::Point32f nn(const utils::Point32f &p) const throw (utils::ICLException){ 00538 Pt n = nn(Pt(p.x,p.y)); 00539 return utils::Point32f(n[0],n[1]); 00540 } 00541 00543 const utils::Point nn(const utils::Point &p) const throw (utils::ICLException){ 00544 Pt n = nn(Pt(p.x,p.y)); 00545 return utils::Point(n[0],n[1]); 00546 } 00547 00548 00550 00553 void insert(const Pt &pIn){ 00554 ++num; 00555 const Pt p(SF*pIn[0],SF*pIn[1]); 00556 Node *n = root; 00557 while(true){ 00558 if(n->next != n->points+CAPACITY){ 00559 *n->next++ = p; 00560 return; 00561 } 00562 if(!n->children) n->split(alloc.next()); 00563 n = (n->children + (p[0] > n->boundary.center[0]) + 2 * (p[1] > n->boundary.center[1])); 00564 } 00565 } 00566 00568 void insert(const utils::Point32f &p){ 00569 insert(Pt(p.x,p.y)); 00570 } 00571 00573 void insert(const utils::Point &p){ 00574 insert(Pt(p.x,p.y)); 00575 } 00576 00578 std::vector<Pt> query(const Scalar &minX, const Scalar &minY, 00579 const Scalar &width, const Scalar &height) const{ 00580 AABB range(Pt(SF*minX+SF*width/2, SF*minY+SF*height/2), 00581 Pt(SF*width/2,SF*height/2)); 00582 std::vector<Pt> found; 00583 root->query(range,found); 00584 return found; 00585 } 00586 00588 std::vector<Pt> query(const utils::Rect &r) const { return query(r.x,r.y,r.width,r.height); } 00589 00591 std::vector<Pt> query(const utils::Rect32f &r) const { return query(r.x,r.y,r.width,r.height); } 00592 00594 std::vector<Pt> queryAll() const { 00595 return alloc.all(); 00596 } 00597 00599 utils::VisualizationDescription vis() const{ 00600 utils::VisualizationDescription d; 00601 d.color(0,100,255,255); 00602 d.fill(0,0,0,0); 00603 root->vis(d); 00604 return d; 00605 } 00606 00608 00609 void clear(){ 00610 root->next = root->points; 00611 root->children = 0; 00612 alloc.clear(); 00613 num = 0; 00614 } 00615 00617 int size() const { 00618 return num; 00619 } 00620 00622 void printStructure(){ 00623 std::cout << "QuadTree{" << std::endl; 00624 root->printStructure(1); 00625 std::cout << "}" << std::endl; 00626 } 00627 }; 00628 00629 } // namespace math 00630 } // namespace icl 00631