Fast Delaunay triangulation of 2D points implemented in C#.
This code was ported from Mapbox's Delaunator project (JavaScript).
See https://mapbox.github.io/delaunator/ for more information about the Triangles and Halfedges data structures.
Simply edit manifest.json file in your Unity Packages directory
{
"dependencies": {
"com.nol1fe.delaunator": "https://github.com/nol1fe/delaunator-sharp.git?path=DelaunatorSharp.Unity",
}
From UnityPackage Menager select Delaunator and press "Import into Project".
There is available playground in DelaunatorSharp.WPF.Example project that shows examples of drawing Voronoi Diagram, Delaunay triangulation and Convex Hull
Points were generated with Poisson Disc Sampling implemented by UniformPoissonDiskSampler
BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19043
11th Gen Intel Core i7-11800H 2.30GHz, 1 CPU, 16 logical and 8 physical cores .NET Core SDK=5.0.401
| Method | Count | Type | Mean | Error | StdDev |
|---|---|---|---|---|---|
| Delaunator | 100000 | Uniform | 63.66 ms | 21.68 ms | 14.34 ms |
| Delaunator | 100000 | Gaussian | 62.07 ms | 21.60 ms | 14.29 ms |
| Delaunator | 100000 | Grid | 46.88 ms | 18.53 ms | 12.25 ms |
| Delaunator | 1000000 | Uniform | 658.91 ms | 41.11 ms | 27.19 ms |
| Delaunator | 1000000 | Gaussian | 680.02 ms | 96.03 ms | 63.52 ms |
| Delaunator | 1000000 | Grid | 516.89 ms | 60.64 ms | 40.11 ms |