geo_to_cells() for a global polygon?

[jorisvandenbossche]

Consider the following example:

import shapely
import h3

bbox = shapely.box(-170, -80, 170, 80)
cells = h3.geo_to_cells(bbox, res=0)

gives

>>> len(cells)
5
>>> cells
['807ffffffffffff',
 '805bfffffffffff',
 '809bfffffffffff',
 '8071fffffffffff',
 '80bbfffffffffff']

i.e. it interprets the polygon not as the one that spans almost the entire globe, but as the smaller counterpart. And it seems to do that regardless of the orientation of the polygon ring.

In the Polygon tutorial there is a section https://uber.github.io/h3-py/polygon_tutorial.html#h3-polygons-don-t-need-to-follow-the-right-hand-rule about the orientation. And it seems to indicate that it will essentially ignore the orientation of the rings of the input, which I assume means it uses the rule of "smallest area" to know which polygon is described?

But that then also means you cannot really pass a polygon larger than half the globe to geo_to_cells()?

[ajfriend]

Thanks for asking! Improving support for "global" polygons is something I've been thinking about recently. I'd love to improve support in the upstream C library, which would carry over to h3-py.

Your understanding of the current library behavior is correct. The polygonToCells function in the C library is agnostic to winding order. It effectively interprets the loop as the smaller of the two regions it defines on the sphere. That means you can't directly pass in a larger-than-a-hemisphere polygon and have it work as you're expecting. As a workaround, a large polygon can be broken into smaller polygons. While that's a downside, this choice does have some benefits: a roundtrip from (cell -> polygon -> cell) for a cell that crosses the antimeridian works in all cases, without having to, for example, extend coordinates outside the [-180°, +180°] longitude range. This approach was chosen, I believe, with the assumption that most users will be interested in "small" polygons rather than global polygons, and we wanted them to not have to worry about winding order. Correct me if I have anything wrong here, @isaacbrodsky @nrabinowitz @dfellis.

First, I think we could improve the documentation to make these limitations clear on both https://h3geo.org and https://uber.github.io/h3-py/intro.html. We currently don't document the geometric assumptions very well (planar interpretation of polygon edges, winding order behavior, or limitations for large polygons). We should fix that. And if you have any suggestions (or want to put up a PR!) for the h3-py docs, that would be more than welcome.

Second, how do we improve support for global polygons going forward?

My thinking has been toward a new "geodesic" mode (uber/h3#1052) that @holoskii has kicked off. The existing mode in polygonToCells interprets polygon edges as planar in lat/lng space, and any changes we make there would potentially be backwards-incompatible. The new geodesic mode presents an opportunity to do things right, without any breaking changes. (But if you think we could make some improvements to the existing mode, please raise them. I just haven't thought about it much.)

To resolve the "which interior do you mean" ambiguity, a geodesic mode for H3 could adopt assumptions like:

• Interpret lat/lng as points on the sphere, rather than as coordinates in fixed ranges, where one might be tempted to interpret the sign of a number. For example, the following coordinates should represent the same point and be algorithmically indistinguishable: (80°, -170°) ≡ (80°, 190°) ≡ (100°, 10°).
• Polygon edges follow the shortest geodesic path between vertices (with exactly 180° arcs disallowed to avoid ambiguity).
• Ring orientation determines interior vs exterior via the right-hand rule: outer loops counter-clockwise, holes clockwise.

With assumptions like those, we should theoretically be able to handle general globe-spanning polygons.

In the short term, approaches like uber/h3#1052 may still need to constrain input polygons to be contained within a hemisphere. From there we can improve the algorithms and relax those constraints over time.

I think uber/h3#1052 is the right next step toward supporting global polygons. But I would also love to hear other thoughts or ideas on this.