A few years ago, Uber published a grid system called H3.
H3: Uber's Hexagonal Hierarchical Spatial Index
I have to say, I dislike most of Uber's behavior. They seem to put a lot of effort into normalizing labor violations and undermining public transit efforts. But I still like thinking about this hexagonal grid system that they published.
If you want to learn how H3 works, you should just go read or watch Uber's explanations (linked above), but I'll try to give my own interpretation here in case you don't want to do that or it goes offline in the future.
The goal of H3 is to assign an address to any arbitrary location in the world. H3 uses hexagonal areas to do this. H3 provides several different resolutions, so you can have large hexagons that cover large areas, or very small hexagons for small areas.
Step 1: Map the globe to an icosahedron (20-sided platonic solid).
Step 2: Split each triangular surface of the icosahedron into some hexagons and partial hexagons, in a specific pattern.
The initial layout of hexagons on one face of the icosahedron
Step 3: If you want a finer resolution, split each hexagon into seven smaller hexagons (one in the center of the "parent" hexagon, with six around its edges). Rotate the system by 15°. (This allows the "child" hexagons to fit more fully within each parent.)
Hexagons after first sub-division
Step 4: Keep sub-dividing until you reach the resolution that you want. Rotate each finer resolution by -15° or 15° (alternating) from its parent.
Hexagons after second sub-division
That's the general idea. I won't go into the details of how each area is addressed. I'm mostly interested in playing around with shapes.
I think this is a pretty neat system. I like the "smoothness" that hexagons offer over triangular grids or square grids. Their documentation would express that more precisely using language something like this:
However, I'm sad about the alternating 15° and -15° rotations. This is a surprisingly effective way to maintain the overall grid pattern from one resolution to the next, but it's a complexity that I don't like aesthetically.
Also, rectangles are just simpler to work with than hexagons. Fewer angles, fewer lines.
It's a neat coincidence that rectangles arranged in a brick-work pattern have some of the same properties as a hexagon grid.
Can we take the general H3 idea and rework parts of it to fit into a rectangular brick-like grid instead of a hexagon grid? The answer seems to be "kind of".
First, what size of rectangles can we use? We could use any size and shape if we didn't care about supporting multiple levels of resolution. But, if we want to "zoom in" on our grid without adding distortion at each level, we will need rectangles that match the layout of regular hexagons. That is, we need rectangles where the center point of each rectangle on the rectangular grid matches the center point of a hexagon on the hexagonal grid.
If we measure the width of a regular hexagon (from one edge to its opposite edge) and the height (from one corner to its second neighbor, measured perpendicular to the width measurement), we get a ratio that is roughly 23:20 or 231:200.
Measuring a rectangle for a hex grid
Now we can reposition this rectangle to the center-point of the hexagon, and add its neighbors, and we have the start of a rectangular grid that shares center-points with a regular hexagonal grid.
Rectangles overlaid on hex grid
For comparison, I've laid out the rectangular grid on an icosahedron face.
Intial layout of the rectangular grid
Rectangular grid after first sub-division
Rectangular grid after second sub-division
So, unfortunately, we can't get away from the 15° rotations between alternate levels of resolution. If we want to preserve the behavior where each cell has a "child" at its center surrounded by six neighbors, then we need to preserve the same center-points that H3 uses, which means placing rectangles on a diagonal.
What's worse is that rectangles make a mess out of the child/parent edges. In the hexagonal H3 system, there are six tiny triangles in a child that aren't within its parent, and six tiny triangles in a parent that aren't within its child. All of the triangles are the same size and shape, just rotated differently.
In the rectangular grid, we have eight (I think?) shapes that are in a child but not a parent, and eight that are in a parent not a child. These come in four different sizes. Some are triangles and some are quadrilaterals. None are regular.
I don't know where else to go with this. It seems to be a dead end.
I don't know. I'm thinking about things like game maps. Mostly I just wanted to move some shapes around to understand what might work or not.
emptyhallway
2021-08-27
