Fast, Constant-Time Sphere Indexing | Hacker News Reader

Fast, Constant-Time Sphere Indexing

donw.io

117 pointsstrangecasts9 comments

Spatial subdivision with fast indexing on a sphere is quite useful for mapping. We want map tiles to be of close to constant size and shape, and find the tile for any point on Earth.

Usually, subdividing the faces of a Platonic solid is the way to go. This post describes tessellation of triangles on the faces of an octahedron. The dual approach is squares on the faces of a cube. A good implementation of this is s2 [1].

[1] http://s2geometry.io/

I used this a lot when I worked at Uber. Very similar but maps to variably sized Hexagons which were nice for things like surge/dispatch algorithms: https://github.com/uber/h3

In case somebody is interested, this [1] is the Microsoft Research paper that introduced this schema under the name Hierarchical Triangular Mesh. Among other things it provides an analysis of the distortion and discusses many operations one may want to perform with such a grid with a focus on GIS applications.

And in case someone is interested in the Spherical Fibonacci Mapping mentioned in the article, here [2] is a non-broken link to the paper.

[1] https://www.microsoft.com/en-us/research/wp-content/uploads/...

[2] https://docplayer.net/40493580-Spherical-fibonacci-mapping.h...

I actually used HTM in a project a few years back.

I had a 360x180 sphere of values, and I needed to rotate the sphere in some combination of translations. I did this by converting the az/el/value triplets to Cartesian XYZ and multiplying by a rotation matrix.

However, when I tried to convert the translated values back to a rotated az/el/value result, the results broke due to what was effectively lat/lon narrowing (ie, 1x1-degree cells are smaller nearer the "poles", so the rotations didn't map evenly).

After research, I settled on using HTM. I was able to borrow the C code from some MySQL extension that implemented HTM (looks like it's at https://github.com/smonkewitz/scisql ), then use that math to more reliably convert the rotated values back to an appropriate az/el/value result.

Still one of the neatest problems I ever solved.

(1) Nice interactive demos of the things being discussed, with live code.

(2) Math being directly applied to near-hardware level, the GPU, with a good explanation.

What's not to love?

I first parsed the title as (Fast, Constant) Time-Sphere indexing, and thought of http://timecube.2enp.com/.

Anyway, neat article, the interactive diagrams are very nice.

What did I just read?

There is a neat way of doing this style of indexing using barycentric coordinates: https://www.shadertoy.com/view/MlVfzG

Hm, I wonder what the algebra would look like if done with Cl(3)/G(3) operations. I think that would be a great exercise to understand geometric algebra and see if it's powerful enough (there's a lot of projecting vectors onto planes, which is trivial in that formalism)

Reply on news.ycombinator.com