-
Notifications
You must be signed in to change notification settings - Fork 3.4k
/
HilbertOrder.js
118 lines (105 loc) · 2.67 KB
/
HilbertOrder.js
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
import Check from "./Check.js";
import DeveloperError from "./DeveloperError.js";
/**
* Hilbert Order helper functions.
*
* @namespace HilbertOrder
*/
const HilbertOrder = {};
/**
* Computes the Hilbert index at the given level from 2D coordinates.
*
* @param {Number} level The level of the curve
* @param {Number} x The X coordinate
* @param {Number} y The Y coordinate
* @returns {Number} The Hilbert index.
* @private
*/
HilbertOrder.encode2D = function (level, x, y) {
const n = Math.pow(2, level);
//>>includeStart('debug', pragmas.debug);
Check.typeOf.number("level", level);
Check.typeOf.number("x", x);
Check.typeOf.number("y", y);
if (level < 1) {
throw new DeveloperError("Hilbert level cannot be less than 1.");
}
if (x < 0 || x >= n || y < 0 || y >= n) {
throw new DeveloperError("Invalid coordinates for given level.");
}
//>>includeEnd('debug');
const p = {
x: x,
y: y,
};
let rx,
ry,
s,
// eslint-disable-next-line no-undef
index = BigInt(0);
for (s = n / 2; s > 0; s /= 2) {
rx = (p.x & s) > 0 ? 1 : 0;
ry = (p.y & s) > 0 ? 1 : 0;
// eslint-disable-next-line no-undef
index += BigInt(((3 * rx) ^ ry) * s * s);
rotate(n, p, rx, ry);
}
return index;
};
/**
* Computes the 2D coordinates from the Hilbert index at the given level.
*
* @param {Number} level The level of the curve
* @param {BigInt} index The Hilbert index
* @returns {Number[]} An array containing the 2D coordinates ([x, y]) corresponding to the Morton index.
* @private
*/
HilbertOrder.decode2D = function (level, index) {
//>>includeStart('debug', pragmas.debug);
Check.typeOf.number("level", level);
Check.typeOf.bigint("index", index);
if (level < 1) {
throw new DeveloperError("Hilbert level cannot be less than 1.");
}
// eslint-disable-next-line no-undef
if (index < BigInt(0) || index >= BigInt(Math.pow(4, level))) {
throw new DeveloperError(
"Hilbert index exceeds valid maximum for given level."
);
}
//>>includeEnd('debug');
const n = Math.pow(2, level);
const p = {
x: 0,
y: 0,
};
let rx, ry, s, t;
for (s = 1, t = index; s < n; s *= 2) {
// eslint-disable-next-line no-undef
rx = 1 & Number(t / BigInt(2));
// eslint-disable-next-line no-undef
ry = 1 & Number(t ^ BigInt(rx));
rotate(s, p, rx, ry);
p.x += s * rx;
p.y += s * ry;
// eslint-disable-next-line no-undef
t /= BigInt(4);
}
return [p.x, p.y];
};
/**
* @private
*/
function rotate(n, p, rx, ry) {
if (ry !== 0) {
return;
}
if (rx === 1) {
p.x = n - 1 - p.x;
p.y = n - 1 - p.y;
}
const t = p.x;
p.x = p.y;
p.y = t;
}
export default HilbertOrder;