h3_polygon_to_cells: Invalid geometries can return millions of Hex IDs

[jmealo]

Issue:

I've found that calling h3_polygon_to_cells with invalid geometries can result in as many as 2.3 million hex_ids being returned at a resolution of 7. This is not a bug in h3-pg but, rather how the h3 library handles invalid geometries. It's unclear whether we can guard against this, or should at the very least provide documentation/warnings about the issues and workarounds to mitigate them.

Cause:

• All of the geometries that caused these issues fail ST_IsValid().
• Using ST_MakeValid() turns them in bow ties.

Test case:

{
  "type": "Polygon",
  "coordinates": [
    [
      [-148.5, 29.1],
      [-148.5, 63.9],
      [-72.5, 29.1],
      [-72.5, 63.9],
      [-148.5, 29.1]
    ]
  ]
}

WITH h3_cells AS (
  SELECT h3_polygon_to_cells(
    ST_GeomFromGeoJSON('{
      "type": "Polygon",
      "coordinates": [
        [
          [-148.5, 29.1],
          [-148.5, 63.9],
          [-72.5, 29.1],
          [-72.5, 63.9],
          [-148.5, 29.1]
        ]
      ]
    }'),
    7
  ) AS cells
)
SELECT COUNT(1) 
FROM h3_cells;
# count = 2,364,092

Solution:

• It might make sense to update the documentation or examples to include a call to ST_IsValid() ... or a warning that invalid geometries could return millions of hex ids?

Upstream issue:

uber/h3#926

[zachasme]

We can definitely handle this more nicely. Principally I'm trying to keep the base h3 extension as close to upstream as possible, instead using the h3-pg extension as a friendlier PostGIS wrapper around those. So I would be open to checking validity or using ST_MakeValid when calling the h3-pg functions.

[jmealo]

@zachasme: The issue I ran into with my particular geometries is that ST_MakeValid() was returning huge bowties, that would still create what I assume to be millions of hexes at higher resolutions. I'm not 100% sure what the correct behavior is. I'm pushing to add ST_IsValid() constraints or triggers to our tables that store geometry/geography.

[zachasme]

I would be okay with adding a flag to the postgis variants of polygon_to_cells that either enables or disables running ST_IsValid on inputs. What do you think of that solution?

[jmealo]

@zachasme: I think that could make sense. I got pulled off this but will be revisiting it in the next few weeks.

Thoughts:

• It's unsafe to call these with invalid geometry
• It's very cheap to use ST_IsValid() ... should the flag default to ON by default?

I would be OK with providing a flag, if it defaults to ON. We should verify that checking a flag at runtime isn't more expensive than calling ST_IsValid() 🤔 .

[jmealo]

@zachasme: Happy New Year! It looks like the risk of invalid memory access is gone, so that significantly simplifies things here (see: uber/h3-py#436 (comment) ). I'll clean this up in the next week.

[zachasme]

Thanks, and happy new year to you too! I'll get your work in #159 merged and fixed up for the new version. Then we can look at this afterwards!