BALL
1.4.1
|
00001 // -*- Mode: C++; tab-width: 2; -*- 00002 // vi: set ts=2: 00003 // 00004 00005 #ifndef BALL_DATATYPE_HASHGRID_H 00006 #define BALL_DATATYPE_HASHGRID_H 00007 00008 #ifndef BALL_COMMON_H 00009 # include <BALL/common.h> 00010 #endif 00011 00012 #ifndef BALL_CONCEPT_FORWARDITERATOR_H 00013 # include <BALL/CONCEPT/forwardIterator.h> 00014 #endif 00015 00016 #ifndef BALL_CONCEPT_VISITOR_H 00017 # include <BALL/CONCEPT/visitor.h> 00018 #endif 00019 00020 #ifndef BALL_CONCEPT_PROCESSOR_H 00021 # include <BALL/CONCEPT/processor.h> 00022 #endif 00023 00024 #ifndef BALL_MATHS_VECTOR3_H 00025 # include <BALL/MATHS/vector3.h> 00026 #endif 00027 00028 #ifdef BALL_HAS_GNU_SLIST 00029 #include <ext/slist> 00030 #else 00031 #include <list> 00032 #endif 00033 00034 #include <algorithm> 00035 00036 namespace BALL 00037 { 00038 namespace __private 00039 { 00040 extern const signed char BALL_EXPORT neighbour_table_[27][3]; 00041 } 00042 00043 template <typename Item> class HashGrid3; 00044 00049 00058 template <typename Item> 00059 class HashGridBox3 00060 { 00061 public: 00062 00066 00068 HashGridBox3(HashGrid3<Item>* parent); 00069 00071 void clear(); 00072 00076 void destroy(); 00077 00079 00082 00084 00087 00088 void setParent(HashGrid3<Item>* p); 00089 00093 void getIndices(Position& x, Position& y, Position& z); 00094 00100 Item* find(const Item &item); 00101 00103 const Item* find(const Item& item) const; 00104 00108 Size getSize() const; 00109 00113 void insert(const Item& item); 00114 00120 bool remove(const Item& item); 00121 00127 bool removeAll(const Item& item); 00128 00130 00133 00135 void host(Visitor<HashGridBox3> &visitor); 00137 00140 00142 bool operator == (const HashGridBox3& box) const; 00143 00145 bool operator != (const HashGridBox3& box) const; 00146 00151 bool has(const Item& item) const; 00152 00156 bool isEmpty() const; 00157 00159 00162 00164 bool isValid() const; 00166 void dump(std::ostream& s = std::cout, Size depth = 0) const; 00167 00169 00172 00174 bool apply(UnaryProcessor<Item>& processor); 00175 00177 bool apply(UnaryProcessor< HashGridBox3<Item> >& processor); 00178 00180 00183 typedef Position BoxIteratorPosition; 00184 00185 class BoxIteratorTraits 00186 { 00187 public: 00188 00189 BALL_CREATE_DEEP(BoxIteratorTraits) 00190 00191 virtual ~BoxIteratorTraits() {} 00192 00193 BoxIteratorTraits() 00194 : bound_(0), 00195 position_(0), 00196 x_(0), y_(0), z_(0) 00197 { 00198 } 00199 00200 BoxIteratorTraits(const HashGridBox3& box) 00201 : bound_((HashGridBox3 *)&box), 00202 position_(0) 00203 { 00204 bound_->getIndices(x_, y_, z_); 00205 } 00206 00207 BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true) 00208 : bound_(traits.bound_), 00209 position_(traits.position_) 00210 { 00211 } 00212 00213 HashGridBox3* getContainer() 00214 { 00215 return bound_; 00216 } 00217 00218 const HashGridBox3* getContainer() const 00219 { 00220 return bound_; 00221 } 00222 00223 bool isSingular() const 00224 { 00225 return (bound_ == 0); 00226 } 00227 00228 BoxIteratorPosition& getPosition() 00229 { 00230 return position_; 00231 } 00232 00233 const BoxIteratorPosition& getPosition() const 00234 { 00235 return position_; 00236 } 00237 00238 bool operator == (const BoxIteratorTraits& traits) const 00239 { 00240 return (position_ == traits.position_); 00241 } 00242 00243 bool operator != (const BoxIteratorTraits& traits) const 00244 { 00245 return (position_ != traits.position_); 00246 } 00247 00248 bool isValid() const 00249 { 00250 return (bound_ != 0 && position_ < 27); 00251 } 00252 00253 void invalidate() 00254 { 00255 bound_ = 0; 00256 position_ = 100; 00257 } 00258 00259 void toBegin() 00260 { 00261 position_ = 0; 00262 cur_box_ = bound_; 00263 } 00264 00265 bool isBegin() const 00266 { 00267 return (position_ == 0); 00268 } 00269 00270 void toEnd() 00271 { 00272 position_ = 27; 00273 cur_box_ = 0; 00274 } 00275 00276 bool isEnd() const 00277 { 00278 return (position_ == 27); 00279 } 00280 00281 HashGridBox3<Item>& getData() 00282 { 00283 return *cur_box_; 00284 } 00285 00286 const HashGridBox3<Item>& getData() const 00287 { 00288 return *cur_box_; 00289 } 00290 00291 void forward() 00292 { 00293 ++position_; 00294 // iterate to the next existing box 00295 while ( position_ < 27 00296 && !(cur_box_ = bound_->parent->getBox(x_ + __private::neighbour_table_[position_][0], 00297 y_ + __private::neighbour_table_[position_][1], 00298 z_ + __private::neighbour_table_[position_][2]))) 00299 { 00300 ++position_; 00301 } 00302 } 00303 00304 private: 00305 00306 HashGridBox3<Item> *bound_; 00307 HashGridBox3<Item> *cur_box_; 00308 BoxIteratorPosition position_; 00309 Position x_, y_, z_; 00310 }; 00311 00312 friend class BoxIteratorTraits; 00313 00318 typedef ForwardIterator 00319 <HashGridBox3<Item>, HashGridBox3<Item>, 00320 BoxIteratorPosition, BoxIteratorTraits> 00321 BoxIterator; 00322 00324 BoxIterator beginBox() 00325 { 00326 return BoxIterator::begin(*this); 00327 } 00328 00330 BoxIterator endBox() 00331 { 00332 return BoxIterator::end(*this); 00333 } 00334 00335 00337 typedef ConstForwardIterator 00338 <HashGridBox3<Item>, HashGridBox3<Item>, 00339 BoxIteratorPosition, BoxIteratorTraits> 00340 ConstBoxIterator; 00341 00343 ConstBoxIterator beginBox() const 00344 { 00345 return ConstBoxIterator::begin(*this); 00346 } 00347 00349 ConstBoxIterator endBox() const 00350 { 00351 return ConstBoxIterator::end(*this); 00352 } 00353 00354 #ifdef BALL_HAS_GNU_SLIST 00355 typedef typename __gnu_cxx::slist<Item> DataContainer; 00356 #else 00357 typedef typename std::list<Item> DataContainer; 00358 #endif 00359 00360 typedef typename DataContainer::iterator DataIteratorPosition; 00361 00362 class DataIteratorTraits 00363 { 00364 public: 00365 00366 BALL_CREATE_DEEP(DataIteratorTraits) 00367 00368 virtual ~DataIteratorTraits() {} 00369 00370 DataIteratorTraits() 00371 : bound_(0), 00372 position_() 00373 { 00374 } 00375 00376 DataIteratorTraits(const HashGridBox3& box) 00377 : bound_((HashGridBox3 *)&box), 00378 position_(bound_->data.begin()) 00379 { 00380 } 00381 00382 DataIteratorTraits(const DataIteratorTraits& traits, bool /* deep */ = true) 00383 : bound_(traits.bound_), 00384 position_(traits.position_) 00385 { 00386 } 00387 00388 const DataIteratorTraits& operator = (const DataIteratorTraits &traits) 00389 { 00390 bound_ = traits.bound_; 00391 position_ = traits.position_; 00392 return *this; 00393 } 00394 00395 HashGridBox3* getContainer() 00396 { 00397 return bound_; 00398 } 00399 00400 const HashGridBox3* getContainer() const 00401 { 00402 return bound_; 00403 } 00404 00405 bool isSingular() const 00406 { 00407 return (bound_ == 0); 00408 } 00409 00410 DataIteratorPosition& getPosition() 00411 { 00412 return position_; 00413 } 00414 00415 const DataIteratorPosition& getPosition() const 00416 { 00417 return position_; 00418 } 00419 00420 bool operator == (const DataIteratorTraits &traits) const 00421 { 00422 return (position_ == traits.position_); 00423 } 00424 00425 bool operator != (const DataIteratorTraits &traits) const 00426 { 00427 return (position_ != traits.position_); 00428 } 00429 00430 bool isValid() const 00431 { 00432 return (bound_ != 0 && position_ != bound_->data.end()); 00433 } 00434 00435 void invalidate() 00436 { 00437 bound_ = 0; 00438 position_ = bound_->data.end(); 00439 } 00440 00441 void toBegin() 00442 { 00443 position_ = bound_->data.begin(); 00444 } 00445 00446 bool isBegin() const 00447 { 00448 return (position_ == bound_->data.begin()); 00449 } 00450 00451 void toEnd() 00452 { 00453 position_ = bound_->data.end(); 00454 } 00455 00456 bool isEnd() const 00457 { 00458 return (position_ == bound_->data.end()); 00459 } 00460 00461 Item& getData() 00462 { 00463 return *position_; 00464 } 00465 00466 const Item& getData() const 00467 { 00468 return *position_; 00469 } 00470 00471 void forward() 00472 { 00473 ++position_; 00474 } 00475 00476 private: 00477 00478 HashGridBox3<Item>* bound_; 00479 DataIteratorPosition position_; 00480 }; 00481 00482 friend class DataIteratorTraits; 00483 00487 typedef ForwardIterator 00488 <HashGridBox3<Item>, Item, 00489 DataIteratorPosition, DataIteratorTraits> 00490 DataIterator; 00491 00493 DataIterator beginData() 00494 { 00495 return DataIterator::begin(*this); 00496 } 00497 00499 DataIterator endData() 00500 { 00501 return DataIterator::end(*this); 00502 } 00503 00504 00508 typedef ConstForwardIterator 00509 <HashGridBox3<Item>, Item, 00510 DataIteratorPosition, DataIteratorTraits> 00511 ConstDataIterator; 00512 00514 ConstDataIterator beginData() const 00515 { 00516 return ConstDataIterator::begin(*this); 00517 } 00518 00520 ConstDataIterator endData() const 00521 { 00522 return ConstDataIterator::end(*this); 00523 } 00524 00526 00527 HashGrid3<Item>* parent; 00528 00529 DataContainer data; 00530 }; 00531 00532 template<typename Item> 00533 HashGridBox3<Item>::HashGridBox3(HashGrid3<Item>* p) 00534 : parent(p) 00535 { 00536 } 00537 00538 template<typename Item> 00539 void HashGridBox3<Item>::clear() 00540 { 00541 data.clear(); 00542 } 00543 00544 template<typename Item> 00545 BALL_INLINE 00546 void HashGridBox3<Item>::destroy() 00547 { 00548 clear(); 00549 } 00550 00551 template<typename Item> 00552 BALL_INLINE void HashGridBox3<Item>::setParent(HashGrid3<Item>* p) 00553 { 00554 parent = p; 00555 } 00556 00557 template<typename Item> 00558 BALL_INLINE 00559 void HashGridBox3<Item>::getIndices(Position& x, Position& y, Position& z) 00560 { 00561 parent->getIndices(*this, x, y, z); 00562 } 00563 00564 template<typename Item> 00565 Item* HashGridBox3<Item>::find(const Item& item) 00566 { 00567 typename DataContainer::iterator found = std::find(data.begin(), data.end(), item); 00568 00569 if (found != data.end()) 00570 { 00571 return &(*found); 00572 } 00573 00574 return 0; 00575 } 00576 00577 template<typename Item> 00578 BALL_INLINE 00579 const Item* HashGridBox3<Item>::find(const Item& item) const 00580 { 00581 return const_cast<HashGridBox3*>(this)->find(item); 00582 } 00583 00584 template<typename Item> 00585 Size HashGridBox3<Item>::getSize() const 00586 { 00587 return data.size(); 00588 } 00589 00590 template<typename Item> 00591 BALL_INLINE 00592 void HashGridBox3<Item>::insert(const Item& item) 00593 { 00594 data.push_front(item); 00595 } 00596 00597 template<typename Item> 00598 bool HashGridBox3<Item>::remove(const Item& item) 00599 { 00600 #ifdef BALL_HAS_GNU_SLIST 00601 if(data.empty()) 00602 { 00603 return false; 00604 } 00605 00606 if(*data.begin() == item) 00607 { 00608 data.pop_front(); 00609 return true; 00610 } 00611 00612 DataIteratorPosition prev = data.begin(); 00613 DataIteratorPosition pos = prev; 00614 for(++pos; pos != data.end(); ++pos) 00615 { 00616 if(*pos == item) 00617 { 00618 data.erase_after(prev); 00619 return true; 00620 } 00621 00622 prev = pos; 00623 } 00624 return false; 00625 #else 00626 DataIteratorPosition pos = std::find(data.begin(), data.end(), item); 00627 00628 if (pos != data.end()) 00629 { 00630 data.erase(pos); 00631 00632 return true; 00633 } 00634 00635 return false; 00636 #endif 00637 } 00638 00639 template<typename Item> 00640 bool HashGridBox3<Item>::removeAll(const Item& item) 00641 { 00642 data.remove(item); 00643 00644 return true; 00645 } 00646 00647 template <typename Item> 00648 BALL_INLINE 00649 void HashGridBox3<Item>::host(Visitor< HashGridBox3<Item> >& visitor) 00650 { 00651 visitor.visit(*this); 00652 } 00653 00654 template<typename Item> 00655 bool HashGridBox3<Item>::operator == (const HashGridBox3<Item>& box) const 00656 { 00657 return (data == box.data); 00658 } 00659 00660 template<typename Item> 00661 BALL_INLINE 00662 bool HashGridBox3<Item>::operator != (const HashGridBox3<Item>& box) const 00663 { 00664 return !(*this == box); 00665 } 00666 00667 template<typename Item> 00668 BALL_INLINE 00669 bool HashGridBox3<Item>::has(const Item& item) const 00670 { 00671 return (std::find(data.begin(), data.end(), item) != data.end()); 00672 } 00673 00674 template<typename Item> 00675 BALL_INLINE 00676 bool HashGridBox3<Item>::isEmpty() const 00677 { 00678 return data.empty(); 00679 } 00680 00681 template<typename Item> 00682 bool HashGridBox3<Item>::isValid() const 00683 { 00684 // this is no longer required... 00685 return true; 00686 } 00687 00688 template<typename Item> 00689 void HashGridBox3<Item>::dump(std::ostream& s, Size depth) const 00690 { 00691 BALL_DUMP_STREAM_PREFIX(s); 00692 00693 BALL_DUMP_DEPTH(s, depth); 00694 00695 BALL_DUMP_DEPTH(s, depth); 00696 s << " size: " << getSize() << std::endl; 00697 00698 BALL_DUMP_DEPTH(s, depth); 00699 s << " data:" << std::endl; 00700 for (typename DataContainer::const_iterator d_it = data.begin(); d_it != data.end(); ++d_it) 00701 { 00702 BALL_DUMP_DEPTH(s, depth); 00703 s << " " << *d_it << std::endl; 00704 } 00705 00706 BALL_DUMP_STREAM_SUFFIX(s); 00707 } 00708 00709 template <typename Item> 00710 bool HashGridBox3<Item>::apply(UnaryProcessor<Item>& processor) 00711 { 00712 if (processor.start() == false) 00713 { 00714 return false; 00715 } 00716 00717 Processor::Result result; 00718 00719 for (typename DataContainer::iterator d_it = data.begin(); d_it != data.end(); ++d_it) 00720 { 00721 result = processor(*d_it); 00722 00723 if (result <= Processor::BREAK) 00724 { 00725 return (result == Processor::BREAK) ? true : false; 00726 } 00727 } 00728 00729 return processor.finish(); 00730 } 00731 00732 template <typename Item> 00733 bool HashGridBox3<Item>::apply(UnaryProcessor< HashGridBox3<Item> >& processor) 00734 { 00735 if (processor.start() == false) 00736 { 00737 return false; 00738 } 00739 00740 Processor::Result result; 00741 00742 for (BoxIterator it = beginBox(); +it; ++it) 00743 { 00744 result = processor(*it); 00745 00746 if (result <= Processor::BREAK) 00747 { 00748 return (result == Processor::BREAK) ? true : false; 00749 } 00750 } 00751 00752 return processor.finish(); 00753 } 00754 00759 template <typename Item> 00760 class HashGrid3 00761 { 00762 public: 00763 00764 BALL_CREATE(HashGrid3) 00765 00766 00769 00771 HashGrid3(); 00772 00783 HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y, 00784 Size dimension_z, float spacing_x, float spacing_y, float spacing_z); 00785 00789 HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y, 00790 Size dimension_z, float spacing); 00791 00801 HashGrid3(const Vector3& origin, const Vector3& size, float spacing); 00802 00804 HashGrid3(const HashGrid3& grid, bool deep = true); 00805 00807 virtual ~HashGrid3(); 00808 00810 virtual void clear(); 00811 00813 void clear(Position x, Position y, Position z); 00814 00816 void clear(const Vector3 &vector); 00817 00819 void destroy(); 00820 00822 void destroy(Position x, Position y, Position z); 00823 00825 void destroy(const Vector3& vector); 00826 00828 00831 00833 void set(const Vector3& origin, const Vector3& unit, 00834 Size dimension_x, Size dimension_y, Size dimension_z); 00835 00837 void set(const Vector3& origin, float unit, Size size); 00838 00840 void set(const HashGrid3& grid, bool deep = true); 00841 00843 const HashGrid3& operator = (const HashGrid3& grid); 00844 00846 void get(Vector3& origin, Vector3& unit, Size& dimension_x, Size& dimension_y, Size& dimension_z) const; 00847 00849 void get(HashGrid3& grid, bool deep = true) const; 00850 00852 00855 00857 Size countNonEmptyBoxes() const; 00858 00860 Size getSize() const; 00861 00863 Vector3& getOrigin(); 00864 00866 const Vector3& getOrigin() const; 00867 00869 Vector3& getUnit(); 00870 00872 const Vector3& getUnit() const; 00873 00875 Size getSizeX() const; 00876 00878 Size getSizeY() const; 00879 00881 Size getSizeZ() const; 00882 00884 HashGridBox3<Item>* getBox(Position x, Position y, Position z); 00885 00887 const HashGridBox3<Item>* getBox(Position x, Position y, Position z) const; 00888 00890 HashGridBox3<Item>* getBox(const Vector3& vector); 00891 00893 const HashGridBox3<Item>* getBox(const Vector3 &vector) const; 00894 00896 bool getIndices(const HashGridBox3<Item>& box, 00897 Position& x, Position& y, Position& z) const; 00898 00900 void insert(Position x, Position y, Position z, const Item& item); 00901 00903 void insert(const Vector3& vector, const Item& item); 00904 00906 bool remove(Position x, Position y, Position z, const Item& item); 00907 00909 bool remove(const Vector3& vector, const Item& item); 00910 00912 00915 00917 void host(Visitor<HashGrid3>& visitor); 00918 00920 00923 00925 bool operator == (const HashGrid3& grid) const; 00926 00928 bool operator != (const HashGrid3& grid) const; 00929 00931 bool isEmpty() const; 00932 00934 00937 00939 virtual bool isValid() const; 00940 00942 virtual void dump(std::ostream& s = std::cout, Size depth = 0) const; 00943 00945 00949 00951 bool apply(UnaryProcessor<Item> &processor); 00952 00954 bool apply(UnaryProcessor< HashGridBox3<Item> > &processor); 00955 00959 const Item* getClosestItem(const Vector3& point, Size distance) const; 00960 00967 static float calculateMinSpacing(LongIndex memory, const Vector3& size); 00968 00970 00973 00974 typedef Position BoxIteratorPosition; 00975 00976 class BoxIteratorTraits 00977 { 00978 public: 00979 00980 BALL_CREATE_DEEP(BoxIteratorTraits) 00981 00982 virtual ~BoxIteratorTraits() {} 00983 00984 BoxIteratorTraits() 00985 : bound_(0), 00986 position_(0) 00987 { 00988 } 00989 00990 BoxIteratorTraits(const HashGrid3 &grid) 00991 : bound_((HashGrid3 *)&grid), 00992 position_(0) 00993 { 00994 } 00995 00996 BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true) 00997 : bound_(traits.bound_), 00998 position_(traits.position_) 00999 { 01000 } 01001 01002 const BoxIteratorTraits& operator = (const BoxIteratorTraits& traits) 01003 { 01004 bound_ = traits.bound_; 01005 position_ = traits.position_; 01006 return *this; 01007 } 01008 01009 HashGrid3* getContainer() 01010 { 01011 return bound_; 01012 } 01013 01014 const HashGrid3* getContainer() const 01015 { 01016 return bound_; 01017 } 01018 01019 bool isSingular() const 01020 { 01021 return (bound_ == 0); 01022 } 01023 01024 BoxIteratorPosition& getPosition() 01025 { 01026 return position_; 01027 } 01028 01029 const BoxIteratorPosition& getPosition() const 01030 { 01031 return position_; 01032 } 01033 01034 bool operator == (const BoxIteratorTraits& traits) const 01035 { 01036 return (position_ == traits.position_); 01037 } 01038 01039 bool operator != (const BoxIteratorTraits& traits) const 01040 { 01041 return (position_ != traits.position_); 01042 } 01043 01044 bool isValid() const 01045 { 01046 return (bound_ != 0 && position_ < bound_->getSize()); 01047 } 01048 01049 void invalidate() 01050 { 01051 bound_ = 0; 01052 position_ = bound_->getSize()+1; 01053 } 01054 01055 void toBegin() 01056 { 01057 position_ = 0; 01058 } 01059 01060 bool isBegin() const 01061 { 01062 return (position_ == 0); 01063 } 01064 01065 void toEnd() 01066 { 01067 position_ = bound_->getSize(); 01068 } 01069 01070 bool isEnd() const 01071 { 01072 return (position_ == bound_->getSize()); 01073 } 01074 01075 HashGridBox3<Item>& getData() 01076 { 01077 return bound_->box_[position_]; 01078 } 01079 01080 const HashGridBox3<Item>& getData() const 01081 { 01082 return bound_->box_[position_]; 01083 } 01084 01085 void forward() 01086 { 01087 ++position_; 01088 } 01089 01090 private: 01091 01092 HashGrid3<Item>* bound_; 01093 BoxIteratorPosition position_; 01094 }; 01095 01096 friend class BoxIteratorTraits; 01097 01099 typedef ForwardIterator 01100 <HashGrid3<Item>, HashGridBox3<Item>, 01101 BoxIteratorPosition, BoxIteratorTraits> 01102 BoxIterator; 01103 01105 BoxIterator beginBox() 01106 { 01107 return BoxIterator::begin(*this); 01108 } 01109 01111 BoxIterator endBox() 01112 { 01113 return BoxIterator::end(*this); 01114 } 01115 01116 01118 typedef ConstForwardIterator 01119 <HashGrid3<Item>, HashGridBox3<Item>, 01120 BoxIteratorPosition, BoxIteratorTraits> 01121 ConstBoxIterator; 01122 01124 ConstBoxIterator beginBox() const 01125 { 01126 return ConstBoxIterator::begin(*this); 01127 } 01128 01130 ConstBoxIterator endBox() const 01131 { 01132 return ConstBoxIterator::end(*this); 01133 } 01134 01136 01137 private: 01138 01139 //_ 01140 Index getIndex_(const HashGridBox3<Item>& box) const; 01141 01142 //_ 01143 Vector3 origin_; 01144 //_ 01145 Vector3 unit_; 01146 //_ 01147 Size dimension_x_; 01148 //_ 01149 Size dimension_y_; 01150 //_ 01151 Size dimension_z_; 01152 //_ 01153 vector<HashGridBox3<Item> > box_; 01154 }; 01155 01156 01158 01159 01160 template <typename Item> 01161 HashGrid3<Item>::HashGrid3() 01162 : origin_(0,0,0), 01163 unit_(0,0,0), 01164 dimension_x_(0), 01165 dimension_y_(0), 01166 dimension_z_(0) 01167 { 01168 } 01169 01170 template <typename Item> 01171 HashGrid3<Item>::HashGrid3 01172 (const Vector3 &originvector, 01173 Size dimension_x, Size dimension_y, Size dimension_z, 01174 float spacing_x, float spacing_y, float spacing_z) 01175 : origin_(originvector), 01176 unit_(spacing_x, spacing_y, spacing_z), 01177 dimension_x_(dimension_x), 01178 dimension_y_(dimension_y), 01179 dimension_z_(dimension_z), 01180 box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this)) 01181 { 01182 } 01183 01184 template <typename Item> 01185 HashGrid3<Item>::HashGrid3 01186 (const Vector3& origin, 01187 Size dimension_x, Size dimension_y, Size dimension_z, float spacing) 01188 : origin_(origin), 01189 unit_(spacing, spacing, spacing), 01190 dimension_x_(dimension_x), 01191 dimension_y_(dimension_y), 01192 dimension_z_(dimension_z), 01193 box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this)) 01194 { 01195 } 01196 01197 // this constructor creates a linear array of HashGridBox3 objects. 01198 template <typename Item> 01199 HashGrid3<Item>::HashGrid3(const Vector3& origin, const Vector3& size, 01200 float spacing) 01201 : origin_(origin), 01202 unit_(spacing, spacing, spacing), 01203 dimension_x_((Size)(size.x / spacing + 1.0)), 01204 dimension_y_((Size)(size.y / spacing + 1.0)), 01205 dimension_z_((Size)(size.z / spacing + 1.0)), 01206 box_(dimension_x_ * dimension_y_ * dimension_z_, HashGridBox3<Item>(this)) 01207 { 01208 } 01209 01210 template <typename Item> 01211 HashGrid3<Item>::HashGrid3(const HashGrid3<Item>& grid, bool deep) 01212 { 01213 set(grid, deep); 01214 } 01215 01216 template <typename Item> 01217 HashGrid3<Item>::~HashGrid3() 01218 { 01219 } 01220 01221 template <typename Item> 01222 void HashGrid3<Item>::clear() 01223 { 01224 Size size = dimension_x_ * dimension_y_ * dimension_z_; 01225 01226 for (Position index = 0; index < (Position)size; ++index) 01227 { 01228 box_[index].clear(); 01229 } 01230 } 01231 01232 template <typename Item> 01233 BALL_INLINE 01234 void HashGrid3<Item>::clear(Position x, Position y, Position z) 01235 { 01236 HashGridBox3<Item>* box = getBox(x, y, z); 01237 01238 if (box != 0) 01239 { 01240 box->clear(); 01241 } 01242 } 01243 01244 template <typename Item> 01245 BALL_INLINE 01246 void HashGrid3<Item>::clear(const Vector3& vector) 01247 { 01248 HashGridBox3<Item>* box = getBox(vector); 01249 01250 if (box != 0) 01251 { 01252 box->clear(); 01253 } 01254 } 01255 01256 template <typename Item> 01257 BALL_INLINE 01258 void HashGrid3<Item>::destroy() 01259 { 01260 clear(); 01261 } 01262 01263 template <typename Item> 01264 BALL_INLINE 01265 void HashGrid3<Item>::destroy(Position x, Position y, Position z) 01266 { 01267 clear(x, y, z); 01268 } 01269 01270 template <typename Item> 01271 BALL_INLINE 01272 void HashGrid3<Item>::destroy(const Vector3 &vector) 01273 { 01274 clear(vector); 01275 } 01276 01277 template <typename Item> 01278 void HashGrid3<Item>::set 01279 (const Vector3& origin, const Vector3& unit, 01280 Size dimension_x, Size dimension_y, Size dimension_z) 01281 { 01282 origin_.set(origin); 01283 unit_.set(unit); 01284 dimension_x_ = dimension_x; 01285 dimension_y_ = dimension_y; 01286 dimension_z_ = dimension_z; 01287 box_.assign(getSize(), HashGridBox3<Item>(this)); 01288 } 01289 01290 template <typename Item> 01291 void HashGrid3<Item>::set(const Vector3& origin, float unit, Size size) 01292 { 01293 origin_.set(origin); 01294 unit_.set(unit, unit, unit); 01295 dimension_x_ = size; 01296 dimension_y_ = size; 01297 dimension_z_ = size; 01298 box_.assign(getSize(), HashGridBox3<Item>(this)); 01299 } 01300 01301 template <typename Item> 01302 void HashGrid3<Item>::set(const HashGrid3<Item>& grid, bool /* deep */) 01303 { 01304 origin_.set(grid.origin_); 01305 unit_.set(grid.unit_); 01306 dimension_x_ = grid.dimension_x_; 01307 dimension_y_ = grid.dimension_y_; 01308 dimension_z_ = grid.dimension_z_; 01309 box_ = grid.box_; 01310 01311 for(Position i = 0; i < box_.size(); ++i) 01312 { 01313 box_[i].setParent(this); 01314 } 01315 } 01316 01317 template <typename Item> 01318 BALL_INLINE 01319 const HashGrid3<Item>& HashGrid3<Item>::operator = (const HashGrid3<Item> &grid) 01320 { 01321 set(grid); 01322 01323 return *this; 01324 } 01325 01326 template <typename Item> 01327 BALL_INLINE 01328 void HashGrid3<Item>::get(Vector3 &origin, Vector3 &unit, 01329 Size& dimension_x, Size& dimension_y, Size& dimension_z) const 01330 { 01331 origin.set(origin_); 01332 unit.set(unit_); 01333 dimension_x = dimension_x_; 01334 dimension_y = dimension_y_; 01335 dimension_z = dimension_z_; 01336 } 01337 01338 template <typename Item> 01339 BALL_INLINE void 01340 HashGrid3<Item>::get(HashGrid3<Item> &grid, bool deep) const 01341 { 01342 grid.set(*this, deep); 01343 } 01344 01345 template <typename Item> 01346 Size 01347 HashGrid3<Item>::countNonEmptyBoxes() const 01348 { 01349 Size size = 0; 01350 01351 for (Position i=0; i<27; ++i) 01352 { 01353 if (!box_[i].isEmpty()) 01354 ++size; 01355 } 01356 01357 return size; 01358 } 01359 01360 template <typename Item> 01361 BALL_INLINE 01362 Size HashGrid3<Item>::getSize() const 01363 { 01364 return (dimension_x_ * dimension_y_ * dimension_z_); 01365 } 01366 01367 template <typename Item> 01368 BALL_INLINE 01369 Vector3& HashGrid3<Item>::getOrigin() 01370 { 01371 return origin_; 01372 } 01373 01374 template <typename Item> 01375 BALL_INLINE 01376 const Vector3& HashGrid3<Item>::getOrigin() const 01377 { 01378 return origin_; 01379 } 01380 01381 template <typename Item> 01382 BALL_INLINE 01383 Vector3& HashGrid3<Item>::getUnit() 01384 { 01385 return unit_; 01386 } 01387 01388 template <typename Item> 01389 BALL_INLINE 01390 const Vector3& HashGrid3<Item>::getUnit() const 01391 { 01392 return unit_; 01393 } 01394 01395 template <typename Item> 01396 BALL_INLINE 01397 Size HashGrid3<Item>::getSizeX() const 01398 { 01399 return dimension_x_; 01400 } 01401 01402 template <typename Item> 01403 BALL_INLINE 01404 Size HashGrid3<Item>::getSizeY() const 01405 { 01406 return dimension_y_; 01407 } 01408 01409 template <typename Item> 01410 BALL_INLINE 01411 Size HashGrid3<Item>::getSizeZ() const 01412 { 01413 return dimension_z_; 01414 } 01415 01416 template <typename Item> 01417 const Item* HashGrid3<Item>::getClosestItem(const Vector3& point, Size dist) const 01418 { 01419 const HashGridBox3<Item>* box = getBox(point); 01420 if (!box) return 0; 01421 01422 Position x, y, z; 01423 getIndices(*box, x, y, z); 01424 01425 const Item* item = 0; 01426 float distance = FLT_MAX; 01427 01428 // iterator over neighbour boxes 01429 for (Index xi = -(Index)dist; xi <= (Index)dist; xi++) 01430 { 01431 const Index xn = x + xi; 01432 for (Index yi = -(Index)dist; yi <= (Index)dist; yi++) 01433 { 01434 const Index yn = y + yi; 01435 for (Index zi = -(Index)dist; zi <= (Index)dist; zi++) 01436 { 01437 // iterate over all data items 01438 const HashGridBox3<Item>* const box_ptr = getBox(xn, yn, z+zi); 01439 if (box_ptr != 0 && !box_ptr->isEmpty()) 01440 { 01441 typename HashGridBox3<Item>::ConstDataIterator hit = box_ptr->beginData(); 01442 for (;hit != box_ptr->endData(); hit++) 01443 { 01444 const float new_dist = ((*hit)->getPosition() - point).getSquareLength(); 01445 if (new_dist < distance) 01446 { 01447 item = &*hit; 01448 distance = new_dist; 01449 } 01450 } 01451 } 01452 } 01453 } 01454 } 01455 01456 return item; 01457 } 01458 01459 template <typename Item> 01460 BALL_INLINE 01461 float HashGrid3<Item>::calculateMinSpacing(LongIndex memory, const Vector3& size) 01462 { 01463 LongSize memory_for_box = sizeof(HashGridBox3<Item>) + sizeof(HashGridBox3<Item>*); 01464 LongSize nr_boxes =(LongSize)floor((float)(memory / memory_for_box)); 01465 01466 return pow((double)((size.x * size.y * size.z) / nr_boxes), (double)(1.0 / 3.0)); 01467 } 01468 01469 template <typename Item> 01470 BALL_INLINE 01471 HashGridBox3<Item>* HashGrid3<Item>::getBox(Position x, Position y, Position z) 01472 { 01473 if (x >= (Position)dimension_x_ || 01474 y >= (Position)dimension_y_ || 01475 z >= (Position)dimension_z_) 01476 { 01477 return 0; 01478 } 01479 else 01480 { 01481 return &(box_[x * dimension_y_ * dimension_z_ + y * dimension_z_ + z]); 01482 } 01483 } 01484 01485 template <typename Item> 01486 BALL_INLINE 01487 const HashGridBox3<Item>* HashGrid3<Item>::getBox(Position x, Position y, Position z) const 01488 { 01489 return ((HashGrid3*)this)->getBox(x, y, z); 01490 } 01491 01492 template <typename Item> 01493 BALL_INLINE 01494 HashGridBox3<Item>* HashGrid3<Item>::getBox(const Vector3& vector) 01495 { 01496 float x = (vector.x - origin_.x) / unit_.x; 01497 float y = (vector.y - origin_.y) / unit_.y; 01498 float z = (vector.z - origin_.z) / unit_.z; 01499 01500 // workaround for MSVC 7, dont change this !!! 01501 Index x1 = (Index) Maths::floor(x); 01502 Index y1 = (Index) Maths::floor(y); 01503 Index z1 = (Index) Maths::floor(z); 01504 01505 return getBox(x1, y1, z1); 01506 } 01507 01508 template <typename Item> 01509 BALL_INLINE 01510 const HashGridBox3<Item>* HashGrid3<Item>::getBox(const Vector3& vector) const 01511 { 01512 return ((HashGrid3 *)this)->getBox(vector); 01513 } 01514 01515 template <typename Item> 01516 BALL_INLINE 01517 bool HashGrid3<Item>::getIndices 01518 (const HashGridBox3<Item>& box, 01519 Position& x, Position& y, Position& z) const 01520 { 01521 Index index = getIndex_(box); 01522 01523 if (index == INVALID_INDEX) 01524 { 01525 x = y = z = INVALID_POSITION; 01526 01527 return false; 01528 } 01529 01530 x = index / (dimension_y_ * dimension_z_); 01531 index -= x * dimension_y_ * dimension_z_; 01532 y = index / dimension_z_; 01533 z = index - y * dimension_z_; 01534 01535 return true; 01536 } 01537 01538 template <typename Item> 01539 BALL_INLINE 01540 void HashGrid3<Item>::insert 01541 (Position x, Position y, Position z, const Item& item) 01542 { 01543 HashGridBox3<Item>* box = getBox(x, y, z); 01544 01545 if (box != 0) 01546 { 01547 box->insert(item); 01548 } 01549 } 01550 01551 template <typename Item> 01552 BALL_INLINE 01553 void HashGrid3<Item>::insert(const Vector3& vector, const Item& item) 01554 { 01555 HashGridBox3<Item> *box = getBox(vector); 01556 01557 if (box != 0) 01558 { 01559 box->insert(item); 01560 } 01561 } 01562 01563 template <typename Item> 01564 BALL_INLINE 01565 bool HashGrid3<Item>::remove(Position x, Position y, Position z, const Item& item) 01566 { 01567 HashGridBox3<Item>* box = getBox(x, y, z); 01568 01569 if (box != 0) 01570 { 01571 return box->remove(item); 01572 } 01573 01574 return false; 01575 } 01576 01577 template <typename Item> 01578 BALL_INLINE 01579 bool HashGrid3<Item>::remove(const Vector3& vector, const Item& item) 01580 { 01581 HashGridBox3<Item>* box = getBox(vector); 01582 01583 if (box != 0) 01584 { 01585 return box->remove(item); 01586 } 01587 01588 return false; 01589 } 01590 01591 template <typename Item> 01592 BALL_INLINE 01593 void HashGrid3<Item>::host(Visitor< HashGrid3<Item> >& visitor) 01594 { 01595 visitor.visit(*this); 01596 } 01597 01598 template <typename Item> 01599 BALL_INLINE 01600 bool HashGrid3<Item>::operator == (const HashGrid3<Item>& grid) const 01601 { 01602 if (getSize() != grid.getSize() 01603 || origin_ != grid.origin_ 01604 || unit_ != grid.unit_ 01605 || dimension_x_ != grid.dimension_x_ 01606 || dimension_y_ != grid.dimension_y_ 01607 || dimension_z_ != grid.dimension_z_) 01608 { 01609 return false; 01610 } 01611 01612 return box_ == grid.box_; 01613 } 01614 01615 template <typename Item> 01616 BALL_INLINE 01617 bool HashGrid3<Item>::operator != (const HashGrid3<Item>& grid) const 01618 { 01619 return !(*this == grid); 01620 } 01621 01622 template <typename Item> 01623 BALL_INLINE 01624 bool HashGrid3<Item>::isEmpty() const 01625 { 01626 return (getSize() == 0); 01627 } 01628 01629 template <typename Item> 01630 bool HashGrid3<Item>::isValid() const 01631 { 01632 Size size = getSize(); 01633 01634 for (Position index = 0; index < (Position)size; ++index) 01635 { 01636 if (box_[index].isValid() == false) 01637 { 01638 return false; 01639 } 01640 } 01641 01642 return true; 01643 } 01644 01645 template <typename Item> 01646 void HashGrid3<Item>::dump(std::ostream& s, Size depth) const 01647 { 01648 BALL_DUMP_STREAM_PREFIX(s); 01649 01650 BALL_DUMP_DEPTH(s, depth); 01651 01652 BALL_DUMP_DEPTH(s, depth); 01653 s << " origin: " << origin_ << std::endl; 01654 01655 BALL_DUMP_DEPTH(s, depth); 01656 s << " unit: " << unit_.z << std::endl; 01657 01658 BALL_DUMP_DEPTH(s, depth); 01659 s << " dimension: " << dimension_x_ << " " 01660 << dimension_y_ << " " 01661 << dimension_z_ << std::endl; 01662 01663 Size size = getSize(); 01664 BALL_DUMP_DEPTH(s, depth); 01665 s << " size: " << size << std::endl; 01666 01667 BALL_DUMP_DEPTH(s, depth); 01668 s << " non empty boxes: " << countNonEmptyBoxes() << std::endl; 01669 01670 BALL_DUMP_DEPTH(s, depth); 01671 s << " boxes:" << std::endl; 01672 Position x, y, z; 01673 for (Position index = 0; index < (Position)size; ++index) 01674 { 01675 BALL_DUMP_DEPTH(s, depth); 01676 getIndices(box_[index], x, y, z); 01677 s << " " << index << ". box: (" 01678 << x << ',' << y << ',' << z << ')' << std::endl; 01679 box_[index].dump(s, 1); 01680 } 01681 01682 BALL_DUMP_DEPTH(s, depth); 01683 s << " non-empty boxes:" << std::endl; 01684 01685 for (Position i=0; i<27; ++i) 01686 { 01687 if (!box_[i].isEmpty()) 01688 s << " " << getIndex_(box_[i]) << std::endl; 01689 } 01690 BALL_DUMP_STREAM_SUFFIX(s); 01691 } 01692 01693 template <typename Item> 01694 bool HashGrid3<Item>::apply(UnaryProcessor<Item>& processor) 01695 { 01696 if (processor.start() == false) 01697 { 01698 return false; 01699 } 01700 Processor::Result result; 01701 01702 for (Position i=0; i<27; ++i) 01703 { 01704 HashGridBox3<Item>* box = &box_[i]; 01705 for (typename HashGridBox3<Item>::DataIterator *item = box->beginData(); +item; ++item) 01706 { 01707 result = processor(*item); 01708 01709 if (result <= Processor::BREAK) 01710 { 01711 return (result == Processor::BREAK) ? true : false; 01712 } 01713 } 01714 } 01715 01716 return processor->finish(); 01717 } 01718 01719 template <typename Item> 01720 bool HashGrid3<Item>::apply(UnaryProcessor< HashGridBox3<Item> >& processor) 01721 { 01722 if (processor.start() == false) 01723 { 01724 return false; 01725 } 01726 01727 Processor::Result result; 01728 01729 for (Position i=0; i<27; ++i) 01730 { 01731 HashGridBox3<Item>* box = &box_[i]; 01732 result = processor(*box); 01733 01734 if (result <= Processor::BREAK) 01735 { 01736 return (result == Processor::BREAK) ? true : false; 01737 } 01738 } 01739 01740 return processor->finish(); 01741 } 01742 01743 template <typename Item> 01744 BALL_INLINE 01745 Index HashGrid3<Item>::getIndex_(const HashGridBox3<Item>& box) const 01746 { 01747 if ((&box < &box_[0]) || (&box - &box_[0] >= getSize())) 01748 { 01749 return INVALID_INDEX; 01750 } 01751 else 01752 { 01753 return (Index)(&box - &box_[0]); 01754 } 01755 } 01756 } // namespace BALL 01757 01758 #endif // BALL_DATATYPE_HASHGRID_H