"polygonToCellsExperimental" can give incorrect results near antimeridian

[benguild]

Related to #1046, I was playing around with this library and realized that there presently seem to be some subtleties in how -180º longitude is handled compared to +180º …because those are technically the same point but entirely different numbers. I was actually able to trigger a crash because of this, but I can't remember if it crashed the calling software test or if H3 actually did.

In any case, considering how rare it may be for some software to interact with these points, it might make sense to take extra care here. A workaround from the client side is detecting and normalizing exact -180.0 coordinates to the equivalent positive range before passing them, but unless this is expected and required, it seems like the library could likely handle that better.

Example

#include <h3/h3api.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
    // Polygon with exact -180.0 longitude (in radians)
    LatLng vertices180[] = {
        {.lat = 0.837758, .lng = -3.141593},
        {.lat = 0.837758, .lng = -3.016},
        {.lat = 0.610865, .lng = -3.016},
        {.lat = 0.610865, .lng = -3.141593}, // -180°
        {.lat = 0.837758, .lng = -3.141593}  // Close
    };

    // Same polygon with +180.0 (normalized)
    LatLng verticesNorm[] = {
        {.lat = 0.837758, .lng = 3.141593},
        {.lat = 0.837758, .lng = -3.016},
        {.lat = 0.610865, .lng = -3.016},
        {.lat = 0.610865, .lng = 3.141593},  // +180°
        {.lat = 0.837758, .lng = 3.141593}   // Close
    };

    GeoPolygon polygon180 = {
        .geoloop = {.numVerts = 5, .verts = vertices180},
        .numHoles = 0,
        .holes = NULL
    };

    GeoPolygon polygonNorm = {
        .geoloop = {.numVerts = 5, .verts = verticesNorm},
        .numHoles = 0,
        .holes = NULL
    };

    // Test with -180 using CONTAINMENT_OVERLAPPING
    int64_t maxCells = 10000;
    H3Index *cells1 = calloc(maxCells, sizeof(H3Index));
    H3Error err1 = polygonToCellsExperimental(
        &polygon180, 3, CONTAINMENT_OVERLAPPING, maxCells, cells1);

    int count1 = 0;
    if (err1 == E_SUCCESS) {
        for (int64_t i = 0; i < maxCells; i++) {
            if (cells1[i] != 0) count1++;
        }
    }

    // Test with +180 (normalized)
    H3Index *cells2 = calloc(maxCells, sizeof(H3Index));
    H3Error err2 = polygonToCellsExperimental(
        &polygonNorm, 3, CONTAINMENT_OVERLAPPING, maxCells, cells2);

    int count2 = 0;
    if (err2 == E_SUCCESS) {
        for (int64_t i = 0; i < maxCells; i++) {
            if (cells2[i] != 0) count2++;
        }
    }

    printf("With -180.0: %d cells\n", count1); // 1 cell (incorrect)
    printf("With +180.0: %d cells\n", count2); // 15 cells (correct)

    free(cells1);
    free(cells2);
    return 0;
}

[benguild]

I may have found another example of this being problematic. When a polygon crosses the antimeridian (spans from positive to negative longitude, e.g., 179.5° to -179.5°), polygonToCellsExperimental returns cells that are completely invalid:

• CONTAINMENT_FULL: Returns 50 cells, 100% have centers outside the polygon
• CONTAINMENT_OVERLAPPING: Returns 84 cells, 75% have centers outside the polygon

… It appears to wrap in the opposite direction around the globe, covering everything except the antimeridian region? Not totally verified as I kind of ran out of time at the moment.

Demo

#include <h3/h3api.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
    LatLng vertices[] = {
        {.lat = 0.0,       .lng = 3.132743},   // 0°N, 179.5°E
        {.lat = 0.017453,  .lng = 3.132743},   // 1°N, 179.5°E
        {.lat = 0.017453,  .lng = -3.132743},  // 1°N, 179.5°W (179.5° west = -179.5°)
        {.lat = 0.0,       .lng = -3.132743},  // 0°N, 179.5°W
    };

    GeoPolygon polygon = {
        .geoloop = {.numVerts = 4, .verts = vertices},
        .numHoles = 0,
        .holes = NULL
    };

    int64_t maxCells = 10000;
    H3Index *cellsFull = calloc(maxCells, sizeof(H3Index));
    H3Error err1 = polygonToCellsExperimental(
        &polygon, 5, CONTAINMENT_FULL, maxCells, cellsFull
    );

    H3Index *cellsOverlap = calloc(maxCells, sizeof(H3Index));
    H3Error err2 = polygonToCellsExperimental(
        &polygon, 5, CONTAINMENT_OVERLAPPING, maxCells, cellsOverlap
    );

    if (err1 == E_SUCCESS && err2 == E_SUCCESS) {
        int countFull = 0, invalidFull = 0;
        for (int64_t i = 0; i < maxCells && cellsFull[i] != 0; i++) {
            countFull++;
            LatLng center;
            cellToLatLng(cellsFull[i], &center);
            double lngDeg = radsToDegs(center.lng);

            int inValidRange = (lngDeg >= 179.5 && lngDeg <= 180.0) ||
                              (lngDeg >= -180.0 && lngDeg <= -179.5);

            if (!inValidRange) {
                invalidFull++;
            }
        }

        int countOverlap = 0, invalidOverlap = 0;
        for (int64_t i = 0; i < maxCells && cellsOverlap[i] != 0; i++) {
            countOverlap++;
            LatLng center;
            cellToLatLng(cellsOverlap[i], &center);
            double lngDeg = radsToDegs(center.lng);

            int inValidRange = (lngDeg >= 179.5 && lngDeg <= 180.0) ||
                              (lngDeg >= -180.0 && lngDeg <= -179.5);

            if (!inValidRange) {
                invalidOverlap++;
            }
        }

        printf("CONTAINMENT_FULL:\n");
        printf("  Total cells: %d\n", countFull);
        printf("  Invalid cells: %d (%.0f%%)\n",
               invalidFull,
               100.0 * invalidFull / countFull);

        printf("\nCONTAINMENT_OVERLAPPING:\n");
        printf("  Total cells: %d\n", countOverlap);
        printf("  Invalid cells: %d (%.0f%%)\n",
               invalidOverlap,
               100.0 * invalidOverlap / countOverlap);
    }

    free(cellsFull);
    free(cellsOverlap);
    return 0;
}