geoarrow-rs icon indicating copy to clipboard operation
geoarrow-rs copied to clipboard

Wrap `TriangulateEarcut` trait.

Open kylebarron opened this issue 2 years ago • 2 comments

Earcut functionality would be useful to support.

  • Does a TriangleArray make sense? It wouldn't be exactly aligned with (today's) formal geoarrow types, but it would be really high performance. A TriangleArray could naively be defined as a FixedSizeList[3]. We could have a to_polygon_array method on the TriangleArray struct, which should be high performance because we know the size of the output coordinate array and output offsets array at the start.
  • earcut_triangles_raw is quite useful because the triangle indices are already in a flat array.
    • Is the order of vertices in the result guaranteed to be the same as the original vertices? They are in the example but you should look/ask to see whether this is always the case. If it is, then you can reuse the input coordinate array and just shift the indices of the output indices as needed to make it accurate in the full array.

kylebarron avatar Jul 09 '23 00:07 kylebarron

Notes:

  • Probably makes more sense to wrap earcutr directly, since then you won't go through geo objects at all. geo's impl is here
  • For the return type, maybe look what deck.gl wants? What makes sense for an arrow definition of triangle vertices and indices?
  • Maybe name it geoarrow::algorithm::earcutr::earcut?
  • This is maybe a great time to try bumpalo, since we won't have geo making its own heap allocations?

kylebarron avatar Jul 19 '23 00:07 kylebarron

Also consider:

  • earcutr takes as input a flat array of vertex coordinates

So... in preparation for earcut we can do:

  1. First convert the coordinates to interleaved coords if they're not already.
  2. Slice the coordinates array based on the current geometry's indices into the global coordinates array.
  3. Compute the local hole indices
  4. Pass into earcut

Then for the result you can just do a FixedSizeList[3] for the indices? Move those indices to the global indices?

kylebarron avatar Jul 19 '23 00:07 kylebarron