Offer `Triangulate` algorithm trait

[frewsxcv]

Options:

• delaunator
• spade
• earcutr

[urschrei]

earcutr probably isn't viable as it doesn't provide Delaunay triangulation: this means we'd have to do more work if / when we wanted to implement Voronoi tesselation, as the Delaunay triangulation is the dual graph of the Voronoi diagram.

[frewsxcv]

Maybe we could offer both? DelauneyTriangulate and EarcutTriangulate? I use the latter for rending in rgis, and I assume it's faster? But I'm not so familiar with this area

[frewsxcv]

Also considering this will likely add another dependency (or more), we should consider putting this behind a Cargo feature flag.

[urschrei]

Yeah: earcut is faster / offers higher-quality triangles on average (i.e. less chance of degenerate triangles), but some algorithms rely on a Delaunay triangulation, and it gives you a Voronoi tesselation "for free".

[urschrei]

Also consider this will likely add another dependency (or more), we should consider putting this behind a Cargo feature flag.

Worth noting that Delaunator-rs wouldn't add any new deps (it only requires robust), and Spade would add two (optional and smallvec).

Earcutr only adds itertools.

We can make a call, but we aren't exactly blowing up our dependency graph with any two of these.

[frewsxcv]

I opened a draft PR for earcut triangulation: https://github.com/georust/geo/pull/1007

[RobWalt]

I'm working on integrating spade now in https://github.com/georust/geo/pull/1083

[doc-E-brown]

If it is helpful I'm preparing a delaunay triangulation trait in https://github.com/franklin-ai/geo/blob/8bae5523f7f7aeba0e8b8d11d9159a6a3c6bf0c3/geo/src/algorithm/triangulate_delaunay.rs which I'll be preparing for an upstream PR soon. We've had an internal need for this trait.

[RobWalt]

@doc-E-brown looks cool! I'll give it a look. Note that we just integrated spade into master which also offers that functionality as well as constrained delaunay triangulations. Nevertheless your code looks promising as it seemingly doesn't need external dependencies and is also rather concise. Do you plan on working on more in that direction? If not I might take over the work of extending this at some point as I think it's quiet interesting and important! I'm looking forward to the PR! ❤️

[frewsxcv]

Both are implementations of Delauney triangulation right? I think it's worth doing a perf comparison of the implementations

[doc-E-brown]

@RobWalt yes I just come across this thread with the integration of spade as usual after I finished my work, lol 😄. The Delaunay triangulation was a means of computing Voronoi diagrams which I'm in the middle of testing and you can find here https://github.com/franklin-ai/geo/blob/8bae5523f7f7aeba0e8b8d11d9159a6a3c6bf0c3/geo/src/algorithm/voronoi_diagram.rs, similarly I'm aiming to submit this as a PR.

@frewsxcv a perf comparison would be interesting, I definitely didn't go for all out performance on my implementation but rather simplicity and ideally low maintenance.

[urschrei]

Spade has a perf comparison which should be a good guide. It's also worth noting that triangulations that don't use robust predicates will be unreliable for many edge cases (no pun intended) – the robust crate (which you're already pulling in if you use geo) will take care of that.

[frewsxcv]

Spade and Earcutr are now integrated

[doc-E-brown]

@doc-E-brown looks cool! I'll give it a look. Note that we just integrated spade into master which also offers that functionality as well as constrained delaunay triangulations. Nevertheless your code looks promising as it seemingly doesn't need external dependencies and is also rather concise. Do you plan on working on more in that direction? If not I might take over the work of extending this at some point as I think it's quiet interesting and important! I'm looking forward to the PR! ❤️

Hey @RobWalt sorry for the delay, but I've made the PR. It is located here #1144 and I've also added some perf comparisons.

Thanks!