Algorithm implementation of polyfill

[yangscout]

I am very interested in the polyfill function when using h3. I want to find the specific definition of this function, but I can't find it in the local library or github. Can you share the specific code implementation?

[kylebarron]

I think the existing polyfill implementation checks which cell centers intersects the geometry of interest. It does not check against actual cell boundaries

[dfellis]

That's correct. Using cell center containment guarantees that two contiguous polygons (with perfect overlap of some of the points of the polygon, like ZCTAs or other regional boundaries) will produce perfectly contiguous sets of H3 cells where there are zero cells that end up in both sets.

That was a hard requirement for the conversion of Uber's internal geofences to H3 during a transition phase where some surge algorithms continued operating on distinct geofences but needed to be rendered in conjunction with other algorithms that used H3 natively.

One caveat, though, is that cell center containment is done in lat, lng coordinates, so it's effectively operating in mercator projection while most of H3 is using an icosahedron-centered gnomonic projection, so at very large scales there are discrepancies there. However, since all Uber geofences were defined in mercator projection, and that is also the de facto standard for GeoJSON and etc, it's probably the best choice, despite feeling a bit off compared to the rest of the library.

Now that H3 4.0 has made it possible to start adding new polyfill algorithms, though, I'm hoping to make other containment and projection combinations available. :) (Once I have some spare time, that is. :/ )

[yangscout]

Yes, the current polyfill does not meet my needs perfectly. I want to ask where I can see the algorithm implemented by the polyfill and improve it.

[dfellis]

Yes, the current polyfill does not meet my needs perfectly. I want to ask where I can see the algorithm implemented by the polyfill and improve it.

So the implementation lives here but it hasn't been refactored to use the flags argument, yet, as a warning for you. What particular polyfill algorithm do you need?

[yangscout]

Yes, the current polyfill does not meet my needs perfectly. I want to ask where I can see the algorithm implemented by the polyfill and improve it.

So the implementation lives here but it hasn't been refactored to use the flags argument, yet, as a warning for you. What particular polyfill algorithm do you need?

The current polyfill algorithm is to find all h3 points whose mesh center is located in the polygon. I want to find an algorithm to find that all the vertices of its h3 hexagon are located in the polygon

[nrabinowitz]

We've discussed this for some time - but note that "all vertices within" is not the same as "contains", as you could still have edges of the polygon that intersect edges of the cell.

We'd welcome contributions here if you are interested in providing them. At the moment, however, it might be easiest for you to post-process the output by filtering out cells that are not fully contained.