15670918640

Committed 16 Jun 2025 02:08AM UTC coverage: 11.775% (-0.2%) from 11.931%

Build # 15670918640

Build Type

push

github

Committed by

alex-w

Commit Message

Updated data

Run Details

14700 of 124846 relevant lines covered (11.77%)

18324.52 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

6.25

/src/core/StelGeodesicGrid.hpp

/*
 
StelGeodesicGrid: a library for dividing the sphere into triangle zones
by subdividing the icosahedron
 
Author and Copyright: Johannes Gajdosik, 2006
 
This library requires a simple Vector library,
which may have different copyright and license,
for example Vec3f from VecMath.hpp.
 
In the moment I choose to distribute the library under the GPL,
later I may choose to additionally distribute it under a more
relaxed license like the LGPL. If you want to have the library
under another license, please ask me.
 
 
 
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
 
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
 
You should have received a copy of the GNU General Public License
along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA  02110-1335, USA.
 
*/

#ifndef STELGEODESICGRID_HPP
#define STELGEODESICGRID_HPP

#include "StelSphereGeometry.hpp"

class GeodesicSearchResult;

//! @class StelGeodesicGrid
//! Grid of triangles (zones) on the sphere with radius 1, generated by subdividing the icosahedron.
//! level 0: just the icosahedron, 20 zones
//! level 1: 80 zones, level 2: 320 zones, ...
//! Each zone has a unique integer number in the range [0,getNrOfZones()-1].
class StelGeodesicGrid
{
public:
        StelGeodesicGrid(int maxLevel);
        ~StelGeodesicGrid(void);
        
        int getMaxLevel(void) const {return maxLevel;}
        
        static int nrOfZones(int level) {return ((20<<(level<<1)) + 1);} // 20*4^level local zones
        
        int getNrOfZones(void) const {return nrOfZones(maxLevel);}
        
        typedef void (VisitFunc)(int lev,int index,
                                                         const Vec3f &c0,
                                                         const Vec3f &c1,
                                                         const Vec3f &c2,
                                 void *context);
        void visitTriangles(int maxVisitLevel, VisitFunc *func,void *context) const;

        //! Find the zone number in which a given point lies.
        //! prerequisite: v*v==1
        //! When the point lies on the border of two or more zones,
        //! one such zone is returned (always the same one,
        //! because the algorithm is deterministic).
        int getZoneNumberForPoint(const Vec3f &v,int searchLevel) const;

        //! Return the position of the 3 corners for the triangle at the given level and index
        void getTriangleCorners(int lev, int index, Vec3f& c0, Vec3f& c1, Vec3f& c2) const;
        
        //! Return the index of the partner triangle with which to form a parallelogram
        int getPartnerTriangle(int lev, int index) const;
        
        //! Return a search result matching the given spatial region
        //! The result is cached, meaning that it is very fast to search the same region consecutively
        //! @return a GeodesicSearchResult instance which must be used with GeodesicSearchBorderIterator and GeodesicSearchInsideIterator
        const GeodesicSearchResult* search(const QVector<SphericalCap>& convex, int maxSearchLevel) const;

private:
        friend class GeodesicSearchResult;
        
        //! Find all zones that lie fully(inside) or partly(border)
        //! in the intersection of the given half spaces.
        //! The result is accurate when (0,0,0) lies on the border of
        //! each half space. If this is not the case,
        //! the result may be inaccurate, because it is assumed, that
        //! a zone lies in a half space when its 3 corners lie in this half space.
        //! inside[l] points to the begin of an integer array of size nrOfZones(l),
        //! border[l] points to one after the end of the same integer array.
        //! The array will be filled from the beginning with the inside zone numbers
        //! and from the end with the border zone numbers of the given level l
        //! for 0<=l<=getMaxLevel().
        //! inside[l] will not contain zones that are already contained
        //! in inside[l1] for some l1 < l.
        //! In order to restrict search depth set maxSearchLevel < maxLevel,
        //! for full search depth set maxSearchLevel = maxLevel,
        void searchZones(const QVector<SphericalCap>& convex,
                                         int **inside,int **border,int maxSearchLevel) const;
        
        const Vec3f& getTriangleCorner(int lev, int index, int cornerNumber) const;
        void initTriangle(int lev,int index,
                                          const Vec3f &c0,
                                          const Vec3f &c1,
                                          const Vec3f &c2);
        void visitTriangles(int lev,int index,
                                                const Vec3f &c0,
                                                const Vec3f &c1,
                                                const Vec3f &c2,
                            int maxVisitLevel,
                            VisitFunc *func,
                            void *context) const;
        void searchZones(int lev,int index,
                         const QVector<SphericalCap>& convex,
                         const int *indexOfUsedSphericalCaps,
                         const int halfSpacesUsed,
                         const bool *corner0_inside,
                         const bool *corner1_inside,
                         const bool *corner2_inside,
                         int **inside,int **border,int maxSearchLevel) const;

        const int maxLevel;
        struct Triangle
        {
                Vec3f e0,e1,e2;   // Seitenmittelpunkte
        };
        Triangle **triangles;
        // 20*(4^0+4^1+...+4^n)=20*(4*(4^n)-1)/3 triangles total
        // 2+10*4^n corners
        
