h3.cells_to_geo/h3shape fails for certain combinations of cells (causes degenerate polygons)

[jorisvandenbossche]

This is probably a bug in the underlying C library, and also probably already reported over there (eg uber/h3#1049), but I thought it might be useful to have an issue here as well (I was looking for existing issue here first, but feel free to close if this is duplicative).

Example, with generating a list of cells through geo_to_cells:

>>> import h3
>>> import shapely
>>> h3.__version__
'4.4.2'
>>> cells = sorted(h3.geo_to_cells(shapely.box(0, 0, 170, 80), res=0))
>>> cells
['8001fffffffffff', '8005fffffffffff', '8009fffffffffff', '800bfffffffffff', '8011fffffffffff', '8015fffffffffff', '8017fffffffffff', '801ffffffffffff', '8021fffffffffff', '8025fffffffffff', '802dfffffffffff', '802ffffffffffff', '8031fffffffffff', '8033fffffffffff', '803dfffffffffff', '803ffffffffffff', '8041fffffffffff', '8043fffffffffff', '804bfffffffffff', '804ffffffffffff', '8053fffffffffff', '8059fffffffffff', '8061fffffffffff', '8063fffffffffff', '8065fffffffffff', '8069fffffffffff', '806bfffffffffff', '8073fffffffffff', '8077fffffffffff']
>>> h3.cells_to_geo(cells)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/joris/conda/envs/geo-dev/lib/python3.11/site-packages/h3/api/basic_str/__init__.py", line 710, in cells_to_geo
    h3shape = cells_to_h3shape(cells, tight=tight)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/joris/conda/envs/geo-dev/lib/python3.11/site-packages/h3/api/basic_str/__init__.py", line 667, in cells_to_h3shape
    polys = [LatLngPoly(*poly) for poly in mpoly]
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/joris/conda/envs/geo-dev/lib/python3.11/site-packages/h3/api/basic_str/__init__.py", line 667, in <listcomp>
    polys = [LatLngPoly(*poly) for poly in mpoly]
             ^^^^^^^^^^^^^^^^^
  File "/home/joris/conda/envs/geo-dev/lib/python3.11/site-packages/h3/_h3shape.py", line 58, in __init__
    raise ValueError('Non-empty LatLngPoly loops need at least 3 points.')
ValueError: Non-empty LatLngPoly loops need at least 3 points.

In this case, there are some cells that cross the antimeridian. Although when I remove those, it still fails (viz of the remaining cells):

import numpy as np

def crosses_antimeridian(cell):
    lons = np.asarray(h3.cell_to_boundary(cell))[:, 1]
    return np.abs(np.diff(lons) > 180).any()

mask = np.array([crosses_antimeridian(cell) for cell in cells])
print(mask.sum())  # 3
cells_without_antimeridian = np.array(cells)[~mask].tolist()

>>> h3.cells_to_geo(cells_without_antimeridian)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/joris/conda/envs/geo-dev/lib/python3.11/site-packages/h3/api/basic_str/__init__.py", line 710, in cells_to_geo
    h3shape = cells_to_h3shape(cells, tight=tight)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/joris/conda/envs/geo-dev/lib/python3.11/site-packages/h3/api/basic_str/__init__.py", line 665, in cells_to_h3shape
    mpoly = _cy.cells_to_multi_polygon(cells)
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "h3/_cy/to_multipoly.pyx", line 61, in h3._cy.to_multipoly.cells_to_multi_polygon
  File "h3/_cy/to_multipoly.pyx", line 43, in h3._cy.to_multipoly._to_multi_polygon
  File "h3/_cy/error_system.pyx", line 242, in h3._cy.error_system.check_for_error
h3._cy.error_system.H3FailedError

(which I assume is the error that caused a segfault before)

Also without the first cell in this remaining list (the one close to the poles), it again gives the "Non-empty LatLngPoly loops need at least 3 points", for something that at this point is a rather simple coverage of cells.

[ajfriend]

Thanks for the report! You're correct that this is an upstream bug in the C library. The good news is that we already have the fix landed with uber/h3#1113, which introduces a new cells-to-polygon algorithm that should work for any set of H3 cells, including "global" polygons that cross the antimeridian, are bigger than a hemisphere, or contain the poles. However, that change hasn't been released yet, and is planned for the v4.5 release of the C library. Once it is released, it should be available in the bindings (including h3-py) shortly afterwards.

We can leave this open for visibility, and close it when h3-py v4.5 is released.

And just to be sure, I checked your examples against the new algorithm in the C library, and they both work correctly without errors. Here was my viz of the cells:

[ajfriend]

We just released an alpha preview with v4.5.0a2, which includes the new algorithm that should fix the issue you were seeing, since it should work for any valid set of cells.

If you are able to test it out, please let us know if you run into any more issues. Thanks!

[jorisvandenbossche]

I can confirm that this works now with the alpha release!