"cellsToMultiPolygon" occasionally produces degenerate polygons with only 1 vertex

[benguild]

For example, when calling with a specific set of 164 valid resolution-2 cells, the function returns 14 polygons where:

• 12 polygons are valid (≥ 3 vertices)
• 2 polygons have only 1 vertex each (degenerate)

My data could be somehow wrong or invalid here, but I didn't think so? These I believe are valid cells, and a valid polygon ring requires at least 3 vertices.

A workaround is to look for invalid polygons and recursively subdivide the collection and retry until the issue disappears (which also "solves" #1046) but it seems like there's some underlying instability here.

As noted, I'm just playing with this library right now, and noticed this stuff.

Reproduction

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

int main() {
    H3Index cells[164] = {
        0x827487fffffffffULL, 0x82748ffffffffffULL, 0x827497fffffffffULL, 0x82749ffffffffffULL,
        0x8274affffffffffULL, 0x8274c7fffffffffULL, 0x8274cffffffffffULL, 0x8274d7fffffffffULL,
        0x8274e7fffffffffULL, 0x8274effffffffffULL, 0x8274f7fffffffffULL, 0x82754ffffffffffULL,
        0x827c07fffffffffULL, 0x827c27fffffffffULL, 0x827c2ffffffffffULL, 0x827c37fffffffffULL,
        0x827d87fffffffffULL, 0x827d8ffffffffffULL, 0x827d97fffffffffULL, 0x827d9ffffffffffULL,
        0x827da7fffffffffULL, 0x827daffffffffffULL, 0x82801ffffffffffULL, 0x8280a7fffffffffULL,
        0x8280affffffffffULL, 0x8280b7fffffffffULL, 0x828197fffffffffULL, 0x82819ffffffffffULL,
        0x8281a7fffffffffULL, 0x8281b7fffffffffULL, 0x828207fffffffffULL, 0x82820ffffffffffULL,
        0x828227fffffffffULL, 0x82822ffffffffffULL, 0x8282e7fffffffffULL, 0x828307fffffffffULL,
        0x82830ffffffffffULL, 0x82831ffffffffffULL, 0x82832ffffffffffULL, 0x828347fffffffffULL,
        0x82834ffffffffffULL, 0x828357fffffffffULL, 0x82835ffffffffffULL, 0x828367fffffffffULL,
        0x828377fffffffffULL, 0x82a447fffffffffULL, 0x82a457fffffffffULL, 0x82a45ffffffffffULL,
        0x82a467fffffffffULL, 0x82a46ffffffffffULL, 0x82a477fffffffffULL, 0x82a4c7fffffffffULL,
        0x82a4cffffffffffULL, 0x82a4d7fffffffffULL, 0x82a4e7fffffffffULL, 0x82a4effffffffffULL,
        0x82a4f7fffffffffULL, 0x82a547fffffffffULL, 0x82a54ffffffffffULL, 0x82a557fffffffffULL,
        0x82a55ffffffffffULL, 0x82a567fffffffffULL, 0x82a577fffffffffULL, 0x82a837fffffffffULL,
        0x82a897fffffffffULL, 0x82a8a7fffffffffULL, 0x82a8b7fffffffffULL, 0x82a917fffffffffULL,
        0x82a927fffffffffULL, 0x82a937fffffffffULL, 0x82a987fffffffffULL, 0x82a98ffffffffffULL,
        0x82a997fffffffffULL, 0x82a99ffffffffffULL, 0x82a9a7fffffffffULL, 0x82a9affffffffffULL,
        0x82ac47fffffffffULL, 0x82ac57fffffffffULL, 0x82ac5ffffffffffULL, 0x82ac67fffffffffULL,
        0x82ac6ffffffffffULL, 0x82ac77fffffffffULL, 0x82ad47fffffffffULL, 0x82ad4ffffffffffULL,
        0x82ad57fffffffffULL, 0x82ad5ffffffffffULL, 0x82ad67fffffffffULL, 0x82ad77fffffffffULL,
        0x82c207fffffffffULL, 0x82c217fffffffffULL, 0x82c227fffffffffULL, 0x82c237fffffffffULL,
        0x82c287fffffffffULL, 0x82c28ffffffffffULL, 0x82c29ffffffffffULL, 0x82c2a7fffffffffULL,
        0x82c2affffffffffULL, 0x82c2b7fffffffffULL, 0x82c307fffffffffULL, 0x82c317fffffffffULL,
        0x82c31ffffffffffULL, 0x82c337fffffffffULL, 0x82cfb7fffffffffULL, 0x82d0c7fffffffffULL,
        0x82d0d7fffffffffULL, 0x82d0dffffffffffULL, 0x82d0e7fffffffffULL, 0x82d0f7fffffffffULL,
        0x82d147fffffffffULL, 0x82d157fffffffffULL, 0x82d15ffffffffffULL, 0x82d167fffffffffULL,
        0x82d177fffffffffULL, 0x82d187fffffffffULL, 0x82d18ffffffffffULL, 0x82d197fffffffffULL,
        0x82d19ffffffffffULL, 0x82d1a7fffffffffULL, 0x82d1affffffffffULL, 0x82dc47fffffffffULL,
        0x82dc57fffffffffULL, 0x82dc5ffffffffffULL, 0x82dc67fffffffffULL, 0x82dc6ffffffffffULL,
        0x82dc77fffffffffULL, 0x82dcc7fffffffffULL, 0x82dccffffffffffULL, 0x82dcd7fffffffffULL,
        0x82dce7fffffffffULL, 0x82dceffffffffffULL, 0x82dcf7fffffffffULL, 0x82dd1ffffffffffULL,
        0x82dd47fffffffffULL, 0x82dd4ffffffffffULL, 0x82dd57fffffffffULL, 0x82dd5ffffffffffULL,
        0x82dd6ffffffffffULL, 0x82dd87fffffffffULL, 0x82dd8ffffffffffULL, 0x82dd97fffffffffULL,
        0x82dd9ffffffffffULL, 0x82ddaffffffffffULL, 0x82ddb7fffffffffULL, 0x82dec7fffffffffULL,
        0x82decffffffffffULL, 0x82ded7fffffffffULL, 0x82dee7fffffffffULL, 0x82deeffffffffffULL,
        0x82def7fffffffffULL, 0x82df0ffffffffffULL, 0x82df1ffffffffffULL, 0x82df47fffffffffULL,
        0x82df4ffffffffffULL, 0x82df57fffffffffULL, 0x82df5ffffffffffULL, 0x82df77fffffffffULL,
        0x82df8ffffffffffULL, 0x82df9ffffffffffULL, 0x82e6c7fffffffffULL, 0x82e6cffffffffffULL,
        0x82e6d7fffffffffULL, 0x82e6dffffffffffULL, 0x82e6effffffffffULL, 0x82e6f7fffffffffULL,
    };

    LinkedGeoPolygon polygons;
    H3Error err = cellsToMultiPolygon(cells, 164, &polygons);

    if (err != E3_OK) {
        fprintf(stderr, "cellsToMultiPolygon failed with error: %d\n", err);
        return 1;
    }

    int polygonCount = 0;
    int degenerateCount = 0;
    LinkedGeoPolygon* current = &polygons;

    while (current != NULL) {
        int vertexCount = 0;
        LinkedLatLng* vertex = current->first;
        while (vertex != NULL) {
            vertexCount++;
            vertex = vertex->next;
        }

        if (vertexCount < 3) {
            printf("Polygon %d: %d vertices (DEGENERATE)\n", polygonCount, vertexCount);
            degenerateCount++;
        } else {
            printf("Polygon %d: %d vertices (valid)\n", polygonCount, vertexCount);
        }

        polygonCount++;
        current = current->next;
    }

    printf("\nTotal: %d polygons, %d degenerate\n", polygonCount, degenerateCount);

    destroyLinkedMultiPolygon(&polygons);
    return 0;
}

[ajfriend]

This is a good catch. Thanks! Out of curiosity, how are you generating these examples? I wonder if the process is generalizable in a way that we can use for more thorough testing.

I can confirm the issue in h3-py, and that your example cells are all valid.

import h3.api.basic_int as h3

cells = [
    0x827487fffffffff, 0x82748ffffffffff, 0x827497fffffffff, 0x82749ffffffffff,
    0x8274affffffffff, 0x8274c7fffffffff, 0x8274cffffffffff, 0x8274d7fffffffff,
    0x8274e7fffffffff, 0x8274effffffffff, 0x8274f7fffffffff, 0x82754ffffffffff,
    0x827c07fffffffff, 0x827c27fffffffff, 0x827c2ffffffffff, 0x827c37fffffffff,
    0x827d87fffffffff, 0x827d8ffffffffff, 0x827d97fffffffff, 0x827d9ffffffffff,
    0x827da7fffffffff, 0x827daffffffffff, 0x82801ffffffffff, 0x8280a7fffffffff,
    0x8280affffffffff, 0x8280b7fffffffff, 0x828197fffffffff, 0x82819ffffffffff,
    0x8281a7fffffffff, 0x8281b7fffffffff, 0x828207fffffffff, 0x82820ffffffffff,
    0x828227fffffffff, 0x82822ffffffffff, 0x8282e7fffffffff, 0x828307fffffffff,
    0x82830ffffffffff, 0x82831ffffffffff, 0x82832ffffffffff, 0x828347fffffffff,
    0x82834ffffffffff, 0x828357fffffffff, 0x82835ffffffffff, 0x828367fffffffff,
    0x828377fffffffff, 0x82a447fffffffff, 0x82a457fffffffff, 0x82a45ffffffffff,
    0x82a467fffffffff, 0x82a46ffffffffff, 0x82a477fffffffff, 0x82a4c7fffffffff,
    0x82a4cffffffffff, 0x82a4d7fffffffff, 0x82a4e7fffffffff, 0x82a4effffffffff,
    0x82a4f7fffffffff, 0x82a547fffffffff, 0x82a54ffffffffff, 0x82a557fffffffff,
    0x82a55ffffffffff, 0x82a567fffffffff, 0x82a577fffffffff, 0x82a837fffffffff,
    0x82a897fffffffff, 0x82a8a7fffffffff, 0x82a8b7fffffffff, 0x82a917fffffffff,
    0x82a927fffffffff, 0x82a937fffffffff, 0x82a987fffffffff, 0x82a98ffffffffff,
    0x82a997fffffffff, 0x82a99ffffffffff, 0x82a9a7fffffffff, 0x82a9affffffffff,
    0x82ac47fffffffff, 0x82ac57fffffffff, 0x82ac5ffffffffff, 0x82ac67fffffffff,
    0x82ac6ffffffffff, 0x82ac77fffffffff, 0x82ad47fffffffff, 0x82ad4ffffffffff,
    0x82ad57fffffffff, 0x82ad5ffffffffff, 0x82ad67fffffffff, 0x82ad77fffffffff,
    0x82c207fffffffff, 0x82c217fffffffff, 0x82c227fffffffff, 0x82c237fffffffff,
    0x82c287fffffffff, 0x82c28ffffffffff, 0x82c29ffffffffff, 0x82c2a7fffffffff,
    0x82c2affffffffff, 0x82c2b7fffffffff, 0x82c307fffffffff, 0x82c317fffffffff,
    0x82c31ffffffffff, 0x82c337fffffffff, 0x82cfb7fffffffff, 0x82d0c7fffffffff,
    0x82d0d7fffffffff, 0x82d0dffffffffff, 0x82d0e7fffffffff, 0x82d0f7fffffffff,
    0x82d147fffffffff, 0x82d157fffffffff, 0x82d15ffffffffff, 0x82d167fffffffff,
    0x82d177fffffffff, 0x82d187fffffffff, 0x82d18ffffffffff, 0x82d197fffffffff,
    0x82d19ffffffffff, 0x82d1a7fffffffff, 0x82d1affffffffff, 0x82dc47fffffffff,
    0x82dc57fffffffff, 0x82dc5ffffffffff, 0x82dc67fffffffff, 0x82dc6ffffffffff,
    0x82dc77fffffffff, 0x82dcc7fffffffff, 0x82dccffffffffff, 0x82dcd7fffffffff,
    0x82dce7fffffffff, 0x82dceffffffffff, 0x82dcf7fffffffff, 0x82dd1ffffffffff,
    0x82dd47fffffffff, 0x82dd4ffffffffff, 0x82dd57fffffffff, 0x82dd5ffffffffff,
    0x82dd6ffffffffff, 0x82dd87fffffffff, 0x82dd8ffffffffff, 0x82dd97fffffffff,
    0x82dd9ffffffffff, 0x82ddaffffffffff, 0x82ddb7fffffffff, 0x82dec7fffffffff,
    0x82decffffffffff, 0x82ded7fffffffff, 0x82dee7fffffffff, 0x82deeffffffffff,
    0x82def7fffffffff, 0x82df0ffffffffff, 0x82df1ffffffffff, 0x82df47fffffffff,
    0x82df4ffffffffff, 0x82df57fffffffff, 0x82df5ffffffffff, 0x82df77fffffffff,
    0x82df8ffffffffff, 0x82df9ffffffffff, 0x82e6c7fffffffff, 0x82e6cffffffffff,
    0x82e6d7fffffffff, 0x82e6dffffffffff, 0x82e6effffffffff, 0x82e6f7fffffffff,
]

assert all(h3.is_valid_cell(c) for c in cells)

h3.cells_to_h3shape(cells)

Running the last line give me an:

ValueError: Non-empty LatLngPoly loops need at least 3 points.

[benguild]

Out of curiosity, how are you generating these examples?

Just playing around with random datasets and occasionally running into quirks. It feels like oceans and wider areas in particular seem to occasionally fall into edge cases, like around the antimeridian where things can wrap around the globe, etc. — but these could be masking other related bugs too so it'd be cool to look into what's going on.

[grim7reaper]

For what it's worth, h3o seems to produce the expected result (at least doesn't return an error).

Might be able to spot the bug by comparing the two implementations.
h3o started as a Rust port of H3, but I then reworked the algorithms a bit to optimize them: might have solved a couple of bugs while doing so.

(also works correctly for #1046)

[benguild]

@grim7reaper nice. I’m testing some of this in Go also, and have verified each of these in Go, too, but perhaps indeed a fix could be inferred based on it working in Rust. Also, it might be interesting to maintain tests around cases like this between the various library and platform variations, and how they can work differently… since it should be consistent.