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