236 lines
5.7 KiB
Plaintext
236 lines
5.7 KiB
Plaintext
// echo ALGORITHM.adoc | entr sh -c "podman run --rm -it --network none -v "${PWD}:/documents/" asciidoctor/docker-asciidoctor asciidoctor -r asciidoctor-mathematical -a mathematical-format=svg ALGORITHM.adoc; printf 'Done ($(date -Isecond))\n'"
|
|
|
|
include::common.adoc.template[]
|
|
:toc:
|
|
|
|
= Algorithm
|
|
|
|
The goal of this document is to define the algorithm.
|
|
|
|
If you want to see the steps to get to this definition, go to link:design[DESIGN].
|
|
|
|
== Data format
|
|
|
|
[source,title='xpin and S2 CellID Format']
|
|
----
|
|
=== xpin Format ===
|
|
WORD2 (12 bits) [52, 63] : vvvvvvvvvvvv
|
|
WORD1 (12 bits) [40, 51] : | |vvvv vvvvvvvv
|
|
WORD0 (12 bits) [28, 39] : | | |vvvvvvvv vvvv
|
|
0000 (13 bits) [15, 27] : | | | |vvvvvvvvvvvv v
|
|
Not represented : | | | | |
|
|
: | | | | |
|
|
Bit : 63 52 48 40 32 28 16| 0
|
|
: | | | | | | | | |
|
|
: 0100101110101000 1011100010010011 1001001100100100 1100000000000000
|
|
=== S2 CellID Format === | | || |
|
|
Face number : ^^^ || |
|
|
Data bits : ^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^| |
|
|
Bit after data bits (1) : ^ |
|
|
All remaining bits (0) : ^^^^^^^^^^^^^^
|
|
----
|
|
|
|
== Encoding
|
|
|
|
[%header,cols="2m,5a"]
|
|
|===
|
|
|Step |Code
|
|
|
|
|(lat, lon)
|
|
|Given
|
|
|
|
|(x, y, z)/Point
|
|
| [source,rust]
|
|
----
|
|
fn lat_lon_to_xyz(lat: f64, lon: f64) -> (f64, f64, f64) {
|
|
let x = cos(lon) * cos(lat);
|
|
let y = sin(lon) * cos(lat);
|
|
let z = sin(lat);
|
|
|
|
(x, y, z)
|
|
}
|
|
----
|
|
|
|
|(face, u, v)
|
|
| [source,rust]
|
|
----
|
|
fn face(x: f64, y: f64, z: f64) -> u8 {
|
|
let (x_abs, y_abs, z_abs) = (x.abs(), y.abs(), z.abs());
|
|
let mut id = 0;
|
|
let mut value = x;
|
|
if y_abs > x_abs {
|
|
id = 1;
|
|
value = y;
|
|
}
|
|
if z_abs > value.abs() {
|
|
id = 2;
|
|
value = z;
|
|
}
|
|
if value < 0. {
|
|
id += 3;
|
|
}
|
|
id
|
|
}
|
|
|
|
fn xyz_to_fuv(x: f64, y: f64, z: f64) -> (u8, f64, f64) {
|
|
let f: u8 = face(x, y, z);
|
|
let (u, v) = match face {
|
|
0 => (y / x, z / x),
|
|
1 => (-x / y, z / y),
|
|
2 => (-x / z, -y / z),
|
|
3 => (z / x, y / x),
|
|
4 => (z / y, -x / y),
|
|
5 => (-y / z, -x / z),
|
|
_ => panic!("Face {f} out of bounds"),
|
|
};
|
|
|
|
(f, u, v)
|
|
}
|
|
----
|
|
|
|
|(face, s, t)
|
|
| [source,rust]
|
|
----
|
|
pub fn u_or_v_to_s_or_t(u_or_v: f64) -> f64 {
|
|
if u_or_v >= 0.0 {
|
|
0.5 * (1.0 + 3.0 * u_or_v).sqrt()
|
|
} else {
|
|
1.0 - 0.5 * (1.0 - 3.0 * u_or_v).sqrt()
|
|
}
|
|
}
|
|
|
|
fn fuv_to_fst(f: u8, u: u64, v: u64) -> (u8, f64, f64) {
|
|
let s = u_or_v_to_s_or_t(u);
|
|
let t = u_or_v_to_s_or_t(v);
|
|
|
|
(f, s, t)
|
|
}
|
|
|
|
----
|
|
|
|
|(face, i, j)
|
|
| [source,rust]
|
|
----
|
|
fn st_to_ij(s: f64) -> u32 {
|
|
clamp((MAX_SIZE as f64 * s).floor() as u32, 0, MAX_SIZE_I32 - 1)
|
|
}
|
|
|
|
fn fst_to_fij(f: u8, s: u64, t: u64) -> (u8, u32, u32) {
|
|
let i = st_to_ij(s);
|
|
let j = st_to_ij(t);
|
|
|
|
(f, i, j)
|
|
}
|
|
----
|
|
|
|
|(cellid)
|
|
| [source,go]
|
|
----
|
|
func cellIDFromFaceIJ(f, i, j int) CellID {
|
|
// Note that this value gets shifted one bit to the left at the end
|
|
// of the function.
|
|
n := uint64(f) << (posBits - 1)
|
|
// Alternating faces have opposite Hilbert curve orientations; this
|
|
// is necessary in order for all faces to have a right-handed
|
|
// coordinate system.
|
|
bits := f & swapMask
|
|
// Each iteration maps 4 bits of "i" and "j" into 8 bits of the Hilbert
|
|
// curve position. The lookup table transforms a 10-bit key of the form
|
|
// "iiiijjjjoo" to a 10-bit value of the form "ppppppppoo", where the
|
|
// letters [ijpo] denote bits of "i", "j", Hilbert curve position, and
|
|
// Hilbert curve orientation respectively.
|
|
for k := 7; k >= 0; k-- {
|
|
mask := (1 << lookupBits) - 1
|
|
bits += ((i >> uint(k*lookupBits)) & mask) << (lookupBits + 2)
|
|
bits += ((j >> uint(k*lookupBits)) & mask) << 2
|
|
bits = lookupPos[bits]
|
|
n \|= uint64(bits>>2) << (uint(k) * 2 * lookupBits)
|
|
bits &= (swapMask \| invertMask)
|
|
}
|
|
return CellID(n*2 + 1)
|
|
}
|
|
----
|
|
[source,rust]
|
|
----
|
|
const FACE_BITS: u64 = 3;
|
|
const NUM_FACES: u8 = 6;
|
|
const MAX_LEVEL: u64 = 30;
|
|
const POS_BITS: u64 = (2 * MAX_LEVEL) + 1;
|
|
const MAX_SIZE: u64 = 1 << MAX_LEVEL;
|
|
const WRAP_OFFSET: u64 = (NUM_FACES as u64) << POS_BITS;
|
|
|
|
fn fij_to_cellid(f: u8, i: u32, j: u32) -> u64 {
|
|
let mut n = u64::from(f) << (POS_BITS - 1);
|
|
let mut bits = u32::from(f & SWAP_MASK);
|
|
|
|
let mut k = 7;
|
|
let mask = (1 << LOOKUP_BITS) - 1;
|
|
loop {
|
|
bits += ((i >> (k * LOOKUP_BITS)) & mask) << (LOOKUP_BITS + 2);
|
|
bits += ((j >> (k * LOOKUP_BITS)) & mask) << 2;
|
|
bits = LOOKUP_POS[bits as usize] as u32;
|
|
n \|= ((bits >> 2) as u64) << ((k * 2 * LOOKUP_BITS) as u64);
|
|
bits &= u32::from(SWAP_MASK \| INVERT_MASK);
|
|
|
|
if k == 0 {
|
|
break;
|
|
}
|
|
k -= 1;
|
|
}
|
|
n * 2 + 1
|
|
}
|
|
----
|
|
|
|
|(number, word1, word2, word3)
|
|
|
|
|
|
|
|===
|
|
|
|
== Decoding
|
|
[%header,cols="m,a,"]
|
|
|===
|
|
|Step |Formula |Description
|
|
|
|
|(number, word1, word2, word3)
|
|
|Given
|
|
|
|
|
|
|
|(cellid)
|
|
|
|
|
|
|
|
|
|
|(face, i, j)
|
|
|
|
|
|
|
|
|
|
|(face, s, t)
|
|
|
|
|
|
|
|
|
|
|(face, u, v)
|
|
|
|
|
|
|
|
|
|
|(x, y, z)/Point
|
|
|
|
|
|
|
|
|
|
|(lat, lon)
|
|
|
|
|
|
|
|
|
|
|===
|
|
|
|
== Wordlist
|
|
|
|
++++
|
|
<style>
|
|
#header, #content, #footnotes, #footer {
|
|
max-width: unset !important;
|
|
}
|
|
.hll {
|
|
background-color: #ff0;
|
|
}
|
|
</style>
|
|
++++
|