        //! A cached search result used to avoid doing twice the same search
        mutable GeodesicSearchResult* cacheSearchResult;
        mutable int lastMaxSearchlevel;
        mutable QVector<SphericalCap> lastSearchRegion;
};

class GeodesicSearchResult
{
public:
        GeodesicSearchResult(const StelGeodesicGrid &grid);
        ~GeodesicSearchResult(void);
        void print(void) const;
private:
        friend class GeodesicSearchInsideIterator;
        friend class GeodesicSearchBorderIterator;
        friend class StelGeodesicGrid;
        
        void search(const QVector<SphericalCap>& convex, int maxSearchLevel);
        
        const StelGeodesicGrid &grid;
        int **const zones;
        int **const inside;
        int **const border;
};

class GeodesicSearchBorderIterator
{
public:
        GeodesicSearchBorderIterator(const GeodesicSearchResult &ar,int alevel)
                : r(ar),level((alevel<0)?0:(alevel>ar.grid.getMaxLevel())
                                     ?ar.grid.getMaxLevel():alevel),
                        end(ar.zones[GeodesicSearchBorderIterator::level]+
                            StelGeodesicGrid::nrOfZones(GeodesicSearchBorderIterator::level))
        {reset();}
        void reset(void) {index = r.border[level];}
        int next(void) // returns -1 when finished
        {if (index < end) {return *index++;} return -1;}
private:
        const GeodesicSearchResult &r;
        const int level;
        const int *const end;
        const int *index;
};


class GeodesicSearchInsideIterator
{
public:
        GeodesicSearchInsideIterator(const GeodesicSearchResult &ar,int alevel)
                :         r(ar), 
                        maxLevel((alevel<0)?0:(alevel>ar.grid.getMaxLevel())?ar.grid.getMaxLevel():alevel)
        {reset();}
        void reset(void);
        int next(void); // returns -1 when finished
private:
        const GeodesicSearchResult &r;
        const int maxLevel;
        int level;
        int maxCount;
        int *indexP;
        int *endP;
        int index;
        int count;
};

#endif // 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
40	class GeodesicSearchResult;
41
42	//! @class StelGeodesicGrid
43	//! Grid of triangles (zones) on the sphere with radius 1, generated by subdividing the icosahedron.
44	//! level 0: just the icosahedron, 20 zones
45	//! level 1: 80 zones, level 2: 320 zones, ...
46	//! Each zone has a unique integer number in the range [0,getNrOfZones()-1].
47	class StelGeodesicGrid
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)) + 1);} // 20*4^level local zones	4✔
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
66	//! Find the zone number in which a given point lies.
67	//! prerequisite: v*v==1
68	//! When the point lies on the border of two or more zones,
69	//! one such zone is returned (always the same one,
70	//! because the algorithm is deterministic).
71	int getZoneNumberForPoint(const Vec3f &v,int searchLevel) const;
72
73	//! Return the position of the 3 corners for the triangle at the given level and index
74	void getTriangleCorners(int lev, int index, Vec3f& c0, Vec3f& c1, Vec3f& c2) const;
75
76	//! Return the index of the partner triangle with which to form a parallelogram
77	int getPartnerTriangle(int lev, int index) const;
78
79	//! Return a search result matching the given spatial region
80	//! The result is cached, meaning that it is very fast to search the same region consecutively
81	//! @return a GeodesicSearchResult instance which must be used with GeodesicSearchBorderIterator and GeodesicSearchInsideIterator
82	const GeodesicSearchResult* search(const QVector<SphericalCap>& convex, int maxSearchLevel) const;
83
84	private:
85	friend class GeodesicSearchResult;
86
87	//! Find all zones that lie fully(inside) or partly(border)
88	//! in the intersection of the given half spaces.
89	//! The result is accurate when (0,0,0) lies on the border of
90	//! each half space. If this is not the case,
91	//! the result may be inaccurate, because it is assumed, that
92	//! a zone lies in a half space when its 3 corners lie in this half space.
93	//! inside[l] points to the begin of an integer array of size nrOfZones(l),
94	//! border[l] points to one after the end of the same integer array.
95	//! The array will be filled from the beginning with the inside zone numbers
96	//! and from the end with the border zone numbers of the given level l
97	//! for 0<=l<=getMaxLevel().
98	//! inside[l] will not contain zones that are already contained
99	//! in inside[l1] for some l1 < l.
100	//! In order to restrict search depth set maxSearchLevel < maxLevel,
101	//! for full search depth set maxSearchLevel = maxLevel,
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
135	//! A cached search result used to avoid doing twice the same search
136	mutable GeodesicSearchResult* cacheSearchResult;
137	mutable int lastMaxSearchlevel;
138	mutable QVector<SphericalCap> lastSearchRegion;
139	};
140
141	class GeodesicSearchResult
142	{
143	public:
144	GeodesicSearchResult(const StelGeodesicGrid &grid);
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
160	class GeodesicSearchBorderIterator
161	{
162	public:
163	GeodesicSearchBorderIterator(const GeodesicSearchResult &ar,int alevel)	×
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
180	class GeodesicSearchInsideIterator
181	{
182	public:
183	GeodesicSearchInsideIterator(const GeodesicSearchResult &ar,int alevel)	×
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

Stellarium / stellarium / 15670918640

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous