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 
55 class LINKAGE SpatialIndex
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:59
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Tue Nov 28 2023 03:58:23 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.