2

Problem: Spheres cannot be tesselated using only hexagonal tiles.

Goal: Create a globe map, made of discrete hexagonal fields.

Requirements:

a. Graphic representation of a globe/sphere/planet.

b. Tesselate area into hexes.

c. Hexes may contain something.

d. The number of tiles should be between 1 000 and 10 000.

e. A reasonable amount of inaccuracy is okay.

Idea:

  1. Create an undirected graph which will represent the hexes. Because hexes must always have exactly 6 neighbors, the graph needs to be 6-regular and contain 1 000 < N < 10 000 vertices and 3N edges (from the handshaking lemma). It can be stored as an adjacency matrix with pointers to vertex instances.

  2. The vertex instances are populated with information. For instance, in a game, this might be units.

  3. Visual representation: No screen can show a whole globe at once. So, to show a part of our globe, we first select the vertex that should be in the middle of the display and display it as a hex. Then, from the adjacency matrix, we pull up its immediate neighbors and position them around as hexes. For each of these neighbors, we pull up the next level of neighbors, and so on, until the screen is filled.

Questions:

I Is there an algorithm which can be used to construct a graph described in 1.?

II Can I prove that up to a selected neighbor depth, no conflicts will arise which will make a graphic representation impossible? Obviously, no conflicts will arise for a display depth of at least 1 + 6 hexes. 

if I&II:
    Do you think the described approach is promising enough to try and implement?
Zubo
  • 1,543
  • 2
  • 20
  • 26
  • 2
    look here http://stackoverflow.com/a/29139125/2521214 it is almost the same problem but not exactly the same. The output could be interesting for you – Spektre Apr 18 '15 at 07:55
  • @Spektre thank you for the wonderful link, it basically mirrors our discussion in real life. However, the whole point of this question is to somehow avoid pentagons and to map the whole sphere, by actually **not creating a projection or tesellation**. As long as the attempt goes through tesselating a sphere, it cannot produce the desired result because it is proven to be impossible. I guess I could ask whether or not my proposed graph way is fundamentally different from sphere tesellation. The link is very useful in terms of code and reusability! – Zubo Apr 19 '15 at 10:29

1 Answers1

1

Nobody ever answered, but the answer is that this is impossible. The Euler characteristic of a finite graph covering the sphere has to be 2 (see http://en.wikipedia.org/wiki/Euler_characteristic for the Euler characteristic) and the Euler characteristic of a graph that is built out of hexagons is always 0.

You have to somewhere have shapes of a different size.

btilly
  • 43,296
  • 3
  • 59
  • 88
  • That goes for full sphere but title states partial sphere ... And there I am not so sure It depends on the sphere coverage and number of layers/tiles .... the cylindric projection is workable for almost whole surface but the tiles are different in size. for same sized tiles I guess the pentagons can be shifted out of covered surface ... if the coverage is not too large – Spektre Apr 24 '15 at 07:05
  • @Spektre As I understood it from the question and comments, the goal was to use a hex representation in any region based on a single graph representation that divided the whole sphere into hexagons. That you can't do. You can do any region with a projection. You can do the whole sphere if 12 of those hexagons are changed to pentagons. But in comments it was made clear that Zubo didn't want to do either of those things. – btilly Apr 24 '15 at 17:42