Questions & Clarification on Coordinate Systems

[douglasg14b]

A few questions & clarifications:

Unfortunately I do not have a background in mathematics, please be patient with me.

---

The gist of my use case is a geo-location based mobile game that uses a hexagonal grid to represent the world, something H3 appears to exactly solve for. Though, this use case necessitates the need to have a coordinate system that can uniquely identify each cell in the global grid for a variety of reasons. I am having a hard time figuring out how to obtain coordinates from the cells of an H3 grid.

H3 Coordinate Systems: https://h3geo.org/docs/core-library/coordsystems Hexagonal Coordinate Systems: https://www.redblobgames.com/grids/hexagons/#coordinates

I marginally familiar three coordinate systems for hexagonal grids:

• Offset Coordinates
• Cube Coordinates (3 axes 120 degrees apart)
• Axial Coordinates (Essentially cube coordinates sans an axis) [What I am aiming for here]

In the H3 docs, it mentions:

• IJK Coordinates
  • This is noted as being the 3 coordinate axes spaced 120° apart which seems like a cube coordinate system. However the example picture's coordinates don't seem to line up with the expectation of i+j+k == 0.
  • What is this if not cube coordinates?
  • Are these globally unique?
  • How can this coordinate be obtained for a given H3Index?
• FaceIJK Coordinates
  • Simply the IJK coordinates, but centered on each face. And I assume constrained to each face. Definitely not what I'm after.
• Hex2d Coordinates.
  • [x,y] coordinates for the IJK coordinates with the +x axis aligned on i axis. This appears to be what I am looking for.
  • Are these essentially Axial Coordinates?
  • Is there a specific conversion expectation to go from IJK to Hex2d?
  • How can this coordinate be obtained for a given H3Index?
• Local IJ Coordinates.
  • At first this looked promising, until I read local coordinates are only valid near the origin.. Which points out that these coordinates are really only valid within the same base cell.

    ---

TL;DR: How can I obtain cartesian coordinates for each cell that are globally unique?

[dfellis]

For your exact question, the h3ToGeo function does this.

[douglasg14b]

I should clarify, since you are right, that provides lat/long which IS how I can get cartesian coordinates for hexagons. But I don't think that will work in my case. Lat/long wasn't something I thought to address when writing this.

I need a way to get [0,1], [0, 2], [500, 79136]....etc To feed into noise functions for procedural generation, unless I can guarantee that the lat/long for each neighboring cell has a value that allows me to iterate each by only 1 on each axis.

Then again, I could be missing the obvious solution.

[dfellis]

To expand a bit on this, hexagons don't map onto a sphere, so there can't be a singular grid system for the entire globe. H3 almost accomplishes this by being a grid system on equilateral triangles and then arranging them into an icosahedron such that the points of the icosahedron map to 12 special pentagons, leaving the rest to be hexagons.

The only 2D grid that can work is isolated to one of the icosahedron faces. It would be possible to unfold the icosahedron into a Dymaxion Map and then apply the right transformations to allow traversal between icosahedron faces, but that would lead to "edge of the world" problems where you can define hexagons that map to nothing. It can work if you know you are constrained to land only, though, and it is one of the things that has been discussed to potentially offer, but with all of those caveats above.

However, you have not explained what exactly you are trying to accomplish with the game. I am going to make some educated guesses:

1. The user has GPS coordinates from their phone. This can be translated to H3 with geoToH3.
2. You need to look up relevant data to show on the map for the player. This can be accomplished with kRing to get the indexes to query your server, with the size based on how far out the map is zoomed, the resolution you choose to operate on, and so on.
3. You need other operations, like pathing (h3Line), hexagon neighbors (kRing of 1 to get, h3IndexesAreNeighbors to check), outlines for rendering (h3ToGeoBoundary), calculating hex-level distances for attack ranges (h3Distance), etc.

I don't see the explicit need for a 2D grid for the game logic. The various APIs of H3 are designed to give you most of the optionality of a grid despite that being impossible on the sphere. If there is an operation that we have missed, we would be glad to hear about that and add it, but the exact request is technically not possible.

[dfellis]

I should clarify, since you are right, that provides lat/long which IS how I can get cartesian coordinates for hexagons. But I don't think that will work in my case. Lat/long wasn't something I thought to address when writing this.

I need a way to get [0,1], [0, 2], [500, 79136]....etc To feed into noise functions for procedural generation, unless I can guarantee that the lat/long for each neighboring cell has a value that allows me to iterate each by only 1 on each axis.

Then again, I could be missing the obvious solution.

You responded while I was writing that up, give me a sec.

[douglasg14b]

Sorry about that! I made edits while you where writing

