Kstars

SpatialIndex.h
1#ifndef _SpatialIndex_h
2#define _SpatialIndex_h
3
4//# Filename: SpatialIndex.h
5//#
6//# SpatialIndex is the class for the sky indexing routines.
7//#
8//# Author: Peter Z. Kunszt, based on A. Szalay s code
9//#
10//# Date: October 15, 1998
11//#
12//# SPDX-FileCopyrightText: 2000 Peter Z. Kunszt Alex S. Szalay, Aniruddha R. Thakar
13//# The Johns Hopkins University
14//# Modification History:
15//#
16//# Oct 18, 2001 : Dennis C. Dinge -- Replaced ValVec with std::vector
17//# Sept 9, 2002 : Gyorgy Fekete -- added setMaxlevel()
18//#
19
20#include <cmath>
21#include <string.h>
22#include <time.h>
23#include <SpatialGeneral.h>
24#include <SpatialVector.h>
25#include <SpatialEdge.h>
26
27#include <vector>
28
29//########################################################################
30//#
31//# Spatial Index class
32//#
33
34/** @class SpatialIndex
35 SpatialIndex is a quad tree of spherical triangles. The tree
36 is built in the following way: Start out with 8 triangles on the
37 sphere using the 3 main circles to determine them. Then, every
38 triangle can be decomposed into 4 new triangles by drawing main
39 circles between midpoints of its edges:
40
41<pre>
42
43. /\
44. / \
45. /____\
46. /\ /\
47. / \ / \
48. /____\/____\
49
50</pre>
51 This is how the quad tree is built up to a certain level by
52 decomposing every triangle again and again.
53*/
54
56{
57 public:
58 /** Constructor.
59 Give the level of the index and optionally the level to build -
60 i.e. the depth to keep in memory. if maxlevel - buildlevel > 0
61 , that many levels are generated on the fly each time the index
62 is called. */
63 SpatialIndex(size_t maxlevel, size_t buildlevel = 5);
64
65 /// NodeName conversion to integer ID
66 static uint64 idByName(const char *);
67
68 /** int32 conversion to a string (name of database).
69 WARNING: if name is already allocated, a size of at least 17 is
70 required. The conversion is done by directly calculating the
71 name from a number. To calculate the name of a certain level,
72 the mechanism is that the name is given by (\# of nodes in that
73 level) + (id of node). So for example, for the first level,
74 there are 8 nodes, and we get the names from numbers 8 through
75 15 giving S0,S1,S2,S3,N0,N1,N2,N3. The order is always
76 ascending starting from S0000.. to N3333... */
77 static char *nameById(uint64 ID, char *name = nullptr);
78
79 /** find the vector to the centroid of a triangle represented by
80 the ID */
81 void pointById(SpatialVector &vector, uint64 ID) const;
82
83 /** find a node by giving a vector.
84 The ID of the node is returned. */
85 uint64 idByPoint(const SpatialVector &vector) const;
86
87 /// return the actual vertex vectors
88 void nodeVertex(const uint64 id, SpatialVector &v1, SpatialVector &v2, SpatialVector &v3) const;
89
90 private:
91 // STRUCTURES
92
93 struct Layer
94 {
95 size_t level_; // layer level
96 size_t nVert_; // number of vertices in this layer
97 size_t nNode_; // number of nodes
98 size_t nEdge_; // number of edges
99 uint64 firstIndex_; // index of first node of this layer
100 size_t firstVertex_; // index of first vertex of this layer
101 };
102
103 struct QuadNode
104 {
105 uint64 index_; // its own index
106 size_t v_[3]; // The three vertex vector indices
107 size_t w_[3]; // The three middlepoint vector indices
108 uint64 childID_[4]; // ids of children
109 uint64 parent_; // id of the parent node (needed for sorting)
110 uint64 id_; // numeric id -> name
111 };
112
113 // FUNCTIONS
114
115 // insert a new node_[] into the list. The vertex indices are given by
116 // v1,v2,v3 and the id of the node is set.
117 uint64 newNode(size_t v1, size_t v2, size_t v3, uint64 id, uint64 parent);
118
119 // make new nodes in a new layer.
120 void makeNewLayer(size_t oldlayer);
121
122 // return the total number of nodes and vertices
123 void vMax(size_t *nodes, size_t *vertices);
124
125 // sort the index so that the leaf nodes are at the beginning
126 void sortIndex();
127
128 // Test whether a vector v is inside a triangle v0,v1,v2. Input
129 // triangle has to be sorted in a counter-clockwise direction.
130 bool isInside(const SpatialVector &v, const SpatialVector &v0, const SpatialVector &v1,
131 const SpatialVector &v2) const;
132
133 // VARIABLES
134
135 size_t maxlevel_; // the depth of the Layer
136 size_t buildlevel_; // the depth of the Layer stored
137 uint64 leaves_; // number of leaf nodes
138 uint64 storedleaves_; // number of stored leaf nodes
139 std::vector<QuadNode> nodes_; // the array of nodes
140 std::vector<Layer> layers_; // array of layers
141
142 std::vector<SpatialVector> vertices_;
143 uint64 index_; // the current index_ of vertices
144
145 friend class SpatialEdge;
146 friend class SpatialConvex;
147 friend class RangeConvex;
148};
149
150#endif
A spatial convex is composed of spatial constraints.
Definition RangeConvex.h:60
SpatialIndex is a quad tree of spherical triangles.
SpatialVector is a 3D vector usually living on the surface of the sphere.
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Tue Mar 26 2024 11:19:03 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.