BALL  1.5.0
hashGrid.h
Go to the documentation of this file.
1 // -*- Mode: C++; tab-width: 2; -*-
2 // vi: set ts=2:
3 //
4 
5 #ifndef BALL_DATATYPE_HASHGRID_H
6 #define BALL_DATATYPE_HASHGRID_H
7 
8 #ifndef BALL_COMMON_H
9 # include <BALL/common.h>
10 #endif
11 
12 #ifndef BALL_CONCEPT_FORWARDITERATOR_H
14 #endif
15 
16 #ifndef BALL_CONCEPT_VISITOR_H
17 # include <BALL/CONCEPT/visitor.h>
18 #endif
19 
20 #ifndef BALL_CONCEPT_PROCESSOR_H
21 # include <BALL/CONCEPT/processor.h>
22 #endif
23 
24 #ifndef BALL_MATHS_VECTOR3_H
25 # include <BALL/MATHS/vector3.h>
26 #endif
27 
28 #include <algorithm>
29 #include <forward_list>
30 
31 namespace BALL
32 {
33  namespace __private
34  {
35  extern const signed char BALL_EXPORT neighbour_table_[27][3];
36  }
37 
38  template <typename Item> class HashGrid3;
39 
44 
53  template <typename Item>
55  {
56  public:
57 
61 
64 
66  void clear();
67 
71  void destroy();
72 
74 
77 
79 
82 
84 
89 
95  Item* find(const Item &item);
96 
98  const Item* find(const Item& item) const;
99 
103  Size getSize() const;
104 
108  void insert(const Item& item);
109 
115  bool remove(const Item& item);
116 
122  bool removeAll(const Item& item);
123 
125 
128 
130  void host(Visitor<HashGridBox3> &visitor);
132 
135 
137  bool operator == (const HashGridBox3& box) const;
138 
140  bool operator != (const HashGridBox3& box) const;
141 
146  bool has(const Item& item) const;
147 
151  bool isEmpty() const;
152 
154 
157 
159  bool isValid() const;
161  void dump(std::ostream& s = std::cout, Size depth = 0) const;
162 
164 
167 
169  bool apply(UnaryProcessor<Item>& processor);
170 
173 
175 
179 
181  {
182  public:
183 
185 
186  virtual ~BoxIteratorTraits() {}
187 
189  : bound_(nullptr),
190  cur_box_(nullptr),
191  position_(0),
192  x_(0),
193  y_(0),
194  z_(0)
195  {
196  }
197 
199  : bound_((HashGridBox3 *)&box),
200  cur_box_(bound_),
201  position_(0),
202  x_(0),
203  y_(0),
204  z_(0)
205  {
206  bound_->getIndices(x_, y_, z_);
207  }
208 
209  BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
210  : bound_(traits.bound_),
211  cur_box_(traits.cur_box_),
212  position_(traits.position_),
213  x_(traits.x_),
214  y_(traits.y_),
215  z_(traits.z_)
216  {
217  }
218 
220  {
221  return bound_;
222  }
223 
224  const HashGridBox3* getContainer() const
225  {
226  return bound_;
227  }
228 
229  bool isSingular() const
230  {
231  return !bound_;
232  }
233 
235  {
236  return position_;
237  }
238 
240  {
241  return position_;
242  }
243 
244  bool operator == (const BoxIteratorTraits& traits) const
245  {
246  return (position_ == traits.position_);
247  }
248 
249  bool operator != (const BoxIteratorTraits& traits) const
250  {
251  return (position_ != traits.position_);
252  }
253 
254  bool isValid() const
255  {
256  return (bound_ && position_ < 27);
257  }
258 
259  void invalidate()
260  {
261  bound_ = nullptr;
262  position_ = 100;
263  }
264 
265  void toBegin()
266  {
267  position_ = 0;
268  cur_box_ = bound_;
269  }
270 
271  bool isBegin() const
272  {
273  return (position_ == 0);
274  }
275 
276  void toEnd()
277  {
278  position_ = 27;
279  cur_box_ = 0;
280  }
281 
282  bool isEnd() const
283  {
284  return (position_ == 27);
285  }
286 
288  {
289  return *cur_box_;
290  }
291 
293  {
294  return *cur_box_;
295  }
296 
297  void forward()
298  {
299  ++position_;
300  // iterate to the next existing box
301  while ( position_ < 27
302  && !(cur_box_ = bound_->parent->getBox(x_ + __private::neighbour_table_[position_][0],
303  y_ + __private::neighbour_table_[position_][1],
304  z_ + __private::neighbour_table_[position_][2])))
305  {
306  ++position_;
307  }
308  }
309 
310  private:
311 
312  HashGridBox3<Item> *bound_;
313  HashGridBox3<Item> *cur_box_;
314  BoxIteratorPosition position_;
315  Position x_, y_, z_;
316  };
317 
318  friend class BoxIteratorTraits;
319 
324  typedef ForwardIterator
328 
331  {
332  return BoxIterator::begin(*this);
333  }
334 
337  {
338  return BoxIterator::end(*this);
339  }
340 
341 
343  typedef ConstForwardIterator
347 
350  {
351  return ConstBoxIterator::begin(*this);
352  }
353 
356  {
357  return ConstBoxIterator::end(*this);
358  }
359 
360  typedef typename std::forward_list<Item> DataContainer;
361 
362  typedef typename DataContainer::iterator DataIteratorPosition;
363 
365  {
366  public:
367 
369 
370  virtual ~DataIteratorTraits() {}
371 
373  : bound_(nullptr),
374  position_()
375  {
376  }
377 
379  : bound_((HashGridBox3 *)&box),
380  position_(bound_->data.begin())
381  {
382  }
383 
384  DataIteratorTraits(const DataIteratorTraits& traits, bool /* deep */ = true)
385  : bound_(traits.bound_),
386  position_(traits.position_)
387  {
388  }
389 
391  {
392  bound_ = traits.bound_;
393  position_ = traits.position_;
394  return *this;
395  }
396 
398  {
399  return bound_;
400  }
401 
402  const HashGridBox3* getContainer() const
403  {
404  return bound_;
405  }
406 
407  bool isSingular() const
408  {
409  return !bound_;
410  }
411 
413  {
414  return position_;
415  }
416 
418  {
419  return position_;
420  }
421 
422  bool operator == (const DataIteratorTraits &traits) const
423  {
424  return (position_ == traits.position_);
425  }
426 
427  bool operator != (const DataIteratorTraits &traits) const
428  {
429  return (position_ != traits.position_);
430  }
431 
432  bool isValid() const
433  {
434  return (bound_ && position_ != bound_->data.end());
435  }
436 
437  void invalidate()
438  {
439  bound_ = nullptr;
440  position_ = bound_->data.end();
441  }
442 
443  void toBegin()
444  {
445  position_ = bound_->data.begin();
446  }
447 
448  bool isBegin() const
449  {
450  return (position_ == bound_->data.begin());
451  }
452 
453  void toEnd()
454  {
455  position_ = bound_->data.end();
456  }
457 
458  bool isEnd() const
459  {
460  return (position_ == bound_->data.end());
461  }
462 
463  Item& getData()
464  {
465  return *position_;
466  }
467 
468  const Item& getData() const
469  {
470  return *position_;
471  }
472 
473  void forward()
474  {
475  ++position_;
476  }
477 
478  private:
479 
480  HashGridBox3<Item>* bound_;
481  DataIteratorPosition position_;
482  };
483 
484  friend class DataIteratorTraits;
485 
489  typedef ForwardIterator
490  <HashGridBox3<Item>, Item,
493 
496  {
497  return DataIterator::begin(*this);
498  }
499 
502  {
503  return DataIterator::end(*this);
504  }
505 
506 
510  typedef ConstForwardIterator
511  <HashGridBox3<Item>, Item,
514 
517  {
518  return ConstDataIterator::begin(*this);
519  }
520 
523  {
524  return ConstDataIterator::end(*this);
525  }
526 
528 
530 
532  };
533 
534  template<typename Item>
536  : parent(p)
537  {
538  }
539 
540  template<typename Item>
542  {
543  data.clear();
544  }
545 
546  template<typename Item>
547  BALL_INLINE
549  {
550  clear();
551  }
552 
553  template<typename Item>
555  {
556  parent = p;
557  }
558 
559  template<typename Item>
562  {
563  parent->getIndices(*this, x, y, z);
564  }
565 
566  template<typename Item>
567  Item* HashGridBox3<Item>::find(const Item& item)
568  {
569  DataIteratorPosition found = std::find(data.begin(), data.end(), item);
570 
571  if (found != data.end())
572  {
573  return &(*found);
574  }
575 
576  return nullptr;
577  }
578 
579  template<typename Item>
580  BALL_INLINE
581  const Item* HashGridBox3<Item>::find(const Item& item) const
582  {
583  return const_cast<HashGridBox3*>(this)->find(item);
584  }
585 
586  template<typename Item>
588  {
589  return std::distance(data.begin(), data.end());
590  }
591 
592  template<typename Item>
593  BALL_INLINE
594  void HashGridBox3<Item>::insert(const Item& item)
595  {
596  data.push_front(item);
597  }
598 
599  template<typename Item>
600  bool HashGridBox3<Item>::remove(const Item& item)
601  {
602  DataIteratorPosition pos = std::adjacent_find(data.before_begin(), data.end(),
603  [&](const Item&, const Item& next){ return next == item; });
604 
605  if (pos != data.end())
606  {
607  data.erase_after(pos);
608  return true;
609  }
610 
611  return false;
612  }
613 
614  template<typename Item>
615  bool HashGridBox3<Item>::removeAll(const Item& item)
616  {
617  data.remove(item);
618 
619  return true;
620  }
621 
622  template <typename Item>
623  BALL_INLINE
625  {
626  visitor.visit(*this);
627  }
628 
629  template<typename Item>
631  {
632  return (data == box.data);
633  }
634 
635  template<typename Item>
636  BALL_INLINE
638  {
639  return !(*this == box);
640  }
641 
642  template<typename Item>
643  BALL_INLINE
644  bool HashGridBox3<Item>::has(const Item& item) const
645  {
646  return (std::find(data.begin(), data.end(), item) != data.end());
647  }
648 
649  template<typename Item>
650  BALL_INLINE
652  {
653  return data.empty();
654  }
655 
656  template<typename Item>
658  {
659  // this is no longer required...
660  return true;
661  }
662 
663  template<typename Item>
664  void HashGridBox3<Item>::dump(std::ostream& s, Size depth) const
665  {
667 
668  BALL_DUMP_DEPTH(s, depth);
669 
670  BALL_DUMP_DEPTH(s, depth);
671  s << " size: " << getSize() << std::endl;
672 
673  BALL_DUMP_DEPTH(s, depth);
674  s << " data:" << std::endl;
675  for(const Item& e: data)
676  {
677  BALL_DUMP_DEPTH(s, depth);
678  s << " " << e << std::endl;
679  }
680 
682  }
683 
684  template <typename Item>
686  {
687  if (!processor.start())
688  {
689  return false;
690  }
691 
692  Processor::Result result;
693 
694  for(Item& e: data)
695  {
696  result = processor(e);
697 
698  if (result <= Processor::BREAK)
699  {
700  return result == Processor::BREAK;
701  }
702  }
703 
704  return processor.finish();
705  }
706 
707  template <typename Item>
709  {
710  if (!processor.start())
711  {
712  return false;
713  }
714 
715  Processor::Result result;
716 
717  for (BoxIterator it = beginBox(); +it; ++it)
718  {
719  result = processor(*it);
720 
721  if (result <= Processor::BREAK)
722  {
723  return result == Processor::BREAK;
724  }
725  }
726 
727  return processor.finish();
728  }
729 
753  template <typename Item>
754  class HashGrid3
755  {
756  public:
757 
759 
760 
763 
764 
766 
784  HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y,
785  Size dimension_z, float spacing_x, float spacing_y, float spacing_z);
786 
793  HashGrid3(const Vector3& origin, Size dimension_x, Size dimension_y,
794  Size dimension_z, float spacing);
795 
805  HashGrid3(const Vector3& origin, const Vector3& size, float spacing);
806 
808  HashGrid3(const HashGrid3& grid, bool deep = true);
809 
811  virtual ~HashGrid3();
812 
814  virtual void clear();
815 
818 
820  void clear(const Vector3 &vector);
821 
823  void destroy();
824 
827 
829  void destroy(const Vector3& vector);
830 
832 
835 
837  void set(const Vector3& origin, const Vector3& unit,
838  Size dimension_x, Size dimension_y, Size dimension_z);
839 
841  void set(const Vector3& origin, float unit, Size size);
842 
844  void set(const HashGrid3& grid, bool deep = true);
845 
847  const HashGrid3& operator = (const HashGrid3& grid);
848 
850  void get(Vector3& origin, Vector3& unit, Size& dimension_x, Size& dimension_y, Size& dimension_z) const;
851 
853  void get(HashGrid3& grid, bool deep = true) const;
854 
856 
859 
862 
864  Size getSize() const;
865 
868 
870  const Vector3& getOrigin() const;
871 
874 
876  const Vector3& getUnit() const;
877 
879  Size getSizeX() const;
880 
882  Size getSizeY() const;
883 
885  Size getSizeZ() const;
886 
889 
891  const HashGridBox3<Item>* getBox(Position x, Position y, Position z) const;
892 
894  HashGridBox3<Item>* getBox(const Vector3& vector);
895 
897  const HashGridBox3<Item>* getBox(const Vector3 &vector) const;
898 
900  bool getIndices(const HashGridBox3<Item>& box,
901  Position& x, Position& y, Position& z) const;
902 
904  void insert(Position x, Position y, Position z, const Item& item);
905 
907  void insert(const Vector3& vector, const Item& item);
908 
910  bool remove(Position x, Position y, Position z, const Item& item);
911 
913  bool remove(const Vector3& vector, const Item& item);
914 
916 
919 
921  void host(Visitor<HashGrid3>& visitor);
922 
924 
927 
929  bool operator == (const HashGrid3& grid) const;
930 
932  bool operator != (const HashGrid3& grid) const;
933 
935  bool isEmpty() const;
936 
938 
941 
943  virtual bool isValid() const;
944 
946  virtual void dump(std::ostream& s = std::cout, Size depth = 0) const;
947 
949 
953 
955  bool apply(UnaryProcessor<Item> &processor);
956 
958  bool apply(UnaryProcessor< HashGridBox3<Item> > &processor);
959 
963  const Item* getClosestItem(const Vector3& point, Size distance) const;
964 
971  static float calculateMinSpacing(LongIndex memory, const Vector3& size);
972 
974 
977 
979 
981  {
982  public:
983 
985 
986  virtual ~BoxIteratorTraits() {}
987 
989  : bound_(nullptr),
990  position_(0)
991  {
992  }
993 
995  : bound_((HashGrid3 *)&grid),
996  position_(0)
997  {
998  }
999 
1000  BoxIteratorTraits(const BoxIteratorTraits& traits, bool /* deep */ = true)
1001  : bound_(traits.bound_),
1002  position_(traits.position_)
1003  {
1004  }
1005 
1007  {
1008  bound_ = traits.bound_;
1009  position_ = traits.position_;
1010  return *this;
1011  }
1012 
1014  {
1015  return bound_;
1016  }
1017 
1018  const HashGrid3* getContainer() const
1019  {
1020  return bound_;
1021  }
1022 
1023  bool isSingular() const
1024  {
1025  return !bound_;
1026  }
1027 
1029  {
1030  return position_;
1031  }
1032 
1034  {
1035  return position_;
1036  }
1037 
1038  bool operator == (const BoxIteratorTraits& traits) const
1039  {
1040  return (position_ == traits.position_);
1041  }
1042 
1043  bool operator != (const BoxIteratorTraits& traits) const
1044  {
1045  return (position_ != traits.position_);
1046  }
1047 
1048  bool isValid() const
1049  {
1050  return (bound_ && position_ < bound_->getSize());
1051  }
1052 
1053  void invalidate()
1054  {
1055  bound_ = nullptr;
1056  position_ = bound_->getSize()+1;
1057  }
1058 
1059  void toBegin()
1060  {
1061  position_ = 0;
1062  }
1063 
1064  bool isBegin() const
1065  {
1066  return (position_ == 0);
1067  }
1068 
1069  void toEnd()
1070  {
1071  position_ = bound_->getSize();
1072  }
1073 
1074  bool isEnd() const
1075  {
1076  return (position_ == bound_->getSize());
1077  }
1078 
1080  {
1081  return bound_->box_[position_];
1082  }
1083 
1085  {
1086  return bound_->box_[position_];
1087  }
1088 
1089  void forward()
1090  {
1091  ++position_;
1092  }
1093 
1094  private:
1095 
1096  HashGrid3<Item>* bound_;
1097  BoxIteratorPosition position_;
1098  };
1099 
1100  friend class BoxIteratorTraits;
1101 
1103  typedef ForwardIterator
1107 
1110  {
1111  return BoxIterator::begin(*this);
1112  }
1113 
1116  {
1117  return BoxIterator::end(*this);
1118  }
1119 
1120 
1122  typedef ConstForwardIterator
1126 
1129  {
1130  return ConstBoxIterator::begin(*this);
1131  }
1132 
1135  {
1136  return ConstBoxIterator::end(*this);
1137  }
1138 
1140 
1141  private:
1142 
1143  //_
1144  Index getIndex_(const HashGridBox3<Item>& box) const;
1145 
1146  //_
1147  Vector3 origin_;
1148  //_
1149  Vector3 unit_;
1150  //_
1151  Size dimension_x_;
1152  //_
1153  Size dimension_y_;
1154  //_
1155  Size dimension_z_;
1156  //_
1157  vector<HashGridBox3<Item> > box_;
1158  };
1159 
1160 
1162 
1163 
1164  template <typename Item>
1166  : origin_(0,0,0),
1167  unit_(0,0,0),
1168  dimension_x_(0),
1169  dimension_y_(0),
1170  dimension_z_(0)
1171  {
1172  }
1173 
1174  template <typename Item>
1176  (const Vector3 &originvector,
1177  Size dimension_x, Size dimension_y, Size dimension_z,
1178  float spacing_x, float spacing_y, float spacing_z)
1179  : origin_(originvector),
1180  unit_(spacing_x, spacing_y, spacing_z),
1181  dimension_x_(dimension_x),
1182  dimension_y_(dimension_y),
1183  dimension_z_(dimension_z),
1184  box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this))
1185  {
1186  }
1187 
1188  template <typename Item>
1190  (const Vector3& origin,
1191  Size dimension_x, Size dimension_y, Size dimension_z, float spacing)
1192  : origin_(origin),
1193  unit_(spacing, spacing, spacing),
1194  dimension_x_(dimension_x),
1195  dimension_y_(dimension_y),
1196  dimension_z_(dimension_z),
1197  box_(dimension_x * dimension_y * dimension_z, HashGridBox3<Item>(this))
1198  {
1199  }
1200 
1201  // this constructor creates a linear array of HashGridBox3 objects.
1202  template <typename Item>
1203  HashGrid3<Item>::HashGrid3(const Vector3& origin, const Vector3& size,
1204  float spacing)
1205  : origin_(origin),
1206  unit_(spacing, spacing, spacing),
1207  dimension_x_((Size)(size.x / spacing + 1.0)),
1208  dimension_y_((Size)(size.y / spacing + 1.0)),
1209  dimension_z_((Size)(size.z / spacing + 1.0)),
1210  box_(dimension_x_ * dimension_y_ * dimension_z_, HashGridBox3<Item>(this))
1211  {
1212  }
1213 
1214  template <typename Item>
1216  {
1217  set(grid, deep);
1218  }
1219 
1220  template <typename Item>
1222  {
1223  }
1224 
1225  template <typename Item>
1227  {
1228  for(HashGridBox3<Item>& e: box_)
1229  {
1230  e.clear();
1231  }
1232  }
1233 
1234  template <typename Item>
1235  BALL_INLINE
1237  {
1238  HashGridBox3<Item>* box = getBox(x, y, z);
1239 
1240  if (box)
1241  {
1242  box->clear();
1243  }
1244  }
1245 
1246  template <typename Item>
1247  BALL_INLINE
1248  void HashGrid3<Item>::clear(const Vector3& vector)
1249  {
1250  HashGridBox3<Item>* box = getBox(vector);
1251 
1252  if (box)
1253  {
1254  box->clear();
1255  }
1256  }
1257 
1258  template <typename Item>
1259  BALL_INLINE
1261  {
1262  clear();
1263  }
1264 
1265  template <typename Item>
1266  BALL_INLINE
1268  {
1269  clear(x, y, z);
1270  }
1271 
1272  template <typename Item>
1273  BALL_INLINE
1274  void HashGrid3<Item>::destroy(const Vector3 &vector)
1275  {
1276  clear(vector);
1277  }
1278 
1279  template <typename Item>
1281  (const Vector3& origin, const Vector3& unit,
1282  Size dimension_x, Size dimension_y, Size dimension_z)
1283  {
1284  origin_.set(origin);
1285  unit_.set(unit);
1286  dimension_x_ = dimension_x;
1287  dimension_y_ = dimension_y;
1288  dimension_z_ = dimension_z;
1289  box_.assign(getSize(), HashGridBox3<Item>(this));
1290  }
1291 
1292  template <typename Item>
1293  void HashGrid3<Item>::set(const Vector3& origin, float unit, Size size)
1294  {
1295  origin_.set(origin);
1296  unit_.set(unit, unit, unit);
1297  dimension_x_ = size;
1298  dimension_y_ = size;
1299  dimension_z_ = size;
1300  box_.assign(getSize(), HashGridBox3<Item>(this));
1301  }
1302 
1303  template <typename Item>
1304  void HashGrid3<Item>::set(const HashGrid3<Item>& grid, bool /* deep */)
1305  {
1306  origin_.set(grid.origin_);
1307  unit_.set(grid.unit_);
1308  dimension_x_ = grid.dimension_x_;
1309  dimension_y_ = grid.dimension_y_;
1310  dimension_z_ = grid.dimension_z_;
1311  box_ = grid.box_;
1312 
1313  for(HashGridBox3<Item>& e: box_)
1314  {
1315  e.setParent(this);
1316  }
1317  }
1318 
1319  template <typename Item>
1320  BALL_INLINE
1322  {
1323  set(grid);
1324 
1325  return *this;
1326  }
1327 
1328  template <typename Item>
1329  BALL_INLINE
1330  void HashGrid3<Item>::get(Vector3 &origin, Vector3 &unit, Size& dimension_x, Size& dimension_y, Size& dimension_z) const
1331  {
1332  origin.set(origin_);
1333  unit.set(unit_);
1334  dimension_x = dimension_x_;
1335  dimension_y = dimension_y_;
1336  dimension_z = dimension_z_;
1337  }
1338 
1339  template <typename Item>
1340  BALL_INLINE void
1341  HashGrid3<Item>::get(HashGrid3<Item> &grid, bool deep) const
1342  {
1343  grid.set(*this, deep);
1344  }
1345 
1346  template <typename Item>
1347  Size
1349  {
1350  return std::count_if(box_.begin(), box_.end(),
1351  std::not1(std::mem_fun_ref(&HashGridBox3<Item>::isEmpty))
1352  );
1353  }
1354 
1355  template <typename Item>
1356  BALL_INLINE
1358  {
1359  return (dimension_x_ * dimension_y_ * dimension_z_);
1360  }
1361 
1362  template <typename Item>
1363  BALL_INLINE
1365  {
1366  return origin_;
1367  }
1368 
1369  template <typename Item>
1370  BALL_INLINE
1372  {
1373  return origin_;
1374  }
1375 
1376  template <typename Item>
1377  BALL_INLINE
1379  {
1380  return unit_;
1381  }
1382 
1383  template <typename Item>
1384  BALL_INLINE
1386  {
1387  return unit_;
1388  }
1389 
1390  template <typename Item>
1391  BALL_INLINE
1393  {
1394  return dimension_x_;
1395  }
1396 
1397  template <typename Item>
1398  BALL_INLINE
1400  {
1401  return dimension_y_;
1402  }
1403 
1404  template <typename Item>
1405  BALL_INLINE
1407  {
1408  return dimension_z_;
1409  }
1410 
1411  template <typename Item>
1412  const Item* HashGrid3<Item>::getClosestItem(const Vector3& point, Size dist) const
1413  {
1414  const HashGridBox3<Item>* box = getBox(point);
1415  if (!box) return 0;
1416 
1417  Position x, y, z;
1418  getIndices(*box, x, y, z);
1419 
1420  const Item* item = 0;
1421  float distance = std::numeric_limits<float>::max();
1422 
1423  // iterator over neighbour boxes
1424  for (Index xi = -(Index)dist; xi <= (Index)dist; xi++)
1425  {
1426  const Index xn = x + xi;
1427  for (Index yi = -(Index)dist; yi <= (Index)dist; yi++)
1428  {
1429  const Index yn = y + yi;
1430  for (Index zi = -(Index)dist; zi <= (Index)dist; zi++)
1431  {
1432  // iterate over all data items
1433  const HashGridBox3<Item>* const box_ptr = getBox(xn, yn, z+zi);
1434  if (box_ptr != 0 && !box_ptr->isEmpty())
1435  {
1436  typename HashGridBox3<Item>::ConstDataIterator hit = box_ptr->beginData();
1437  for (;hit != box_ptr->endData(); hit++)
1438  {
1439  const float new_dist = ((*hit)->getPosition() - point).getSquareLength();
1440  if (new_dist < distance)
1441  {
1442  item = &*hit;
1443  distance = new_dist;
1444  }
1445  }
1446  }
1447  }
1448  }
1449  }
1450 
1451  return item;
1452  }
1453 
1454  template <typename Item>
1455  BALL_INLINE
1457  {
1458  LongSize memory_for_box = sizeof(HashGridBox3<Item>) + sizeof(HashGridBox3<Item>*);
1459  LongSize nr_boxes =(LongSize)floor((float)(memory / memory_for_box));
1460 
1461  return pow((double)((size.x * size.y * size.z) / nr_boxes), (double)(1.0 / 3.0));
1462  }
1463 
1464  template <typename Item>
1465  BALL_INLINE
1467  {
1468  if (x >= (Position)dimension_x_ ||
1469  y >= (Position)dimension_y_ ||
1470  z >= (Position)dimension_z_)
1471  {
1472  return 0;
1473  }
1474  else
1475  {
1476  return &(box_[x * dimension_y_ * dimension_z_ + y * dimension_z_ + z]);
1477  }
1478  }
1479 
1480  template <typename Item>
1481  BALL_INLINE
1483  {
1484  return ((HashGrid3*)this)->getBox(x, y, z);
1485  }
1486 
1487  template <typename Item>
1488  BALL_INLINE
1490  {
1491  float x = (vector.x - origin_.x) / unit_.x;
1492  float y = (vector.y - origin_.y) / unit_.y;
1493  float z = (vector.z - origin_.z) / unit_.z;
1494 
1495  // workaround for MSVC 7, dont change this !!!
1496  Index x1 = (Index) Maths::floor(x);
1497  Index y1 = (Index) Maths::floor(y);
1498  Index z1 = (Index) Maths::floor(z);
1499 
1500  return getBox(x1, y1, z1);
1501  }
1502 
1503  template <typename Item>
1504  BALL_INLINE
1506  {
1507  return ((HashGrid3 *)this)->getBox(vector);
1508  }
1509 
1510  template <typename Item>
1511  BALL_INLINE
1513  (const HashGridBox3<Item>& box,
1514  Position& x, Position& y, Position& z) const
1515  {
1516  Index index = getIndex_(box);
1517 
1518  if (index == INVALID_Index)
1519  {
1520  x = y = z = INVALID_Position;
1521 
1522  return false;
1523  }
1524 
1525  x = index / (dimension_y_ * dimension_z_);
1526  index -= x * dimension_y_ * dimension_z_;
1527  y = index / dimension_z_;
1528  z = index - y * dimension_z_;
1529 
1530  return true;
1531  }
1532 
1533  template <typename Item>
1534  BALL_INLINE
1536  (Position x, Position y, Position z, const Item& item)
1537  {
1538  HashGridBox3<Item>* box = getBox(x, y, z);
1539 
1540  if (box)
1541  {
1542  box->insert(item);
1543  }
1544  }
1545 
1546  template <typename Item>
1547  BALL_INLINE
1548  void HashGrid3<Item>::insert(const Vector3& vector, const Item& item)
1549  {
1550  HashGridBox3<Item> *box = getBox(vector);
1551 
1552  if (box)
1553  {
1554  box->insert(item);
1555  }
1556  }
1557 
1558  template <typename Item>
1559  BALL_INLINE
1560  bool HashGrid3<Item>::remove(Position x, Position y, Position z, const Item& item)
1561  {
1562  HashGridBox3<Item>* box = getBox(x, y, z);
1563 
1564  return box ? box->remove(item) : false;
1565  }
1566 
1567  template <typename Item>
1568  BALL_INLINE
1569  bool HashGrid3<Item>::remove(const Vector3& vector, const Item& item)
1570  {
1571  HashGridBox3<Item>* box = getBox(vector);
1572 
1573  return box ? box->remove(item) : false;
1574  }
1575 
1576  template <typename Item>
1577  BALL_INLINE
1579  {
1580  visitor.visit(*this);
1581  }
1582 
1583  template <typename Item>
1584  BALL_INLINE
1586  {
1587  if (getSize() != grid.getSize()
1588  || origin_ != grid.origin_
1589  || unit_ != grid.unit_
1590  || dimension_x_ != grid.dimension_x_
1591  || dimension_y_ != grid.dimension_y_
1592  || dimension_z_ != grid.dimension_z_)
1593  {
1594  return false;
1595  }
1596 
1597  return box_ == grid.box_;
1598  }
1599 
1600  template <typename Item>
1601  BALL_INLINE
1603  {
1604  return !(*this == grid);
1605  }
1606 
1607  template <typename Item>
1608  BALL_INLINE
1610  {
1611  return (getSize() == 0);
1612  }
1613 
1614  template <typename Item>
1616  {
1617  for(const HashGridBox3<Item>& e: box_)
1618  {
1619  if(!e.isValid()) return false;
1620  }
1621  return true;
1622  }
1623 
1624  template <typename Item>
1625  void HashGrid3<Item>::dump(std::ostream& s, Size depth) const
1626  {
1628 
1629  BALL_DUMP_DEPTH(s, depth);
1630 
1631  BALL_DUMP_DEPTH(s, depth);
1632  s << " origin: " << origin_ << std::endl;
1633 
1634  BALL_DUMP_DEPTH(s, depth);
1635  s << " unit: " << unit_.z << std::endl;
1636 
1637  BALL_DUMP_DEPTH(s, depth);
1638  s << " dimension: " << dimension_x_ << " "
1639  << dimension_y_ << " "
1640  << dimension_z_ << std::endl;
1641 
1642  Size size = getSize();
1643  BALL_DUMP_DEPTH(s, depth);
1644  s << " size: " << size << std::endl;
1645 
1646  BALL_DUMP_DEPTH(s, depth);
1647  s << " non empty boxes: " << countNonEmptyBoxes() << std::endl;
1648 
1649  BALL_DUMP_DEPTH(s, depth);
1650  s << " boxes:" << std::endl;
1651  Position x, y, z;
1652  for (Position index = 0; index < (Position)size; ++index)
1653  {
1654  BALL_DUMP_DEPTH(s, depth);
1655  getIndices(box_[index], x, y, z);
1656  s << " " << index << ". box: ("
1657  << x << ',' << y << ',' << z << ')' << std::endl;
1658  box_[index].dump(s, 1);
1659  }
1660 
1661  BALL_DUMP_DEPTH(s, depth);
1662  s << " non-empty boxes:" << std::endl;
1663 
1664  for (Position i=0; i<27; ++i)
1665  {
1666  if (!box_[i].isEmpty())
1667  s << " " << getIndex_(box_[i]) << std::endl;
1668  }
1670  }
1671 
1672  template <typename Item>
1674  {
1675  if (!processor.start())
1676  {
1677  return false;
1678  }
1679  Processor::Result result;
1680 
1681  for (Position i=0; i<27; ++i)
1682  {
1683  HashGridBox3<Item>* box = &box_[i];
1684  for (typename HashGridBox3<Item>::DataIterator *item = box->beginData(); +item; ++item)
1685  {
1686  result = processor(*item);
1687 
1688  if (result <= Processor::BREAK)
1689  {
1690  return result == Processor::BREAK;
1691  }
1692  }
1693  }
1694 
1695  return processor->finish();
1696  }
1697 
1698  template <typename Item>
1700  {
1701  if (!processor.start())
1702  {
1703  return false;
1704  }
1705 
1706  Processor::Result result;
1707 
1708  for (Position i=0; i<27; ++i)
1709  {
1710  HashGridBox3<Item>* box = &box_[i];
1711  result = processor(*box);
1712 
1713  if (result <= Processor::BREAK)
1714  {
1715  return result == Processor::BREAK;
1716  }
1717  }
1718 
1719  return processor->finish();
1720  }
1721 
1722  template <typename Item>
1723  BALL_INLINE
1725  {
1726  if ((&box < &box_[0]) || (&box - &box_[0] >= getSize()))
1727  {
1728  return INVALID_Index;
1729  }
1730  else
1731  {
1732  return (Index)(&box - &box_[0]);
1733  }
1734  }
1735 } // namespace BALL
1736 
1737 #endif // BALL_DATATYPE_HASHGRID_H
#define BALL_CREATE(name)
Definition: create.h:62
#define BALL_INLINE
Definition: debug.h:15
#define BALL_DUMP_STREAM_PREFIX(os)
Definition: macros.h:391
#define BALL_DUMP_STREAM_SUFFIX(os)
Definition: macros.h:395
#define BALL_DUMP_DEPTH(os, depth)
Definition: macros.h:390
#define BALL_CREATE_DEEP(name)
Definition: create.h:26
Definition: constants.h:13
static const Position INVALID_Position
BALL_ULONG64_TYPE LongSize
static const Index INVALID_Index
BALL_SIZE_TYPE Position
BALL_LONG64_TYPE LongIndex
BALL_INDEX_TYPE Index
const signed char BALL_EXPORT neighbour_table_[27][3]
T max(const T &a, const T &b)
Definition: MATHS/common.h:75
long floor(const T &t)
Definition: MATHS/common.h:284
static ConstForwardIterator begin(const Container &container)
static ConstForwardIterator end(const Container &container)
static ForwardIterator begin(const Container &container)
static ForwardIterator end(const Container &container)
virtual bool start()
Definition: processor.h:92
virtual bool finish()
Definition: processor.h:99
Three-dimensional Hash Grid Class.
Definition: hashGrid.h:755
void destroy()
Destroys the grid (obsolete, only calls clear())
Definition: hashGrid.h:1260
bool isEmpty() const
Tests, whether this is empty.
Definition: hashGrid.h:1609
void set(const Vector3 &origin, const Vector3 &unit, Size dimension_x, Size dimension_y, Size dimension_z)
assigns the content of a hash grid (obsolete)
Definition: hashGrid.h:1281
bool operator==(const HashGrid3 &grid) const
Equality operator.
Definition: hashGrid.h:1585
bool getIndices(const HashGridBox3< Item > &box, Position &x, Position &y, Position &z) const
Get the position indices of a HashGridBox3.
Definition: hashGrid.h:1513
virtual void dump(std::ostream &s=std::cout, Size depth=0) const
Dump the contents of a HashGrid3 to a stream.
Definition: hashGrid.h:1625
static float calculateMinSpacing(LongIndex memory, const Vector3 &size)
Definition: hashGrid.h:1456
Vector3 & getUnit()
Returns the unit of the grid.
Definition: hashGrid.h:1378
Vector3 & getOrigin()
Returns the origin of the grid.
Definition: hashGrid.h:1364
ForwardIterator< HashGrid3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > BoxIterator
Definition: hashGrid.h:1106
bool remove(Position x, Position y, Position z, const Item &item)
Remove an item from position (x, y ,z)
Definition: hashGrid.h:1560
virtual bool isValid() const
Validity check.
Definition: hashGrid.h:1615
bool operator!=(const HashGrid3 &grid) const
Inequality operator.
Definition: hashGrid.h:1602
BoxIterator beginBox()
Definition: hashGrid.h:1109
virtual void clear()
Clears the whole grid.
Definition: hashGrid.h:1226
void insert(Position x, Position y, Position z, const Item &item)
Insert an item at position (x, y, z)
Definition: hashGrid.h:1536
virtual ~HashGrid3()
Destructor.
Definition: hashGrid.h:1221
Size countNonEmptyBoxes() const
Counts the non-empty boxes of a grid.
Definition: hashGrid.h:1348
bool apply(UnaryProcessor< Item > &processor)
Definition: hashGrid.h:1673
ConstForwardIterator< HashGrid3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > ConstBoxIterator
Definition: hashGrid.h:1125
friend class BoxIteratorTraits
Definition: hashGrid.h:1100
const HashGrid3 & operator=(const HashGrid3 &grid)
Assignment operator.
Definition: hashGrid.h:1321
HashGridBox3< Item > * getBox(Position x, Position y, Position z)
Return the HashGridBox3 at position (x, y, z)
Definition: hashGrid.h:1466
BoxIterator endBox()
Definition: hashGrid.h:1115
void get(Vector3 &origin, Vector3 &unit, Size &dimension_x, Size &dimension_y, Size &dimension_z) const
Definition: hashGrid.h:1330
Size getSizeY() const
Get the y dimension of the grid.
Definition: hashGrid.h:1399
Size getSizeZ() const
Get the z dimension of the grid.
Definition: hashGrid.h:1406
ConstBoxIterator endBox() const
Definition: hashGrid.h:1134
Position BoxIteratorPosition
Definition: hashGrid.h:978
Size getSize() const
Returns the size of a grid, i. e. ?????
Definition: hashGrid.h:1357
ConstBoxIterator beginBox() const
Definition: hashGrid.h:1128
const Item * getClosestItem(const Vector3 &point, Size distance) const
Definition: hashGrid.h:1412
void host(Visitor< HashGrid3 > &visitor)
Definition: hashGrid.h:1578
HashGrid3()
Default constructor.
Definition: hashGrid.h:1165
Size getSizeX() const
Get the x dimension of the grid.
Definition: hashGrid.h:1392
ConstDataIterator endData() const
Definition: hashGrid.h:522
bool removeAll(const Item &item)
Definition: hashGrid.h:615
bool apply(UnaryProcessor< Item > &processor)
Definition: hashGrid.h:685
ConstForwardIterator< HashGridBox3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > ConstBoxIterator
This is the const version of BoxIterator .
Definition: hashGrid.h:346
ForwardIterator< HashGridBox3< Item >, Item, DataIteratorPosition, DataIteratorTraits > DataIterator
Definition: hashGrid.h:492
bool remove(const Item &item)
Definition: hashGrid.h:600
const Item * find(const Item &item) const
The const version of find()
Definition: hashGrid.h:581
friend class DataIteratorTraits
Definition: hashGrid.h:484
ConstBoxIterator endBox() const
get the last box
Definition: hashGrid.h:355
void dump(std::ostream &s=std::cout, Size depth=0) const
Definition: hashGrid.h:664
ConstForwardIterator< HashGridBox3< Item >, Item, DataIteratorPosition, DataIteratorTraits > ConstDataIterator
Definition: hashGrid.h:513
DataIterator beginData()
Definition: hashGrid.h:495
void host(Visitor< HashGridBox3 > &visitor)
Host method.
Definition: hashGrid.h:624
bool isValid() const
Definition: hashGrid.h:657
DataContainer data
Definition: hashGrid.h:531
DataIterator endData()
Definition: hashGrid.h:501
ConstBoxIterator beginBox() const
get the first box
Definition: hashGrid.h:349
HashGridBox3(HashGrid3< Item > *parent)
Default constructor.
Definition: hashGrid.h:535
void getIndices(Position &x, Position &y, Position &z)
Definition: hashGrid.h:561
bool has(const Item &item) const
Definition: hashGrid.h:644
Position BoxIteratorPosition
Definition: hashGrid.h:178
bool isEmpty() const
Definition: hashGrid.h:651
friend class BoxIteratorTraits
Definition: hashGrid.h:318
ForwardIterator< HashGridBox3< Item >, HashGridBox3< Item >, BoxIteratorPosition, BoxIteratorTraits > BoxIterator
Definition: hashGrid.h:327
Item * find(const Item &item)
Definition: hashGrid.h:567
DataContainer::iterator DataIteratorPosition
Definition: hashGrid.h:362
bool apply(UnaryProcessor< HashGridBox3< Item > > &processor)
Definition: hashGrid.h:708
BoxIterator endBox()
get the last box
Definition: hashGrid.h:336
void setParent(HashGrid3< Item > *p)
Definition: hashGrid.h:554
std::forward_list< Item > DataContainer
Definition: hashGrid.h:360
void clear()
Clears the grid box.
Definition: hashGrid.h:541
bool operator==(const HashGridBox3 &box) const
Equality operator.
Definition: hashGrid.h:630
HashGrid3< Item > * parent
Definition: hashGrid.h:529
BoxIterator beginBox()
get the first box
Definition: hashGrid.h:330
bool operator!=(const HashGridBox3 &box) const
Inequality operator.
Definition: hashGrid.h:637
Size getSize() const
Definition: hashGrid.h:587
ConstDataIterator beginData() const
Definition: hashGrid.h:516
void insert(const Item &item)
Definition: hashGrid.h:594
BoxIteratorTraits(const HashGridBox3 &box)
Definition: hashGrid.h:198
bool operator!=(const BoxIteratorTraits &traits) const
Definition: hashGrid.h:249
const HashGridBox3< Item > & getData() const
Definition: hashGrid.h:292
bool operator==(const BoxIteratorTraits &traits) const
Definition: hashGrid.h:244
const BoxIteratorPosition & getPosition() const
Definition: hashGrid.h:239
const HashGridBox3 * getContainer() const
Definition: hashGrid.h:224
HashGridBox3< Item > & getData()
Definition: hashGrid.h:287
BoxIteratorPosition & getPosition()
Definition: hashGrid.h:234
BoxIteratorTraits(const BoxIteratorTraits &traits, bool=true)
Definition: hashGrid.h:209
bool operator!=(const DataIteratorTraits &traits) const
Definition: hashGrid.h:427
DataIteratorTraits(const DataIteratorTraits &traits, bool=true)
Definition: hashGrid.h:384
DataIteratorTraits(const HashGridBox3 &box)
Definition: hashGrid.h:378
const DataIteratorTraits & operator=(const DataIteratorTraits &traits)
Definition: hashGrid.h:390
bool operator==(const DataIteratorTraits &traits) const
Definition: hashGrid.h:422
const DataIteratorPosition & getPosition() const
Definition: hashGrid.h:417
DataIteratorPosition & getPosition()
Definition: hashGrid.h:412
const HashGridBox3 * getContainer() const
Definition: hashGrid.h:402
const HashGrid3 * getContainer() const
Definition: hashGrid.h:1018
BoxIteratorPosition & getPosition()
Definition: hashGrid.h:1028
const BoxIteratorPosition & getPosition() const
Definition: hashGrid.h:1033
HashGridBox3< Item > & getData()
Definition: hashGrid.h:1079
const HashGridBox3< Item > & getData() const
Definition: hashGrid.h:1084
BoxIteratorTraits(const BoxIteratorTraits &traits, bool=true)
Definition: hashGrid.h:1000
BoxIteratorTraits(const HashGrid3 &grid)
Definition: hashGrid.h:994
void set(const T *ptr)
Definition: vector3.h:615
#define BALL_EXPORT
Definition: COMMON/global.h:50