Misaligned polygons, not perfect hexagons. Some pentagons. Catering for projection

Portur commented 5 years ago

Hi,

Im trying to incorprate your library on a number of solutions which require realtime translations between hex ids and geojson multi/polygons.

h3.h3SetToMultiPolygon(["85291a6ffffffff"],true)

returns

[[[[-121.87310260648961,36.48355301296484],[-121.82059177712684,36.56646154014561],[-121.88144909358076,36.64149027277887],[-121.99481876336013,36.63355254199253],[-122.0471691328904,36.550641568925464],[-121.98631059624982,36.4756707384872],[-121.87310260648961,36.48355301296484]]]]

No problem with that. The issue however is displaying this now results in an askew/misrepresented polygon on a map.

The map is in EPSG:4326. Geojson.io

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {
        "color": "blue"
      },
      "geometry": {
        "type": "MultiPolygon",
        "coordinates": [
          [
            [
              [
                -121.87310260648961,
                36.48355301296484
              ],
              [
                -121.82059177712684,
                36.56646154014561
              ],
              [
                -121.88144909358076,
                36.64149027277887
              ],
              [
                -121.99481876336013,
                36.63355254199253
              ],
              [
                -122.0471691328904,
                36.550641568925464
              ],
              [
                -121.98631059624982,
                36.4756707384872
              ],
              [
                -121.87310260648961,
                36.48355301296484
              ]
            ]
          ]
        ]
      }
    }
  ]
}

Is this correct?

Portur commented 5 years ago

Just to be clear, the expectation is an equal volume/shape hex (such as this module by Turf)

nrabinowitz commented 5 years ago

This appears to be working as expected. In order to divide the world into stable cells that have low shape and area distortion, the H3 grid doesn't work like a screen-based or local hex binning algorithm with screen-aligned hexagons.

Key issues to be aware of:

The alignment of the cells will change in different parts of the world.
Particularly at coarse resolutions, hexagons may appear distorted at northern or southern latitudes when shown on a Mercator projection (as in web maps). This is a function of the projection, not the H3 system.
H3 cells are not exactly equal size or equal area, though they have low shape and area distortion.
There are 12 pentagon-shaped cells at every resolution. These are centered in water, and can be ignored for many use cases.
Some cells (on the edges of the icosahedron used to create the grid) are subject to distortion, which adds additional vertexes on one or two edges. Hexagon cells (in the topological sense, with 6 neighbors) may have up to eight vertices, and pentagon cells may have 10.

Portur commented 5 years ago

see update below

Would a hex graticule not have zero distortion on a perfect sphere?

As I understand it, the hex grid allows for exact uniform distances between neighbouring cell distances, at a certain resolution, for n neighbours. If all hex polygons are askew as the one above, they won't sync up with a round trip of the earth. You won't end up where you started. Meaning a hex grid won't line up at the edges and poles. i.e. this diagram is thus incorrect

The alignment of the cells will change in different parts of the world.

Particularly at coarse resolutions, hexagons may appear distorted at northern or southern latitudes when shown on a Mercator projection (as in web maps). This is a function of the projection, not the H3 system.

This would only affect shrinking in the y-axis as you get closer to the poles, no?

H3 cells are not exactly equal size or equal area, though they have low shape and area distortion.

Maybe I misunderstand. I thought all cells are equal area/size/shape/orientation at a specific resolution.

There are 12 pentagon-shaped cells at every resolution. These are centered in water, and can be ignored for many use cases.

I'm not sure I follow here, how would a hex polygon over water differ from one on land? And as I understand these are hexagons, sevon of them if you count 1 parent and it's neighbours.

Update

Im leaving the above as this was my initial train of thought and my help others.

The hex grid is not calculated from a perfect sphere.

I went though the demonstrations and examples on observable. You are correct. I specifically chose the h3 index to avoid distortion but wasn't aware it was only minimized with h3, not avoided.

One of the videos clearly shows this.

And also showing the cases of areas over water vs land.

Thank for your answer(s)

Portur commented 5 years ago

More info this gist

and this video

nrabinowitz commented 5 years ago

H3 is based on a perfect sphere, but a sphere cannot be tiled with hexagons. This video goes into detail on the construction of the grid: https://youtu.be/wDuKeUkNLkQ

curran commented 3 years ago

I have a use case where the location on the globe does not matter, and one of my goals is to minimize the distortion of the hexagons.

Based on this screenshot in https://github.com/uber/h3/issues/136, I have determined roughly the center point of one of those triangles to be (75.326508, 141.286197).

Original screenshot.

Best guess location of triangle center.

My hexagons before, at (0,0):

My hexagons before, at (75.147338, 142.868226):

Finishing touch: rotate the projection by -2.4 degrees for vertical alignment:

If there is a way to find out the exact center of one of those triangles, I would be keen to know about it. I did a quick search through the codebase but was not able to locate where these geometries are defined.

isaacbrodsky commented 3 years ago

I don't think the library directly exposes this, but it should be possible to extract this from the library. The centroid of the triangle should be the centroid of the center cell on that face; in the C library this could be computed using internal functions as:

int res = 0;
for (int f = 0; f < NUM_ICOSA_FACES; f++) {
    FaceIJK fijk = {f, {0, 0, 0}};
    LatLng latLngRadians = {0, 0};
    _faceIjkToGeo(&fijk, res, &latLngRadians);
    // print latLngRadians
}

In order to do this from JavaScript you would need to get the H3 indexes these FaceIJK&res values represent and call h3ToGeo. Edit: here are the indexes:

8021fffffffffff
8005fffffffffff
800ffffffffffff
8035fffffffffff
803ffffffffffff
8065fffffffffff
8033fffffffffff
8049fffffffffff
8081fffffffffff
8097fffffffffff
8073fffffffffff
805dfffffffffff
808ffffffffffff
80c1fffffffffff
80abfffffffffff
80bffffffffffff
80b5fffffffffff
80d3fffffffffff
80effffffffffff
80e5fffffffffff

nrabinowitz commented 3 years ago

See https://observablehq.com/@nrabinowitz/flat-h3-grid-via-gnomonic-projection

The faceCenterGeo has the center of each face.

curran commented 3 years ago

Amazing! Thank you so much 🙏

Sulorb commented 10 months ago

Finishing touch: rotate the projection by -2.4 degrees for vertical alignment:

How did you rotate the hexagons please? Mine are not perfectly aligned and i'd like it like that.

nrabinowitz commented 10 months ago

@Sulorb This isn't likely to work in most cases, and it's just a visual adjustment, not a change to the grid. The H3 grid has fixed geographic positions, so if you'd like the cells in some area to be vertically aligned, you'd have to rotate the map, not the grid. The rotation you'd need would depend on your position on the globe, as different areas of the globe have differently aligned hexagon cells.

In general, if having perfectly aligned cells matters to your use case, H3 isn't a good fit - you'd be better off with an ad-hoc hex bin, such as those created by GIS software, or a visual hexbin like the one Deck.gl provides.

uber / h3-js

Misaligned polygons, not perfect hexagons. Some pentagons. Catering for projection #59

Update