search

georust / geo

Geospatial primitives and algorithms for Rust
https://crates.io/crates/geo
Other
1.53k stars 198 forks source link

Add Voronoi diagrams with zero dependency delaunay triangulation #1144

Closed doc-E-brown closed 3 months ago

doc-E-brown commented 8 months ago

This PR adds the VoronoiDiagram trait to create Voronoi diagrams from Polygon and MultiPoint types. The Voronoi diagram is created using the property that voronoi diagrams are the dual of delaunay triangulation.

The VoronoiDiagram trait uses an added TriangulateDelaunay trait that computes Delaunay triangles without any additional dependencies. As per the conversation here this work was started before the introduction of the spade methodology. As requested in the conversation I've added a bench performance test to compare the different methods and these are the results when running on my laptop.

Delaunay Triangulation  time:   [2.2839 µs 2.3687 µs 2.4780 µs]
                        change: [-21.682% -14.728% -7.0971%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

Spade Unconstrained Triangulation
                        time:   [1.4216 µs 1.4831 µs 1.5582 µs]
                        change: [+39.411% +46.250% +53.808%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 7 outliers among 100 measurements (7.00%)
  5 (5.00%) high mild
  2 (2.00%) high severe

Constrained Outer Triangulation
                        time:   [3.5185 µs 3.7830 µs 4.1260 µs]

Constrain Triangulation time:   [3.5962 µs 3.7355 µs 3.8970 µs]
Found 15 outliers among 100 measurements (15.00%)
  2 (2.00%) low mild
  4 (4.00%) high mild
  9 (9.00%) high severe

the TriangulateDelaunay trait is faster then the Constrained Outer Triangulation method but not the Unconstrained Method.

The original intent behind implementing Delaunay triangulation in geo arose when we needed a method that was compliant with the Apache license using geo-types and was not otherwise available.

Thank you for considering this PR.

doc-E-brown commented 7 months ago

Thanks so much for your thorough review @RobWalt! I'll work through them and have an update soon.

doc-E-brown commented 7 months ago

Hi @RobWalt sorry for the delay, I've updated the PR as per your comments. It definitely looks much cleaner! Thanks!

RobWalt commented 4 months ago

Hey, sorry for leaving this unattended for so long. I kind of forgot about it and lost track of it. Here's my new suggestion: The PR is kind of big. Could we split it up into two parts?

  1. the triangulation part, which I'm happy to approve instantly
  2. the vonoroi part, which still needs some review
urschrei commented 4 months ago

@doc-E-brown @RobWalt Apologies, I thought I had already asked this question: given that we already depend on spade – which provides Voronoi tessellation (though we haven't exposed it via geo) and Delaunay triangulation, and have an ear-cut triangulation module. As it stands, I can't imagine merging this PR:

  1. It duplicates functionality
  2. It's not tested in use to the same extent as the functionality it's duplicating (Spade is mature and in fairly wide use)