Monday, March 12, 2012

[ffdeqrep] Geodesic global mesh

Project an icosahedron on the globe.  Consider the vertices to be the primary (level 1) poles for pole based addressing.

Divide each triangular face into 4.  Doing this (in later levels) might be nontrivial to avoid distortion.  The goal is to always have poles as globally evenly spaced out as possible.  The newly defined vertices are the secondary (level 2) poles.  Repeat to a desired degree of granularity.  The earth gets covered in a triangular mesh resembling a geodesic dome.

The inspiration was to avoid distorted graticule zones near the North and South Poles for xkcd geohashing.  I think level 7 poles are spaced about 1 degree apart (derived from the dihedral angle of a dodecahedron).  Given a latitude and longitude, determine the nearest level 7 pole.  Sample a random point in the (hexagonal or pentagonal) Voronoi cell around the pole, or (simpler) sample a random point in a disc around the pole.  Regions will overlap.  What is the minimum radius of a circle around a pole such that any point on earth has a chance of being selected?

A cleverer way to exactly consume all the bits of the hash is to define the graticules as the triangles themselves instead of the Voronoi cell around a vertex.  After deciding on a starting triangle, divide the triangle into 4 as above, and consume 2 bits of hash to select one of the 4 triangles.  Repeat recursively.

For a globalhash, one can start with an octahedron, first consuming 3 bits to select a face, then continuing recursively as above.

One might also consider starting from a cube, cuboctahedron, or rhombicuboctahedron (or snub cube, or improved snub cube).  Then squares get divided into 4, which is somewhat more natural.

No comments :