Offer `Triangulate` algorithm trait about geo HOT 14 CLOSED

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.

from geo.

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".

from geo.

@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! ❤️

from geo.

@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!

from geo.

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.

from geo.

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

from geo.

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

from geo.

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.

from geo.

I opened a draft PR for earcut triangulation: #1007

from geo.

I'm working on integrating spade now in #1083

from geo.

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

from geo.

@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.

from geo.

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.

from geo.

Spade and Earcutr are now integrated

from geo.