SharpVoronoiLib 1.0.4
dotnet add package SharpVoronoiLib --version 1.0.4
NuGet\Install-Package SharpVoronoiLib -Version 1.0.4
<PackageReference Include="SharpVoronoiLib" Version="1.0.4" />
paket add SharpVoronoiLib --version 1.0.4
#r "nuget: SharpVoronoiLib, 1.0.4"
// Install SharpVoronoiLib as a Cake Addin #addin nuget:?package=SharpVoronoiLib&version=1.0.4 // Install SharpVoronoiLib as a Cake Tool #tool nuget:?package=SharpVoronoiLib&version=1.0.4
SharpVoronoiLib
C# implementation of generating a Voronoi diagram from a set of points in a plane (using Fortune's Algorithm) with edge clipping and border closure. This implementation guarantees O(n×ln(n)) performance.
The key differences from the original VoronoiLib repo
- Borders can be closed, that is, edges generated along the boundary
- Edges and points/sites contain additional useful data
- Multiple critical and annoyingly-rare bugs and edge cases fixes
- LOTS more unit testing
Known issues:
- The algorithm uses a lot of allocations, forcing garbage collection
Examples
TODO: several pretty pictures here
Use
Quick-start:
List<VoronoiSite> sites = new List<VoronoiSite>
{
new VoronoiSite(300, 300),
new VoronoiSite(300, 400),
new VoronoiSite(400, 300)
};
List<VoronoiEdge> edges = VoronoiPlane.TessellateOnce(
sites,
0, 0,
600, 600
);
The tesselation result for the given VoronoiSite
s contains VoronoiEdge
s and VoronoiPoint
s. The returned collection contains the generated edges.
VoronoiEdge.Start
and.End
are the start and end points of the edge.VoronoiEdge.Right
and.Left
are the sites the edge encloses. Border edges move clockwise and will only have the.Right
site. And if no points are within the region, both will benull
.- Edge end
VoronoiPoint
s also contain a.BorderLocation
specifying if it's on a border and which one. VoronoiEdge.Neighbours
(on-demand) are edges directly "connecting" to this edge, basically creating a traversable edge graph.VoronoiEdge.Length
(on-demand) is the distance between its end points.VoronoiSite.Cell
contains the edges that enclose the site (the order is not guaranteed).VoronoiSite.ClockwiseCell
(on-demand) contains these edges sorted clockwise (starting from the bottom-right "corner" end point).VoronoiSite.Neighbors
contains the site's neighbors (in the Delaunay Triangulation), that is, other sites across its edges.VoronoiSite.Points
(on-demand) contains points of the cell, that is, edge end points / edge nodes.VoronoiSite.ClockwisePoints
(on-demand) contains these points sorted clockwise (starting from the bottom-right "corner").
If closing borders around the boundary is not desired (leaving sites with unclosed cells/polygons):
List<VoronoiEdge> edges = VoronoiPlane.TessellateOnce(
sites,
0, 0,
600, 600,
BorderEdgeGeneration.DoNotMakeBorderEdges
);
Full syntax (leaving a reusable VoronoiPlane
instance):
VoronoiPlane plane = new VoronoiPlane(0, 0, 600, 600);
plane.SetSites(sites);
List<VoronoiEdge> edges = plane.Tessellate();
(Note that the algorithm will ignore duplicate sites, so check VoronoiSite.Tesselated
for skipped sites if duplicates are possible in your data.)
Sites can be quickly randomly-generated (this will guarantee no duplicates):
VoronoiPlane plane = new VoronoiPlane(0, 0, 600, 600);
plane.GenerateRandomSites(1000, PointGenerationMethod.Uniform); // also supports .Gaussian
plane.Tessellate();
Lloyds relaxation algorithm can be applied to "smooth" cells:
VoronoiPlane plane = new VoronoiPlane(0, 0, 600, 600);
plane.SetSites(sites);
plane.Tessellate();
List<VoronoiEdge> edges = plane.Relax();
// List<VoronoiEdge> edges = plane.Relax(3, 0.7f); // relax 3 times with 70% strength each time
MonoGame example
A very simple MonoGame example is included in MonoGameExample
project:
Dependencies
The main library is compiled for .NET 8.0 and .NET Standard 2.0 and targets compatible OSes - Windows, Linux & macOS - and .NET and Mono frameworks - Xamarin, Mono, UWP, Unity, etc.
Credits
- Originally written by Logan Lembke as VoronoiLib
- Updated with unit tests and nuget package by Sean Esopenko
- Improvements by Jeffrey Jones
- Various code pieces attributed inline
Original implementation inspired by:
Product | Versions Compatible and additional computed target framework versions. |
---|---|
.NET | net5.0 was computed. net5.0-windows was computed. net6.0 was computed. net6.0-android was computed. net6.0-ios was computed. net6.0-maccatalyst was computed. net6.0-macos was computed. net6.0-tvos was computed. net6.0-windows was computed. net7.0 was computed. net7.0-android was computed. net7.0-ios was computed. net7.0-maccatalyst was computed. net7.0-macos was computed. net7.0-tvos was computed. net7.0-windows was computed. net8.0 is compatible. net8.0-android was computed. net8.0-browser was computed. net8.0-ios was computed. net8.0-maccatalyst was computed. net8.0-macos was computed. net8.0-tvos was computed. net8.0-windows was computed. |
.NET Core | netcoreapp2.0 was computed. netcoreapp2.1 was computed. netcoreapp2.2 was computed. netcoreapp3.0 was computed. netcoreapp3.1 was computed. |
.NET Standard | netstandard2.0 is compatible. netstandard2.1 was computed. |
.NET Framework | net461 was computed. net462 was computed. net463 was computed. net47 was computed. net471 was computed. net472 was computed. net48 was computed. net481 was computed. |
MonoAndroid | monoandroid was computed. |
MonoMac | monomac was computed. |
MonoTouch | monotouch was computed. |
Tizen | tizen40 was computed. tizen60 was computed. |
Xamarin.iOS | xamarinios was computed. |
Xamarin.Mac | xamarinmac was computed. |
Xamarin.TVOS | xamarintvos was computed. |
Xamarin.WatchOS | xamarinwatchos was computed. |
-
.NETStandard 2.0
- No dependencies.
-
net8.0
- No dependencies.
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.
Version | Downloads | Last updated |
---|---|---|
1.0.4 | 158 | 10/13/2024 |