Covering Earth with Hexagonal Map Tiles

Many strategy games use hexagonal tiles. One of the main advantages is that the distance between the center of any tile and all its neighboring tiles is the same.

I was wondering if anyone has any thoughts on marrying a hexagonal tile system with the traditional geographic system (longitude/latitude). I think it would be interesting to cover a globe with hexagonal tiles and be able to map a geographic coordinate to a tile.

Has anyone seen anything remotely close to this before?

UPDATE

I'm looking for a way to subdivide the surface of a sphere so that each division has the same surface area. Ideally, the centers of adjacent sub-divisions would be equidistant.

Take a look at vraid/earthgen; it uses hexagons (plus a few pentagons) and includes source code (see planet/grid/create_grid.cpp).

As of 2018 a new version is available based on racket.

Well, lots of people have made the point that you can't tile the sphere with hexagonal tiles - maybe you are wondering why.

Euler stated (and there are lots of interesting and different proofs, and even a whole book) that given a tile of the sphere in x Polygons with y Edges total and z vertices total (for example, a cube has 6 polygons with 12 edges and 8 vertices) the formula

>x - y + z = 2

always holds (mind the minus sign).

(BTW: it's a topological statement so a cube and a sphere - or, to be precise, only their border - is really the same here)

If you want to use only hexagons to tile a sphere, you end up with x hexagons, having 6x edges. However, one edge is shared by each pair of hexagons. So, we only want to count 3x of them, and 6x vertices but, again, each of them is shared by 3 hexagons so you end up with 2x edges.

Now, using the formula:

>x - 3x + 2x = 2

you end up with the false statement 0 = 2 - so you really can't use only hexagons.

That's why the classical soccer ball looks like it does - of course modern ones are more fancy but the basic fact remains.

It is impossible to cover a sphere with regular tiles (except for long and thin "orange slices". So the optimal way to pixelize a map, given certain constraints or requirements, is actually a pretty difficult research problem.

One sort of tiling used very often (in astrophysics) is the HEALPIX pixelisation: http://healpix.sourceforge.net/

This pixelization satisfies the equal-area requirement; it's impossible to make everything equidistant, however.

Another pixelization is "GLESP", which has some different properties (and isn't as polished a software package): http://www.glesp.nbi.dk/

The first website that comes to mind is Amit's Game Programming Information and its collection of links on hexagonal grids.

You can't cover a sphere with equal hexagons, but you could cover it with a geodesic, which is mostly hexagons, with 12 pentagons at the vertices of an icosohedron, and the hexagons slightly distorted to make it bulge into a sphere.

Hexagonal tiles are too complicated for regular geometry as applied to geospatial uses. Check out HTM for a similar thing with triangles or google for "Hierarchical Triangular Mesh" for other sources.

Read "Geodesic Discrete Global Grid Systems" by Kevin Sahr, Denis White, and A. Jon Kimerling

You can find it here...

I've just built an R package called dggridR which divides the surface of the Earth into equally sized hexagons for the purposes of binned spatial analysis.

Carsten makes this sound impossible in his answer, but, practically speaking, it's not. By introducing 12 pentagons all the rest of the hexagons fit together without an issue. Since you may have millions upon millions of cells for a highly-resolved grid, you can forget about those pentagons most of the time.

The maths of the transformation are complicated. You can find them in:

• Crider, John E. “Exact Equations for Fuller’s Map Projection and Inverse.” Cartographica: The International Journal for Geographic Information and Geovisualization 43.1 (2008): 67–72. Web.

• Snyder, John P. “An Equal-Area Map Projection For Polyhedral Globes.” Cartographica: The International Journal for Geographic Information and Geovisualization 29.1 (1992): 10–21. Web.

In the background dggridR relies on Kevin Sahr's DGGRID software.

You may also find the following references to be of use:

• Gregory, Matthew J. et al. “A Comparison of Intercell Metrics on Discrete Global Grid Systems.” Computers, Environment and Urban Systems 32.3 (2008): 188–203. CrossRef. Web.
• Kimerling, Jon A. et al. “Comparing Geometrical Properties of Global Grids.” Cartography and Geographic Information Science 26.4 (1999): 271–288. Print.
• Sahr, K. “Hexagonal Discrete Global GRID Systems for Geospatial Computing.” Archiwum Fotogrametrii, Kartografii i Teledetekcji Vol. 22 (2011): 363–376. Print.
• Sahr, Kevin. “Location Coding on Icosahedral Aperture 3 Hexagon Discrete Global Grids.” Computers, Environment and Urban Systems 32.3 (2008): 174–187. CrossRef. Web.
• Sahr, Kevin, Denis White, and A. Jon Kimerling. “Geodesic Discrete Global Grid Systems.” Cartography and Geographic Information Science 30.2 (2003): 121–134. Print.

Getting a sphere to divide into equal parts made with flat surfaces is a tough nut. Because of this, you end up with Geodesic shapes, which are not composed of shapes that can be in turn composed of triangles of equal size. Breaking down all of the hexagons and pentagons into triangles, you end up with triangles that have different interior angles, leading to a loss of symmetry.

The one consolation that I can give you is that all of the shapes will have a limited number of triangles that can be catagorised, which means for a small geodesic, that 5 or 6 triangles can be used repeatedly to describe all of the hexagons and pentagons required for the geodesic. While distances will not be equal from the "center" of each triangle/shape, you can at least divide the handling of each triangle into a discrete case, lending to a potential work-around in code.

The old Traveller roleplaying game used to map planet surfaces as icosahedra (cut open for printing in a book). This produced a big distortion at the corner hexes (they have to become pentagons). You might find some such material when searching for GURPS Traveller.

There are only a few platonic polyhedra that use a single type of polygon to approximate a sphere. Famously the ICOSAHEDRON and the DODECAHEDRON. If you're willing to have a little bit of distortion and a few overlapping points, you can get fair results that would make a game fun. Try THIS LINK, which manages to have nearly equal area for all tiles and pretty consistent tile-distances for circles around the globe.

However none of these map very easily onto the good old geographic, cylindrical longitude/latitude projection system.

One solution is to just super-impose a honeycomb pattern onto the EQUIRECTANGULAR projection map and allow TONS of distortion as you approach the poles LIKE THIS.

Good luck with your research! :)

HEAlpix is the right one if your constraint is to keep equal area when splitting the sphere in pieces (interesting for covering the projected area in the sky the same in the poles as well as in the equator region). You basically split your sphere in 4 each time following either an ring or nested scheme to fulfill the Hierarchical Equal Area constraint. It is also very convenient for 'deploying' FT functions ((iso-latitude property) on the sky for example to study the temperature of CMB modes in Planck or WMAP mission.

It is also implemented in many programming languages.

Furthermore, I should mentioned another one (not equal area though), called Q3C for 'Quad Tree Cube', another sky-partitioning scheme which has other advantages (cone search and x-match)

• https://github.com/segasai/q3c

original paper:

http:// adsabs.harvard.edu/abs/2006ASPC..351..735K

Old question, but:

The other responses are correct in that it is impossible to tile a sphere using only hexagons.

However, a simple(ish) hack is:

Create a 2d "sheet" of hexagons:

and offset them in 3D space from the origin by 1. Then, normalize all of the vertices.

This will give you a "bulging" version of the sheet that has a nice spherical curve to it. The problem is that this will only work if the sheet covers part of the sphere.

One solution is similar to what is used to create an infinite grid floor. As the sphere rotates, when you have moved half a cell, rotate the sphere back once cell in the relevant direction. (For the case of hexagons, the numbers aren't really half a cell, but tied to the dimensions of a hex tile.) This is a little tricky in 3D, but is doable.

I had a similar question in 2D awhile back that may be helpful.

https://gamedev.stackexchange.com/questions/70092/infinite-treadmilling-hexagonal-grid/70341#70341

There is a paper which handles the case of equal area tiling (almost square tiles around the equator) and is relatively easy to pre-compute neighbouring tiles and on which tile a specific set of coordinates falls in. It doesn't fare well with the requirement for equal distance between the vertices though.

Copying here the abstract:

> A new method is proposed to divide a spherical surface into equal-area cells. The method is based on dividing a sphere into several latitudinal bands of near-constant span with further division of each band into equal-area cells. It is simple in construction and provides more uniform latitude step between latitudinal bands than other methods of isolatitudinal equal-area tessellation of a spherical surface.

(I've used its ideas trying to find closest geolocation neighbours from a long list of locations).