KrisLibrary  1.0.0
GridSubdivision.h
1 #ifndef GEOMETRY_GRID_SUBDIVISION_H
2 #define GEOMETRY_GRID_SUBDIVISION_H
3 
4 #include <KrisLibrary/math/vector.h>
6 #include <KrisLibrary/utils/IntTuple.h>
7 #include <KrisLibrary/utils/IntTriple.h>
8 #include <list>
9 //this is needed for unordered_map compatibility across compilers / OSs
10 #include <KrisLibrary/utils/stl_tr1.h>
11 
12 namespace Geometry {
13 
14 using namespace Math;
15 using namespace Math3D;
16 
17 struct IndexHash
18 {
19  explicit IndexHash(size_t pow=257);
20  size_t operator () (const IntTriple& x) const;
21  size_t operator () (const std::vector<int>& x) const;
22  size_t pow;
23 };
24 
33 {
34 public:
35  typedef IntTriple Index;
36  typedef void* Value;
37  //called once per value in the query range, return false to stop enumerating
38  typedef bool (*QueryCallback)(void* value);
39 
40  explicit GridHash3D(Real h=1);
41  explicit GridHash3D(const Vector3& h);
42  size_t GetBucketCount() const { return buckets.bucket_count(); }
43  void SetBucketCount(size_t n) { buckets.rehash(n); }
44  Vector3 GetResolution() const;
46  void SetResolution(const Vector3& h);
48  void SetResolution(Real h);
50  void Set(const Index& i,void* data);
52  void* Get(const Index& i) const;
54  void* Erase(const Index& i);
56  bool Contains(const Index& i);
57  void Clear();
58  void Enumerate(std::vector<Value>& items) const;
59 
60  //returns the index of the point
61  void PointToIndex(const Vector3& p,Index& i) const;
62  //same, but with the local coordinates in the bucket [0,1]^n
63  void PointToIndex(const Vector3& p,Index& i,Vector3& u) const;
64  //returns the lower/upper corner of the bucket
65  void IndexBucketBounds(const Index& i,Vector3& bmin,Vector3& bmax) const;
66 
67  //returns the min/max indices of all occupied cells
68  void GetRange(Index& imin,Index& imax) const;
69  //returns the min/max bound of all occupied cells
70  void GetRange(Vector3& bmin,Vector3& bmax) const;
71 
72  //range imin to imax
73  bool IndexQuery(const Index& imin,const Index& imax,QueryCallback f) const;
74  //bounding box from bmin to bmax
75  bool BoxQuery(const Vector3& bmin,const Vector3& bmax,QueryCallback f) const;
76  //ball with center c, radius r
77  bool BallQuery(const Vector3& c,Real r,QueryCallback f) const;
78  //segment from a to b
79  bool SegmentQuery(const Vector3& a,const Vector3& b,QueryCallback f) const;
80 
81  //range imin to imax
82  void IndexItems(const Index& imin,const Index& imax,std::vector<Value>& items) const;
83  //bounding box from bmin to bmax
84  void BoxItems(const Vector3& bmin,const Vector3& bmax,std::vector<Value>& items) const;
85  //ball with center c, radius r
86  void BallItems(const Vector3& c,Real r,std::vector<Value>& items) const;
87  //segment from a to b
88  void SegmentItems(const Vector3& a,const Vector3& b,std::vector<Value>& items) const;
89 
90  Vector3 hinv;
91  typedef UNORDERED_MAP_TEMPLATE<Index,Value,IndexHash> HashTable;
92  HashTable buckets;
93 };
94 
99 {
100 public:
101  typedef IntTriple Index;
102  typedef std::vector<void*> ObjectSet;
103  //called once per object in the query range, return false to stop enumerating
104  typedef bool (*QueryCallback)(void* obj);
105 
106  explicit GridSubdivision3D(Real h=1);
107  explicit GridSubdivision3D(const Vector3& h);
108  size_t GetBucketCount() const { return buckets.bucket_count(); }
109  void SetBucketCount(size_t n) { buckets.rehash(n); }
110  //this doesn't work -- hash power can't currently be changed.
111  //void SetHashPower(size_t n) { buckets.hash_function().pow=n; }
113  void Insert(const Index& i,void* data);
115  bool Erase(const Index& i,void* data);
116  ObjectSet* GetObjectSet(const Index& i);
117  const ObjectSet* GetObjectSet(const Index& i) const;
118  void Clear();
119 
120  //returns the index of the point
121  void PointToIndex(const Vector3& p,Index& i) const;
122  //same, but with the local coordinates in the bucket [0,1]^n
123  void PointToIndex(const Vector3& p,Index& i,Vector3& u) const;
124  //returns the lower/upper corner of the bucket
125  void IndexBucketBounds(const Index& i,Vector3& bmin,Vector3& bmax) const;
126 
127  //returns the min/max indices of all occupied cells
128  void GetRange(Index& imin,Index& imax) const;
129  //returns the min/max bound of all occupied cells
130  void GetRange(Vector3& bmin,Vector3& bmax) const;
131 
132  //range imin to imax
133  bool IndexQuery(const Index& imin,const Index& imax,QueryCallback f) const;
134  //bounding box from bmin to bmax
135  bool BoxQuery(const Vector3& bmin,const Vector3& bmax,QueryCallback f) const;
136  //ball with center c, radius r
137  bool BallQuery(const Vector3& c,Real r,QueryCallback f) const;
138  //segment from a to b
139  bool SegmentQuery(const Vector3& a,const Vector3& b,QueryCallback f) const;
140 
141  //range imin to imax
142  void IndexItems(const Index& imin,const Index& imax,ObjectSet& objs) const;
143  //bounding box from bmin to bmax
144  void BoxItems(const Vector3& bmin,const Vector3& bmax,ObjectSet& objs) const;
145  //ball with center c, radius r
146  void BallItems(const Vector3& c,Real r,ObjectSet& objs) const;
147  //segment from a to b
148  void SegmentItems(const Vector3& a,const Vector3& b,ObjectSet& objs) const;
149 
150  Vector3 hinv;
151  typedef UNORDERED_MAP_TEMPLATE<Index,ObjectSet,IndexHash> HashTable;
152  HashTable buckets;
153 };
154 
155 
163 class GridHash
164 {
165 public:
166  typedef IntTuple Index;
167  typedef void* Value;
168  //called once per value in the query range, return false to stop enumerating
169  typedef bool (*QueryCallback)(void* value);
170 
171  explicit GridHash(int numDims,Real h=1);
172  explicit GridHash(const Vector& h);
173  size_t GetBucketCount() const { return buckets.bucket_count(); }
174  void SetBucketCount(size_t n) { buckets.rehash(n); }
175  Vector GetResolution() const;
177  void SetResolution(const Vector& h);
179  void SetResolution(Real h);
181  void Set(const Index& i,void* data);
183  void* Get(const Index& i) const;
185  void* Erase(const Index& i);
187  bool Contains(const Index& i);
188  void Clear();
189  void Enumerate(std::vector<Value>& items) const;
190 
191  //returns the index of the point
192  void PointToIndex(const Vector& p,Index& i) const;
193  //same, but with the local coordinates in the bucket [0,1]^n
194  void PointToIndex(const Vector& p,Index& i,Vector& u) const;
195  //returns the lower/upper corner of the bucket
196  void IndexBucketBounds(const Index& i,Vector& bmin,Vector& bmax) const;
197 
198  //returns the min/max indices of all occupied cells
199  void GetRange(Index& imin,Index& imax) const;
200  //returns the min/max bound of all occupied cells
201  void GetRange(Vector& bmin,Vector& bmax) const;
202 
203  //range imin to imax
204  bool IndexQuery(const Index& imin,const Index& imax,QueryCallback f) const;
205  //bounding box from bmin to bmax
206  bool BoxQuery(const Vector& bmin,const Vector& bmax,QueryCallback f) const;
207  //ball with center c, radius r
208  bool BallQuery(const Vector& c,Real r,QueryCallback f) const;
209  //segment from a to b
210  bool SegmentQuery(const Vector& a,const Vector& b,QueryCallback f) const;
211 
212  //range imin to imax
213  void IndexItems(const Index& imin,const Index& imax,std::vector<Value>& items) const;
214  //bounding box from bmin to bmax
215  void BoxItems(const Vector& bmin,const Vector& bmax,std::vector<Value>& items) const;
216  //ball with center c, radius r
217  void BallItems(const Vector& c,Real r,std::vector<Value>& items) const;
218  //segment from a to b
219  void SegmentItems(const Vector& a,const Vector& b,std::vector<Value>& items) const;
220 
221  Vector hinv;
222  typedef UNORDERED_MAP_TEMPLATE<Index,Value,IndexHash> HashTable;
223  HashTable buckets;
224 };
225 
226 
231 {
232 public:
233  typedef IntTuple Index;
234  typedef std::vector<void*> ObjectSet;
235  //called once per object in the query range, return false to stop enumerating
236  typedef bool (*QueryCallback)(void* obj);
237 
238  explicit GridSubdivision(int numDims,Real h=1);
239  explicit GridSubdivision(const Vector& h);
240  size_t GetBucketCount() const { return buckets.bucket_count(); }
241  void SetBucketCount(size_t n) { buckets.rehash(n); }
242  //this doesn't work -- hash power can't currently be changed.
243  //void SetHashPower(size_t n) { buckets.hash_function().pow=n; }
245  void Insert(const Index& i,void* data);
247  bool Erase(const Index& i,void* data);
248  ObjectSet* GetObjectSet(const Index& i);
249  const ObjectSet* GetObjectSet(const Index& i) const;
250  void Clear();
251 
252  //returns the index of the point
253  void PointToIndex(const Vector& p,Index& i) const;
254  //same, but with the local coordinates in the bucket [0,1]^n
255  void PointToIndex(const Vector& p,Index& i,Vector& u) const;
256  //returns the lower/upper corner of the bucket
257  void IndexBucketBounds(const Index& i,Vector& bmin,Vector& bmax) const;
258 
259  //returns the min/max indices of all occupied cells
260  void GetRange(Index& imin,Index& imax) const;
261  //returns the min/max bound of all occupied cells
262  void GetRange(Vector& bmin,Vector& bmax) const;
263 
264  //range imin to imax
265  bool IndexQuery(const Index& imin,const Index& imax,QueryCallback f) const;
266  //bounding box from bmin to bmax
267  bool BoxQuery(const Vector& bmin,const Vector& bmax,QueryCallback f) const;
268  //ball with center c, radius r
269  bool BallQuery(const Vector& c,Real r,QueryCallback f) const;
270  //segment from a to b
271  bool SegmentQuery(const Vector& a,const Vector& b,QueryCallback f) const;
272 
273  //range imin to imax
274  void IndexItems(const Index& imin,const Index& imax,ObjectSet& objs) const;
275  //bounding box from bmin to bmax
276  void BoxItems(const Vector& bmin,const Vector& bmax,ObjectSet& objs) const;
277  //ball with center c, radius r
278  void BallItems(const Vector& c,Real r,ObjectSet& objs) const;
279  //segment from a to b
280  void SegmentItems(const Vector& a,const Vector& b,ObjectSet& objs) const;
281 
282  Vector hinv;
283  typedef UNORDERED_MAP_TEMPLATE<Index,ObjectSet,IndexHash> HashTable;
284  HashTable buckets;
285 };
286 
287 
288 
289 } //namespace Geometry
290 
291 #endif
A lightweight integer 3-tuple class.
Definition: IntTriple.h:9
A grid containing objects (referenced by void pointers)
Definition: GridSubdivision.h:32
A 3D vector class.
Definition: math3d/primitives.h:136
An ND grid with a list of arbitrary objects (given by void pointers)
Definition: GridSubdivision.h:230
Class declarations for useful 3D math types.
An integer tuple class.
Definition: IntTuple.h:14
An ND grid containing objects (referenced by void pointers)
Definition: GridSubdivision.h:163
Definition: GridSubdivision.h:17
Contains all the definitions in the Math3D package.
Definition: AnyGeometry.h:13
Contains all definitions in the Math package.
Definition: WorkspaceBound.h:12
Contains all definitions in the Geometry package.
Definition: AnyGeometry.cpp:26
A grid with a list of arbitrary objects (given by void pointers)
Definition: GridSubdivision.h:98