18#include "SpatialIndex.h"
19#include "SpatialException.h"
25#include <sys/malloc.h>
39#define N(x) nodes_[(x)]
40#define V(x) vertices_[nodes_[index].v_[(x)]]
41#define IV(x) nodes_[index].v_[(x)]
42#define W(x) vertices_[nodes_[index].w_[(x)]]
43#define IW(x) nodes_[index].w_[(x)]
44#define ICHILD(x) nodes_[index].childID_[(x)]
46#define IV_(x) nodes_[index_].v_[(x)]
47#define IW_(x) nodes_[index_].w_[(x)]
48#define ICHILD_(x) nodes_[index_].childID_[(x)]
62 size_t nodes, vertices;
64 vMax(&nodes, &vertices);
65 layers_.resize(buildlevel_ + 1);
66 nodes_.resize(nodes + 1);
67 vertices_.resize(vertices + 1);
72 layers_[0].level_ = 0;
73 layers_[0].nVert_ = 6;
74 layers_[0].nNode_ = 8;
75 layers_[0].nEdge_ = 12;
76 layers_[0].firstIndex_ = 1;
77 layers_[0].firstVertex_ = 0;
84 { -1.0L, 0.0L, 0.0L },
85 { 0.0L, -1.0L, 0.0L },
89 for (
int i = 0; i < 6; i++)
90 vertices_[i].set(v[i][0], v[i][1], v[i][2]);
94 newNode(1, 5, 2, 8, 0);
95 newNode(2, 5, 3, 9, 0);
96 newNode(3, 5, 4, 10, 0);
97 newNode(4, 5, 1, 11, 0);
98 newNode(1, 0, 4, 12, 0);
99 newNode(4, 0, 3, 13, 0);
100 newNode(3, 0, 2, 14, 0);
101 newNode(2, 0, 1, 15, 0);
106 size_t level = buildlevel_;
109 SpatialEdge edge(*
this,
pl);
110 edge.makeMidPoints();
123 if (buildlevel_ == maxlevel_)
126 v0 = vertices_[nodes_[
idx].v_[0]];
127 v1 = vertices_[nodes_[
idx].v_[1]];
128 v2 = vertices_[nodes_[
idx].v_[2]];
135 uint64 sid =
id >> ((maxlevel_ - buildlevel_) * 2);
138 v0 = vertices_[nodes_[
idx].v_[0]];
139 v1 = vertices_[nodes_[
idx].v_[1]];
140 v2 = vertices_[nodes_[
idx].v_[2]];
145 for (
uint32 i = buildlevel_ + 1; i <= maxlevel_; i++)
147 uint64 j = (
id >> ((maxlevel_ - i) * 2)) & 3;
183void SpatialIndex::makeNewLayer(
size_t oldlayer)
191 layers_[
newlayer].firstIndex_ = index_;
198 id = N(index).id_ << 2;
199 ICHILD(0) = newNode(IV(0), IW(2), IW(1),
id++, index);
200 ICHILD(1) = newNode(IV(1), IW(0), IW(2),
id++, index);
201 ICHILD(2) = newNode(IV(2), IW(1), IW(0),
id++, index);
202 ICHILD(3) = newNode(IW(0), IW(1), IW(2),
id, index);
225 N(index_).index_ = index_;
226 N(index_).parent_ = parent;
237void SpatialIndex::vMax(
size_t *nodes,
size_t *vertices)
242 int32 i = buildlevel_;
250 *nodes += (size_t)nf;
252 *vertices = (size_t)
nv;
256 i = maxlevel_ - buildlevel_;
268void SpatialIndex::sortIndex()
270 std::vector<QuadNode>
oldnodes(nodes_);
275#define ON(x) oldnodes[(x)]
278 for (index = IOFFSET,
leaf = IOFFSET,
nonleaf = nodes_.size() - 1; index < nodes_.size(); index++)
280 if (ON(index).childID_[0] == 0)
285 for (
size_t i = 0; i < 4; i++)
287 if (N(N(
leaf).parent_).childID_[i] == index)
289 N(N(
leaf).parent_).childID_[i] =
leaf;
306 for (
size_t i = 0; i < 4; i++)
308 if (N(N(
nonleaf).parent_).childID_[i] == index)
348 if (name[0] !=
'N' && name[0] !=
'S')
354 throw SpatialFailure(
"SpatialIndex:idByName:invalid name - too short ", name);
355 if (size > HTMNAMEMAX)
356 throw SpatialFailure(
"SpatialIndex:idByName:invalid name - too long ", name);
358 for (i = size - 1; i > 0; i--)
360 if (name[i] >
'3' || name[i] <
'0')
361 throw SpatialFailure(
"SpatialIndex:idByName:invalid name digit ", name);
362 out += (
uint64(name[i] -
'0') << 2 * (size - i - 1));
368 out += (i << (2 * size - 2));
404 IDHIGHBIT = IDHIGHBIT << 63;
405 IDHIGHBIT2 = IDHIGHBIT2 << 62;
422 for (i = 0; i < IDSIZE; i += 2)
424 if ((
id << i) & IDHIGHBIT)
426 if ((
id << i) & IDHIGHBIT2)
432 size = (IDSIZE - i) >> 1;
435 name =
new char[size + 1];
438 for (i = 0; i < size - 1; i++)
439 name[size - i - 1] =
'0' +
char((
id >> i * 2) & 3);
442 if ((
id >> (size * 2 - 2)) & 1)
461 char name[HTMNAMEMAX];
513 for (index = 1; index <= 8; index++)
515 if ((V(0) ^ V(1)) * v < -gEpsilon)
517 if ((V(1) ^ V(2)) * v < -gEpsilon)
519 if ((V(2) ^ V(0)) * v < -gEpsilon)
524 while (ICHILD(0) != 0)
527 for (
size_t i = 0; i < 4; i++)
529 index = nodes_[
oldindex].childID_[i];
530 if ((V(0) ^ V(1)) * v < -gEpsilon)
532 if ((V(1) ^ V(2)) * v < -gEpsilon)
534 if ((V(2) ^ V(0)) * v < -gEpsilon)
540 if (maxlevel_ == buildlevel_)
546 char name[HTMNAMEMAX];
553 size_t level = maxlevel_ - buildlevel_;
563 if (isInside(v,
v0,
w2, w1))
570 else if (isInside(v,
v1, w0,
w2))
578 else if (isInside(v,
v2, w1, w0))
586 else if (isInside(v, w0, w1,
w2))
606 if ((
v0 ^
v1) * v < -gEpsilon)
608 if ((
v1 ^
v2) * v < -gEpsilon)
610 if ((
v2 ^
v0) * v < -gEpsilon)
SpatialException thrown on operational failure.
uint64 idByPoint(const SpatialVector &vector) const
find a node by giving a vector.
static uint64 idByName(const char *)
NodeName conversion to integer ID.
void pointById(SpatialVector &vector, uint64 ID) const
find the vector to the centroid of a triangle represented by the ID
SpatialIndex(size_t maxlevel, size_t buildlevel=5)
Constructor.
void nodeVertex(const uint64 id, SpatialVector &v1, SpatialVector &v2, SpatialVector &v3) const
return the actual vertex vectors
static char * nameById(uint64 ID, char *name=nullptr)
int32 conversion to a string (name of database).
SpatialVector is a 3D vector usually living on the surface of the sphere.
void normalize()
Normalize vector length to 1.