Stellarium 0.13.0
StelSphericalIndex.hpp
1 /*
2  * Stellarium
3  * Copyright (C) 2009 Fabien Chereau
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA.
18  */
19 
20 #ifndef _STELSPHERICALINDEX_HPP_
21 #define _STELSPHERICALINDEX_HPP_
22 
23 #include "StelRegionObject.hpp"
24 
28 {
29 public:
30  StelSphericalIndex(int maxObjectsPerNode = 100, int maxLevel=7);
31  virtual ~StelSphericalIndex();
32 
34  void insert(StelRegionObjectP obj);
35 
37  template<class FuncObject> void processIntersectingRegions(const SphericalRegion* region, FuncObject& func) const
38  {
39  rootNode->processIntersectingRegions(region, func);
40  }
41 
43  template<class FuncObject> void processIntersectingPointInRegions(const SphericalRegion* region, FuncObject& func) const
44  {
45  rootNode->processIntersectingPointInRegions(region, func);
46  }
47 
49  template<class FuncObject> void processBoundingCapIntersectingRegions(const SphericalCap& cap, FuncObject& func) const
50  {
51  rootNode->processBoundingCapIntersectingRegions(cap, func);
52  }
53 
55  template<class FuncObject> void processContainedRegions(const SphericalRegion* region, FuncObject& func) const
56  {
57  rootNode->processContainedRegions(region, func);
58  }
59 
61  template<class FuncObject> void processAll(FuncObject& func) const
62  {
63  rootNode->processAll(func);
64  }
65 
67  void clear()
68  {
69  rootNode->clear();
70  }
71 
73  unsigned int count()
74  {
75  CountFunc func;
76  processAll<CountFunc>(func);
77  return func.nb;
78  }
79 
80 private:
81  struct CountFunc
82  {
83  CountFunc() : nb(0) {;}
84  void operator()(const StelRegionObject*)
85  {
86  ++nb;
87  }
88  unsigned int nb;
89  };
90 
92  struct NodeElem
93  {
94  NodeElem() {;}
95  NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
96  StelRegionObjectP obj;
97  SphericalCap cap;
98  };
99 
103  struct Node
104  {
105  virtual ~Node() {;}
106  QVector<NodeElem> elements;
107  QVector<Node> children;
108  SphericalConvexPolygon triangle;
110  virtual void split()
111  {
112  // Default implementation for HTM triangle more than level 0
113  Q_ASSERT(children.empty());
114  Q_ASSERT(triangle.getConvexContour().size() == 3);
115 
116  const Vec3d& c0 = triangle.getConvexContour().at(0);
117  const Vec3d& c1 = triangle.getConvexContour().at(1);
118  const Vec3d& c2 = triangle.getConvexContour().at(2);
119 
120  Q_ASSERT((c1^c0)*c2 >= 0.0);
121  Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
122  e0.normalize();
123  Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
124  e1.normalize();
125  Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
126  e2.normalize();
127 
128  children.resize(4);
129  children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
130  Q_ASSERT(children[0].triangle.checkValid());
131  children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
132  Q_ASSERT(children[1].triangle.checkValid());
133  children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
134  Q_ASSERT(children[2].triangle.checkValid());
135  children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
136  Q_ASSERT(children[3].triangle.checkValid());
137  }
138 
140  void clear()
141  {
142  elements.clear();
143  children.clear();
144  }
145  };
146 
149  class RootNode : public Node
150  {
151  public:
152  RootNode(int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel)
153  {
154  }
155 
156  virtual ~RootNode() {}
157 
159  virtual void split()
160  {
161  static const Vec3d vertice[6] =
162  {
163  Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
164  };
165 
166  static const int verticeIndice[8][3] =
167  {
168  {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
169  };
170 
171  // Create the 8 base triangles
172  Node node;
173  for (int i=0;i<8;++i)
174  {
175  node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
176  Q_ASSERT(node.triangle.checkValid());
177  children.append(node);
178  }
179  }
180 
182  void insert(const NodeElem& el, int level)
183  {
184  insert(*this, el, level);
185  }
186 
188  template<class FuncObject> void processIntersectingRegions(const SphericalRegion* region, FuncObject& func) const
189  {
190  processIntersectingRegions(*this, region, func);
191  }
192 
194  template<class FuncObject> void processIntersectingPointInRegions(const SphericalRegion* region, FuncObject& func) const
195  {
196  processIntersectingPointInRegions(*this, region, func);
197  }
198 
199  template<class FuncObject> void processBoundingCapIntersectingRegions(const SphericalCap& cap, FuncObject& func) const
200  {
201  processBoundingCapIntersectingRegions(*this, cap, func);
202  }
203 
205  template<class FuncObject> void processContainedRegions(const SphericalRegion* region, FuncObject& func) const
206  {
207  processContainedRegions(*this, region, func);
208  }
209 
211  template<class FuncObject> void processAll(FuncObject& func) const
212  {
213  processAll(*this, func);
214  }
215 
216  private:
218  void insert(Node& node, const NodeElem& el, int level)
219  {
220  if (node.children.isEmpty())
221  {
222  node.elements.append(el);
223  // If we have too many objects in the node, we split it.
224  if (level<maxLevel && node.elements.size() > maxObjectsPerNode)
225  {
226  node.split();
227  const QVector<NodeElem> nodeElems = node.elements;
228  node.elements.clear();
229  // Re-insert the elements
230  for (QVector<NodeElem>::ConstIterator iter = nodeElems.constBegin();iter != nodeElems.constEnd(); ++iter)
231  {
232  insert(node, *iter, level);
233  }
234  }
235  return;
236  }
237 
238  // If we have children and one of them contains the element, store it in a sub-level
239  for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
240  {
241  if (((SphericalRegion*)&(iter->triangle))->contains(el.obj->getRegion().data()))
242  {
243  insert(*iter, el, level+1);
244  return;
245  }
246  }
247  // Else store it here
248  node.elements.append(el);
249  }
250 
252  template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegion* region, FuncObject& func) const
253  {
254  foreach (const NodeElem& el, node.elements)
255  {
256  if (region->intersects(el.obj->getRegion().data()))
257  func(&(*el.obj));
258  }
259  foreach (const Node& child, node.children)
260  {
261  if (region->contains(child.triangle))
262  processAll(child, func);
263  else if (region->intersects(child.triangle))
264  processIntersectingRegions(child, region, func);
265  }
266  }
267 
269  template<class FuncObject> void processIntersectingPointInRegions(const Node& node, const SphericalRegion* region, FuncObject& func) const
270  {
271  foreach (const NodeElem& el, node.elements)
272  {
273  if (region->contains(el.obj->getPointInRegion()))
274  func(&(*el.obj));
275  }
276  foreach (const Node& child, node.children)
277  {
278  if (region->contains(child.triangle))
279  processAll(child, func);
280  else if (region->intersects(child.triangle))
281  processIntersectingPointInRegions(child, region, func);
282  }
283  }
284 
285  template<class FuncObject> void processBoundingCapIntersectingRegions(const Node& node, const SphericalCap& cap, FuncObject& func) const
286  {
287  foreach (const NodeElem& el, node.elements)
288  {
289  if (cap.intersects(el.cap))
290  func(&(*el.obj));
291  }
292  foreach (const Node& child, node.children)
293  {
294  if (cap.contains(child.triangle))
295  processAll(child, func);
296  else if (cap.intersects(child.triangle))
297  processBoundingCapIntersectingRegions(child, cap, func);
298  }
299  }
300 
302  template<class FuncObject> void processContainedRegions(const Node& node, const SphericalRegion* region, FuncObject& func) const
303  {
304  foreach (const NodeElem& el, node.elements)
305  {
306  if (region->contains(el.obj->getRegion().data()))
307  func(&(*el.obj));
308  }
309  foreach (const Node& child, node.children)
310  {
311  if (region->contains(child.triangle))
312  processAll(child, func);
313  else if (region->intersects(child.triangle))
314  processContainedRegions(child, region, func);
315  }
316  }
317 
319  template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
320  {
321  foreach (const NodeElem& el, node.elements)
322  func(&(*el.obj));
323  foreach (const Node& child, node.children)
324  processAll(child, func);
325  }
326 
328  int maxObjectsPerNode;
330  int maxLevel;
331  };
332 
334  int maxObjectsPerNode;
335 
336  RootNode* rootNode;
337 };
338 
339 #endif // _STELSPHERICALINDEX_HPP_
340 
341 
void processIntersectingRegions(const SphericalRegion *region, FuncObject &func) const
Process all the objects intersecting the given region using the passed function object.
Definition: StelSphericalIndex.hpp:37
void processAll(FuncObject &func) const
Process all the objects intersecting the given region using the passed function object.
Definition: StelSphericalIndex.hpp:61
unsigned int count()
Return the total number of elements in the container.
Definition: StelSphericalIndex.hpp:73
A SphericalCap is defined by a direction and an aperture.
Definition: StelSphereGeometry.hpp:273
void processIntersectingPointInRegions(const SphericalRegion *region, FuncObject &func) const
Process all the objects intersecting the given region using the passed function object.
Definition: StelSphericalIndex.hpp:43
void insert(StelRegionObjectP obj)
Insert the given object in the StelSphericalIndex.
void clear()
Remove all the elements in the container.
Definition: StelSphericalIndex.hpp:67
bool contains(const SphericalRegion *r) const
Returns whether a SphericalRegion is contained into this region.
A special case of SphericalPolygon for which the polygon is convex.
Definition: StelSphereGeometry.hpp:629
Abstract class defining a region of the sphere.
Definition: StelSphereGeometry.hpp:135
void processContainedRegions(const SphericalRegion *region, FuncObject &func) const
Process all the objects contained in the given region using the passed function object.
Definition: StelSphericalIndex.hpp:55
Container allowing to store and query SphericalRegion.
Definition: StelSphericalIndex.hpp:27
bool intersects(const SphericalRegion *r) const
Returns whether a SphericalRegion intersects with this region.
Simple abstract class defining basic methods implemented by all objects that need to be stored in a S...
Definition: StelRegionObject.hpp:28
void processBoundingCapIntersectingRegions(const SphericalCap &cap, FuncObject &func) const
Process all the objects intersecting the given region using the passed function object.
Definition: StelSphericalIndex.hpp:49