File indexing completed on 2024-04-14 03:42:34
0001 #ifndef _SpatialIndex_h 0002 #define _SpatialIndex_h 0003 0004 //# Filename: SpatialIndex.h 0005 //# 0006 //# SpatialIndex is the class for the sky indexing routines. 0007 //# 0008 //# Author: Peter Z. Kunszt, based on A. Szalay s code 0009 //# 0010 //# Date: October 15, 1998 0011 //# 0012 //# SPDX-FileCopyrightText: 2000 Peter Z. Kunszt Alex S. Szalay, Aniruddha R. Thakar 0013 //# The Johns Hopkins University 0014 //# Modification History: 0015 //# 0016 //# Oct 18, 2001 : Dennis C. Dinge -- Replaced ValVec with std::vector 0017 //# Sept 9, 2002 : Gyorgy Fekete -- added setMaxlevel() 0018 //# 0019 0020 #include <cmath> 0021 #include <string.h> 0022 #include <time.h> 0023 #include <SpatialGeneral.h> 0024 #include <SpatialVector.h> 0025 #include <SpatialEdge.h> 0026 0027 #include <vector> 0028 0029 //######################################################################## 0030 //# 0031 //# Spatial Index class 0032 //# 0033 0034 /** @class SpatialIndex 0035 SpatialIndex is a quad tree of spherical triangles. The tree 0036 is built in the following way: Start out with 8 triangles on the 0037 sphere using the 3 main circles to determine them. Then, every 0038 triangle can be decomposed into 4 new triangles by drawing main 0039 circles between midpoints of its edges: 0040 0041 <pre> 0042 0043 . /\ 0044 . / \ 0045 . /____\ 0046 . /\ /\ 0047 . / \ / \ 0048 . /____\/____\ 0049 0050 </pre> 0051 This is how the quad tree is built up to a certain level by 0052 decomposing every triangle again and again. 0053 */ 0054 0055 class LINKAGE SpatialIndex 0056 { 0057 public: 0058 /** Constructor. 0059 Give the level of the index and optionally the level to build - 0060 i.e. the depth to keep in memory. if maxlevel - buildlevel > 0 0061 , that many levels are generated on the fly each time the index 0062 is called. */ 0063 SpatialIndex(size_t maxlevel, size_t buildlevel = 5); 0064 0065 /// NodeName conversion to integer ID 0066 static uint64 idByName(const char *); 0067 0068 /** int32 conversion to a string (name of database). 0069 WARNING: if name is already allocated, a size of at least 17 is 0070 required. The conversion is done by directly calculating the 0071 name from a number. To calculate the name of a certain level, 0072 the mechanism is that the name is given by (\# of nodes in that 0073 level) + (id of node). So for example, for the first level, 0074 there are 8 nodes, and we get the names from numbers 8 through 0075 15 giving S0,S1,S2,S3,N0,N1,N2,N3. The order is always 0076 ascending starting from S0000.. to N3333... */ 0077 static char *nameById(uint64 ID, char *name = nullptr); 0078 0079 /** find the vector to the centroid of a triangle represented by 0080 the ID */ 0081 void pointById(SpatialVector &vector, uint64 ID) const; 0082 0083 /** find a node by giving a vector. 0084 The ID of the node is returned. */ 0085 uint64 idByPoint(const SpatialVector &vector) const; 0086 0087 /// return the actual vertex vectors 0088 void nodeVertex(const uint64 id, SpatialVector &v1, SpatialVector &v2, SpatialVector &v3) const; 0089 0090 private: 0091 // STRUCTURES 0092 0093 struct Layer 0094 { 0095 size_t level_; // layer level 0096 size_t nVert_; // number of vertices in this layer 0097 size_t nNode_; // number of nodes 0098 size_t nEdge_; // number of edges 0099 uint64 firstIndex_; // index of first node of this layer 0100 size_t firstVertex_; // index of first vertex of this layer 0101 }; 0102 0103 struct QuadNode 0104 { 0105 uint64 index_; // its own index 0106 size_t v_[3]; // The three vertex vector indices 0107 size_t w_[3]; // The three middlepoint vector indices 0108 uint64 childID_[4]; // ids of children 0109 uint64 parent_; // id of the parent node (needed for sorting) 0110 uint64 id_; // numeric id -> name 0111 }; 0112 0113 // FUNCTIONS 0114 0115 // insert a new node_[] into the list. The vertex indices are given by 0116 // v1,v2,v3 and the id of the node is set. 0117 uint64 newNode(size_t v1, size_t v2, size_t v3, uint64 id, uint64 parent); 0118 0119 // make new nodes in a new layer. 0120 void makeNewLayer(size_t oldlayer); 0121 0122 // return the total number of nodes and vertices 0123 void vMax(size_t *nodes, size_t *vertices); 0124 0125 // sort the index so that the leaf nodes are at the beginning 0126 void sortIndex(); 0127 0128 // Test whether a vector v is inside a triangle v0,v1,v2. Input 0129 // triangle has to be sorted in a counter-clockwise direction. 0130 bool isInside(const SpatialVector &v, const SpatialVector &v0, const SpatialVector &v1, 0131 const SpatialVector &v2) const; 0132 0133 // VARIABLES 0134 0135 size_t maxlevel_; // the depth of the Layer 0136 size_t buildlevel_; // the depth of the Layer stored 0137 uint64 leaves_; // number of leaf nodes 0138 uint64 storedleaves_; // number of stored leaf nodes 0139 std::vector<QuadNode> nodes_; // the array of nodes 0140 std::vector<Layer> layers_; // array of layers 0141 0142 std::vector<SpatialVector> vertices_; 0143 uint64 index_; // the current index_ of vertices 0144 0145 friend class SpatialEdge; 0146 friend class SpatialConvex; 0147 friend class RangeConvex; 0148 }; 0149 0150 #endif