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.
void processAll(FuncObject &func) const
Process all the objects intersecting the given region using the passed function object.
unsigned int count()
Return the total number of elements in the container.
A SphericalCap is defined by a direction and an aperture.
void processIntersectingPointInRegions(const SphericalRegion *region, FuncObject &func) const
Process all the objects intersecting the given region using the passed function object.
void insert(StelRegionObjectP obj)
Insert the given object in the StelSphericalIndex.
void clear()
Remove all the elements in the container.
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.
Abstract class defining a region of the sphere.
void processContainedRegions(const SphericalRegion *region, FuncObject &func) const
Process all the objects contained in the given region using the passed function object.
Container allowing to store and query SphericalRegion.
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...
void processBoundingCapIntersectingRegions(const SphericalCap &cap, FuncObject &func) const
Process all the objects intersecting the given region using the passed function object.