polyfill not filling the complete polygon about h3 HOT 11 CLOSED

This issue is legitimate, even if it doesn't affect the OP. Reversing the lat/long in the test case is still a valid polygon, and does hit this issue.

Repro case:

static GeoCoord testVerts[] = {{0.10068990369902957, 0.8920772174196191},
                               {0.10032914690616246, 0.8915914753447348},
                               {0.10033349237998787, 0.8915860128746426},
                               {0.10069496685903621, 0.8920742194546231}};
static Geofence testGeofence = {.numVerts = 4, .verts = testVerts};
static GeoPolygon testPolygon;

SUITE(polyfill) {

    testPolygon.geofence = testGeofence;
    testPolygon.numHoles = 0;

    TEST(weirdShape) {
        int res = 13;
        int numHexagons = H3_EXPORT(maxPolyfillSize)(&testPolygon, res);
        H3Index* hexagons = calloc(numHexagons, sizeof(H3Index));

        H3_EXPORT(polyfill)(&testPolygon, res, hexagons);
        int actualNumHexagons = countActualHexagons(hexagons, numHexagons);

        printf("Hex count: %d\n", actualNumHexagons);

        free(hexagons);
    }
}

Output with the current 1.5 coeffecient in bboxHexRadius:

TEST polyfill
Hex count: 3945

Output with the coefficient set to 1.0:

TEST polyfill
Hex count: 4353

from h3.

First of all, thanks! This is a great bug report - really thorough. I think the issue here is that the 1.5 constant comes from a regular polyhedron model, and doesn't work when the projection distorts the shape of the hexagon - I think this is less a function of the shape you're trying to polyfill, and more a function of whether it's aligned with the long or short axis of the hexagons in its particular area of the grid. My guess is that the same shape, rotated 90 degrees, would be polyfilled correctly with the current settings (and in fact that's what happens at res 12 - suggesting that res 11 would also potentially fail to fill the shape).

We've been considering an alternative approach for polyfill that would solve this problem and be much more efficient for this kind of shape, using h3ToIJ (#102). I'd rather pursue that approach than try to fiddle with the scaling factor here, though I'd like thoughts from @isaacbrodsky and @dfellis on whether that's a reasonable stop-gap. One option would be to calculate the scale factor from a hexagon at res - 1, which is the approximate shape of the k-ring.

from h3.

Definitely an amazing bug report.

I disagree on leaving the issue alone until h3ToIJ is ready for use, though. I think we should alter the scaling factor to guarantee correctness and deal with the polyfill slowdown for the short term and then get the performance back up.

We don't have to do the math to determine the maximum extent of hex distortion, if that's what you're worried about wasting time on; just set the constant to something we know could never be reached even with distortion, such as 1.1, and move on.

from h3.

just set the constant to something we know could never be reached even with distortion, such as 1.1, and move on.

I'm fine with this, though given the perf implications it seems worthwhile calculating the worst-case scenario offline and using that as a constant.

from h3.

Thank you both!

You are correct @nrabinowitz , resolution 11 also has this problem:

I had a brief look at #102 and will keep an eye on this functionality in the future. For now I will wait and use the released version of H3.

In the meantime I am thinking of additionally tackling this issue outside of H3 by splitting the polygon into smaller parts and running polyfill on each of them separately. I hope to compensate the increased radius and keep performance up by having to generate and check less indexes.

from h3.

I just noticed something embarrassing - seems I had a quite stupid bug in my code I simply missed.

I will re-check this issue tomorrow, but there is a good chance this issue is invalid and H3 works as expected. So please do not spend any more time on this right now.

from h3.

Please close this issue as invalid. The problem was caused on my side where I had a systematic mixup of coordinate positions (x,y to lon,lat and back). I am working on an Postgresql binding for H3 and the bug happened during the translation from native postgresql geometry types to the H3 types. Because this error was a systematic mistake, it took a while for me to notice it. It can be frustrating when such simple errors can be the cause for bugs.

Thank you both for your support. I am sorry for the effort this caused on your side.

from h3.

Glad to hear it's working for you. I'll close this issue since it seems the current solutions is working well enough.

from h3.

I think it might still be worth looking into this, though - the original bug report seemed legit, and even if the OP's current issue is solved, there may still be areas of the world/H3 resolutions where this is an issue. Seeing if we can get a repro case would allow us to say whether we fixed it with an h3ToIJ implementation.

from h3.

Sorry for my Englist!

I try to creat a KML file that contain the global grid in res 2. I find indexes within the given geofence by Polyfill and get the boundary by GeoToBoundary. I found an issue where the grid which the Function's return out of the geofence.You can see the geofence vertices and the grids in the image:

from h3.

@greatathrun There's currently a known issue where you can't polyfill a polygon containing a pole. For this particular purpose, though, you ought to be able to use the h3ToGeoBoundaryHier utility, passing in each of the base cells.

from h3.