The distortion of using H3 on a mercator projection is completely acceptable to me, and the "edge of the world" problems are acceptable as well as this game is constrained to places people can physically go with cell reception. The likelihood of encountering one of the pentagons is extremely low, and in that instance the player can just deal with it not working right at that location.

[dfellis]

I need a way to get [0,1], [0, 2], [500, 79136]....etc To feed into noise functions for procedural generation, unless I can guarantee that the lat/long for each neighboring cell has a value that allows me to iterate each by only 1 on each axis.

So procedural generation just requires that you have a repeatable seed input. The H3 index itself can act as that seed. The indexes are just 64-bit numbers starting with a base cell and then a series of 3-bit subsections to index the seven subdivisions 0-6 (with 7 indicating not-used). You could break it up if you want/need to (eg, have cells nearby more likely to have similar procedurally generated data) but the ID itself would work fine as a seed.

[dfellis]

If you want to have that property, that cells nearer to each other are more likely to be similar, there are two approaches: you can key on base cell and then each child sub division 0-6 is equivalent to either "staying put" or "moving in a direction" and you can treat that as IJK or IJ, etc.

However, H3 is also has the property that values that are close to each other numerically are also usually close to each other spatially (it does have discontinuities, but that would exist with any conversion of a 2D plane to a 1D index), so if you don't need that level of precision, simple ordering could suffice.

[douglasg14b]

I greatly appreciate your guidance on this. Unfortunately I am not prepared to roll my own noise algorithms, and am simply used pre-existing ones that I have manipulated to get the map features I am aiming for.

The trouble with pre-existing functions like perlin & simplex noise is that these functions expect x,y coords (Or x,y,z) to generate their noise, the relation those coordinates have with each other is their closeness. This should describe the point better than I can: https://en.wikipedia.org/wiki/Perlin_noise#Algorithm_detail

I don't believe this could function with coordinate values that are significantly spaced, or that don't have closeness to each other in a consistent manner.

---

Lets shift direction and address a couple items only within the scope of H3, so I can get some facts straight.

The H3 docs mention that the IJK coordinates are used internally by H3. It also implies that the Hex2d coordinates are derived from those. Are these obtainable in some way? And is their uniqueness constrained to each icosahedron face, or to the entire grid?

The uniqueness being constrained to just a face would still work for my case (Not perfect, but it would still work), though I'd need to clarify how H3 handles the coordinates for those hexagons that are in multiple faces.

[dfellis]

First, on your questions about H3: the algorithm is (simplified a bit) (lat, lng) -> (x, y, z) (to spherical coordinates), then (x, y, z) -> (x, y) + icosahedron face id (to hex2d, per icosahedron) then (x, y) + icosahedron -> FaceIJK (icosahedron face + (i, j, k) (where IJK here is a 2D coordinate system such that all values are positive and therefore storable inside of an integer) and finally to the H3 Index where it is subdivided such that each 3-bit segment stores a value 0-6 corresponding to one of the IJK subdivision+traversal steps.

It is possible to rederive the original XYZ spherical coordinates from the H3 cells, but involving H3 at all would be a waste of your time, as the conversion from (lat, lng) -> (x, y, z) is literally just this:

void _geoToVec3d(const GeoCoord* geo, Vec3d* v) {
    double r = cos(geo->lat);

    v->z = sin(geo->lat);
    v->x = cos(geo->lon) * r;
    v->y = sin(geo->lon) * r;
}

But if you did go with spherical coordinates, you'd need a 3D perlin noise algorithm and some way to sample out from the unit sphere of that noise to then generate what you're actually after.

If the main thing you're after from H3 is the ability to generate perlin noise on a sphere, I would have to point you to the Google S2 project that this was was inspired by. You would be working with square-ish indexes, and while you do still have the issue that boundaries along the 6 cube faces would have weird traversal rules and odd boundary behavior for the perlin noise if you unfolded that, it could be possible to simply compute the noise 6 times for each unfolding and sum them together and divide by 6 to avoid it.

It should be possible to port a perlin noise function to H3 (unfold the icosahedron centered on each face, then use IJ coordinates then translate back), but it would still have the same unfolding problem, except now you have 20 icosahedron faces to deal with so your function would be ~3x slower to accommodate the boundary problem.

Finally, the fastest way to generate perlin noise on the sphere is to just use (r, theta, phi) with a fixed r you can ignore, and some sort of consideration for the antimerdian problem if you care about that at all (it's also mostly over water). (EDIT 2: Which is basically lat, lng.)

Edit: I missed one last part about how H3 handles hexagons in multiple faces: there are a fixed set of these and they are assigned to one of the two bisecting faces following a rule to make sure all faces have an equal number of hexagons. I don't recall the rule off the top of my head, but the H3 code doesn't compute it, either, the 122 base cells are simply stored in the code with which face they are associated with.