Stellarium 0.15.2
StelGeodesicGrid.hpp
1 /*
2 
3 StelGeodesicGrid: a library for dividing the sphere into triangle zones
4 by subdividing the icosahedron
5 
6 Author and Copyright: Johannes Gajdosik, 2006
7 
8 This library requires a simple Vector library,
9 which may have different copyright and license,
10 for example Vec3f from VecMath.hpp.
11 
12 In the moment I choose to distribute the library under the GPL,
13 later I may choose to additionally distribute it under a more
14 relaxed license like the LGPL. If you want to have the library
15 under another license, please ask me.
16 
17 
18 
19 This library is free software; you can redistribute it and/or
20 modify it under the terms of the GNU General Public License
21 as published by the Free Software Foundation; either version 2
22 of the License, or (at your option) any later version.
23 
24 This library is distributed in the hope that it will be useful,
25 but WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 GNU General Public License for more details.
28 
29 You should have received a copy of the GNU General Public License
30 along with this library; if not, write to the Free Software
31 Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA.
32 
33 */
34 
35 #ifndef _STELGEODESICGRID_HPP_
36 #define _STELGEODESICGRID_HPP_
37 
38 #include "StelSphereGeometry.hpp"
39 
41 
48 {
49 public:
50  StelGeodesicGrid(int maxLevel);
51  ~StelGeodesicGrid(void);
52 
53  int getMaxLevel(void) const {return maxLevel;}
54 
55  static int nrOfZones(int level) {return (20<<(level<<1));} // 20*4^level
56 
57  int getNrOfZones(void) const {return nrOfZones(maxLevel);}
58 
59  typedef void (VisitFunc)(int lev,int index,
60  const Vec3f &c0,
61  const Vec3f &c1,
62  const Vec3f &c2,
63  void *context);
64  void visitTriangles(int maxVisitLevel, VisitFunc *func,void *context) const;
65 
71  int getZoneNumberForPoint(const Vec3f &v,int searchLevel) const;
72 
74  void getTriangleCorners(int lev, int index, Vec3f& c0, Vec3f& c1, Vec3f& c2) const;
75 
77  int getPartnerTriangle(int lev, int index) const;
78 
82  const GeodesicSearchResult* search(const QVector<SphericalCap>& convex, int maxSearchLevel) const;
83 
84 private:
85  friend class GeodesicSearchResult;
86 
102  void searchZones(const QVector<SphericalCap>& convex,
103  int **inside,int **border,int maxSearchLevel) const;
104 
105  const Vec3f& getTriangleCorner(int lev, int index, int cornerNumber) const;
106  void initTriangle(int lev,int index,
107  const Vec3f &c0,
108  const Vec3f &c1,
109  const Vec3f &c2);
110  void visitTriangles(int lev,int index,
111  const Vec3f &c0,
112  const Vec3f &c1,
113  const Vec3f &c2,
114  int maxVisitLevel,
115  VisitFunc *func,
116  void *context) const;
117  void searchZones(int lev,int index,
118  const QVector<SphericalCap>& convex,
119  const int *indexOfUsedSphericalCaps,
120  const int halfSpacesUsed,
121  const bool *corner0_inside,
122  const bool *corner1_inside,
123  const bool *corner2_inside,
124  int **inside,int **border,int maxSearchLevel) const;
125 
126  const int maxLevel;
127  struct Triangle
128  {
129  Vec3f e0,e1,e2; // Seitenmittelpunkte
130  };
131  Triangle **triangles;
132  // 20*(4^0+4^1+...+4^n)=20*(4*(4^n)-1)/3 triangles total
133  // 2+10*4^n corners
134 
136  mutable GeodesicSearchResult* cacheSearchResult;
137  mutable int lastMaxSearchlevel;
138  mutable QVector<SphericalCap> lastSearchRegion;
139 };
140 
142 {
143 public:
145  ~GeodesicSearchResult(void);
146  void print(void) const;
147 private:
148  friend class GeodesicSearchInsideIterator;
149  friend class GeodesicSearchBorderIterator;
150  friend class StelGeodesicGrid;
151 
152  void search(const QVector<SphericalCap>& convex, int maxSearchLevel);
153 
154  const StelGeodesicGrid &grid;
155  int **const zones;
156  int **const inside;
157  int **const border;
158 };
159 
161 {
162 public:
164  : r(ar),level((alevel<0)?0:(alevel>ar.grid.getMaxLevel())
165  ?ar.grid.getMaxLevel():alevel),
166  end(ar.zones[GeodesicSearchBorderIterator::level]+
167  StelGeodesicGrid::nrOfZones(GeodesicSearchBorderIterator::level))
168  {reset();}
169  void reset(void) {index = r.border[level];}
170  int next(void) // returns -1 when finished
171  {if (index < end) {return *index++;} return -1;}
172 private:
173  const GeodesicSearchResult &r;
174  const int level;
175  const int *const end;
176  const int *index;
177 };
178 
179 
181 {
182 public:
184  : r(ar),
185  maxLevel((alevel<0)?0:(alevel>ar.grid.getMaxLevel())?ar.grid.getMaxLevel():alevel)
186  {reset();}
187  void reset(void);
188  int next(void); // returns -1 when finished
189 private:
190  const GeodesicSearchResult &r;
191  const int maxLevel;
192  int level;
193  int maxCount;
194  int *indexP;
195  int *endP;
196  int index;
197  int count;
198 };
199 
200 #endif // _STELGEODESICGRID_HPP_
const GeodesicSearchResult * search(const QVector< SphericalCap > &convex, int maxSearchLevel) const
Return a search result matching the given spatial region The result is cached, meaning that it is ver...
int getZoneNumberForPoint(const Vec3f &v, int searchLevel) const
Find the zone number in which a given point lies.
Grid of triangles (zones) on the sphere with radius 1, generated by subdividing the icosahedron...
void getTriangleCorners(int lev, int index, Vec3f &c0, Vec3f &c1, Vec3f &c2) const
Return the position of the 3 corners for the triangle at the given level and index.
int getPartnerTriangle(int lev, int index) const
Return the index of the partner triangle with which to form a parallelogram.
Define all SphericalGeometry primitives as well as the SphericalRegionP type.