jcreed blog > Somewhat-Topology-Preserving Hex Map Reduction

Somewhat-Topology-Preserving Hex Map Reduction

Given a tiling of the plane with hexagons, there is a way of grouping together groups of seven hexes, and thinking of it as its own hex tiling:

This rotates the tiling clockwise by a small angle, but there's a mirror-version of this grouping which rotates counter-clockwise by the same angle, so we can alternate them if we want to iterate and preserve the orientation of the overall picture. (in the limit this yields roughly hexagonal fractals called Gosper regions)

If we have some information stored on the hex map like, for example, which cells are land and which have water, there's a slight annoyance that naturally arises from the fact that we're downsampling, which is that some connectivity information is wrecked.

Imagine that during downsampling we look at the center hex of each group of 7, and let that determine whether the hex in the smaller map is land or water:

The snakey peninsula in the original map, which doesn't connect to the northwest landmass in the original map, now incorrectly does in the smaller map.

A common thing in board games on hex grids is to allow features that exist on the edges of hexes as well as their interior. So let's

  1. Allow there to optionally be a river on any edge between land hexes, and an isthmus on any edge between two water hexes.
  2. During map reduction, place a river (or isthmus) whenever we attempt to create adjacent land (or water) hexes in the small map, but observe that there is no actual land-only (or water-only) path between the centers of the two adjacent 7-hex groups in the original large map that stays within the interiors and boundaries of the 14 hexes in the union of those two original groups.
Here's an example:

I think this reduction step makes good sense even when the large map itself has rivers and isthmuses in it, because step 2's notion of connectivity between 7-hex group centers can take advantage of rivers and isthmuses.

Question: are there any nice lemmas one can prove about this preserving the topology of the original map in some sense? Clearly it's able to delete islands and small lakes, so it can't preserve all topological information, but maybe you can prove that it will only delete islands and lakes, rather than merging two islands or two lakes.

Maybe a Counterexample

This example doesn't behave like I hoped it would:

It's because I stipulated in step 2 above that the connectivity between two 7-hex regions has to be witnessed by a path that lies inside those two regions. If I allowed arbitrary paths, that would have both the disadvantage of it being somewhat slower to compute (but probably not too bad) and also that a big ocean might obliterate an isthmus that inuitively it shouldn't, just because one side of the isthmus is connected to the other allll the way around the world.