Generate a Voronoi diagram from a set of points in a plane (using Fortune's Algorithm) with edge clipping and border closure. Includes Lloyds relaxation algorithm. Original version published as VoronoiLib.
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.
Installation
The library is available as SharpVoronoiLibNuGet package: dotnet add package SharpVoronoiLib via CLI or via your preferred NuGet package manager.
Alternatively, you can download the solution and either copy the SharpVoronoiLib project code or build the project and use the SharpVoronoiLib.dll.
Usage
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
);
(Note that the algorithm will ignore duplicate sites, so check VoronoiSite.Tesselated for skipped sites if duplicates are possible in your data.)
Full syntax
Full syntax (leaving a reusable VoronoiPlane instance):
The tesselation result for the given VoronoiSites contains VoronoiEdges and VoronoiPoints. The returned collection contains the generated edges.
VoronoiEdge.Start and .End are the start and end points of the edge.
VoronoiEdge.Right and are the sites the edge encloses. Border edges move clockwise and will only have the site. And if no points are within the region, both will be .
A Voronoi diagram has a corresponding Delaunay triangulation, i.e. site neighbour links:
While these normally form triangles, be aware that four or more points in a circle will make this mathematically ambiguous; sites will have neighbours across a vertex crossing other neighbour links. This is extremely rare with random points, but must be checked if using the results for something like a triangle mesh. The library does not currently provide a direct way to gather a list of these triangles.
MonoGame example
A simple interactive MonoGame example is included in MonoGameExample project:
Dependencies
The main library targets .NET 10.0, 9.0 and .NET Standard 2.0, 2.1 and targets compatible OSes - Windows, Linux & macOS - and .NET and Mono frameworks - Xamarin, Mono, UWP, Unity, etc.
