Covering Earth with Hexagonal Map Tiles [closed]

Question

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.

Retouch

Also, you want to remember that earth is pretty far from spherical. In most cases this isn't a big deal, but if you want to match tiles to the surface, the fact that it's not a sphere is going to eventually come up. – Protium

@Gnubie: Did you get here from Mathoverflow? =D – Pother

@Vandermonde: How did you guess? ;-) – Ashbey

I think you could have 12 lone pentagons and a whole bunch of pairs of a pentagon right beside a heptagon. Each pair of a pentagon right beside a heptagon would be a point dislocation. Because Earth is so big, the pentagon and the heptagons would be a small fraction of the tiling. The hexagons would almost all be very nearly the same size and nearly perfect. – Peaslee

Uber H3 is a hexagonal grid system for Earth: uber.com/blog/h3 – Creedon

Answer 1

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.

Minsk

Interesting. Is there an explanation of the algorithm other than reading the source? Is there a way to obtain the longitude and latitude of each tile? – Retouch

@Retouch Icosahedron subdivision. Start with an icosahedron. Subdivide each face into 4 triangles. Rinse, repeat. At the end, no matter how many times you subdivide (tessellate), you'll still only have 12 pentagons (from the vertices of the original icosahedron.) Lat/Long are obtained by taking the 3D coordinates of a given tile and calculating their angle relative to the equator and prime meridian. – Viscid

@Viscid This is a great suggestion and I've tried using it! However, the numbers don't seem to add up. I started with an icosahedron and tesselated 3 times. That's 20*4^3 = 1280 faces. Generating 12 pentagons at the original vertices leaves me with 1280 - (12*6) = 1220 faces. That number isn't divisible by 6. Is my math off? I hope my math is off... – Castle

@Castle Contributing factors: each of the original 20 faces contribute to at least (I think) three pentagons. I'll think on this for a bit. Look at a soccer ball in the mean time. (Not kidding.) – Viscid

@Castle So, think of it this way: the icosahedron has 12 vertices, and therefore 12 pentagons, but only 20 faces. – Viscid

@Viscid I actually scripted the thing in Blender. This is what the tesselated icosahedron looks like and this is what it looked like when I turned the triangles around the original vertices into pentagons and the groups around those into hexagons. You can see that there is no way to fill in the rest of the triangles with hexagons. – Castle

@Viscid I think I figured it out: We've been thinking about the tesselation wrong. If you subdivide each triangle into 4 triangles, you don't end up with a soccer ball, you end up with this. Instead of cutting each edge in half we need to cut them in three. That way you end up with three triangles around a hexagon instead of four triangles. – Castle

Answer 2

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 6*x edges. However, one edge is shared by each pair of hexagons. So, we only want to count 3*x of them, and 6*x vertices but, again, each of them is shared by 3 hexagons so you end up with 2*x edges.

Now, using the formula:

x - 3*x + 2*x = 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.

Aconcagua

interesting. any links for that proof? – Tuition

A lot hinges on the definition of "hexagon" on a curved surface. You've made the assumption that vertices must be shared by 3 hexagons. Perhaps some could be coaxed into 2 or 4? For example, divide the equator into six lengths. These "edges" are straight for a spherical surface. So two hemispheres tile Earth into two "hexagons". Sure, this feels wrong, but can you come up with a definition of a curved-surface hexagon that doesn't apply to a hemisphere? – Monolith

Answer 3

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/

Unscreened

I had never heard of that one. Pretty awesome. – Tuition

very nice, and never heard about it before – Saccharometer

dumb question time: Is this why we see Geodesics being popular on college campi ( nominative plural of campus ) - that it is thought to be unsolvable or known to be unsolvable leads to known solutions in Geodesics ... ( ? ) I always wondered about those architect students who could work the issue and wish to identify "pretty difficult research problem"(s) so as to avoid deep excursions in time wasters that have no solution. – Diaphysis

upvoted for sharing the healpix method – Voronezh

Answer 4

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

Stockton

A newer and more relevant article from Amit: here – Crosspatch

Answer 5

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.

Exarchate

An icosohedron is a 20-sided die, like for D&D. Each vertex has 5 triangles. If you nip of that corner, it will be a pentagon, and the remainder of each triangle is a hexagon. Divide that hexagon into smaller hexagons as needed. – Exarchate

Or think of a soccer ball: it's made up of pentagons each of which is surrounded by hexagons. Or, look here for the truncated icosahedron: en.wikipedia.org/wiki/File:Uniform_polyhedron-53-t12.png – Strew

@Exarchate - this is by far, the best visualization of that kinda mesh I've heard of. – Referendum

@ErickRobertson That's awesome. Is this something you're writing? – Retouch

Answer 6

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.

Tuition

Doesn't that just mean we need better abstractions before they become usable for geospatial purposes? I've just released an R package that handles this rather nicely. – Fossa

Answer 7

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

You can find it here...

Lolland

-1 When your whole answer is a reference to another source, I expect you to summarize the source in some way. Tell me why I want to read that document. You have only provided a link, and I think we can do better. – Chapiter

Answer 8

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.

Fossa

Found a link for the last one in this list. "Geodesic Discrete Global Grid Systems" Kevin Sahr, Denis White, and A. Jon Kimerling discreteglobalgrids.org/wp-content/uploads/sites/33/2016/01/… – Nobukonoby

Answer 9

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.

Precipitant

Answer 10

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.

Gunny

Yes and GURPS Space has a standard form for planetary hex maps. Of course it is an abstraction and is pretty coarse/grainy. – Gentle

Answer 11

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! :)

Voronezh

Answer 12

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

Numen

upvoted for sharing the healpix method – Voronezh

Answer 13

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

Viscid

That's an interesting hack indeed. Though it's not really useful for persistent worlds, where hexes should exist on the same coordinates persistently. I DO hope I'm wrong :D – Emmieemmit

Answer 14

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).

Xantha