H3 Polyfill skipping areas near the boundary

[nsehgal]

Hi I have noticed, when using polyfill for a polygon, it randomly skips certain areas near the boundary. How can we solve this?

For example. In this image blue dots are polygon side, and red is center. Notice the area in Cayote Point is not part of any polygon. So, polyfill will skip it even if that is part of the boundary.

Seems like if center is not part of boudary, it skips the whole polygon.

[dfellis]

So assignment to a polygon is based on the location of the center points of the hexagons.

This was chosen because if you have two perfectly contiguous polygons, the entire hexagon grid will be assigned to only one polygon, instead of potentially two, maintaining the contiguous nature of the two polygons after the polyfill.

To get the behavior you appear to desire - any hexagon that touches the polygon is included - you can simply expand the polygon by the edge length of the hexagons. This page describes how to do this perfectly, but this simpler algorithm would probably suffice.

[rustyconover]

Actually expanding by the edge length is insufficient.

See: https://observablehq.com/@rustyconover/ensuring-h3-polyfill-returns-all-hexagons-for-a-polygon

You may need to expand by edge length * 2.0.

[dfellis]

You only need to expand around the polygon by the edge length. You're confusing a border around an arbitrary polygon with a radius.

To create a border equal to the edge length for a circle you need to add 2 times the edge length to it, but the length of the distance between an arbitrary point on the circle and the closest point on the expanded circle would be just the edge length.

[kamil-kielczewski]

@dfellis understanding and implementation Minkowski sum is quite time consumming. May be it will be better if we add some optional boolean parameter to polyfill function which as default will be work in old way - but if someone set it to true then the result will be minimal set of hexagons which cover input polygon?

That would save a lot of time for many people

[dfellis]

@dfellis understanding and implementation Minkowski sum is quite time consumming. May be it will be better if we add some optional boolean parameter to polyfill function which as default will be work in old way - but if someone set it to true then the result will be minimal set of hexagons which cover input polygon?

That would save a lot of time for many people

@kamil-kielczewski work has already started on adding multiple polyfill modes in the planned 4.0 of H3. If you wish to save a lot of time for many people, feel free to help getting this over the line sooner.