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.

Installation

The library is available as SharpVoronoiLib NuGet 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):

VoronoiPlane plane = new VoronoiPlane(0, 0, 600, 600);

plane.SetSites(sites);

List<VoronoiEdge> edges = plane.Tessellate();

Result structure

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 .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 be null.
• Edge end VoronoiPoints 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.Edges (aka cell) contains the edges that enclose the site (the order is not guaranteed).
• VoronoiSite.ClockwiseEdges (on-demand) contains these edges sorted clockwise (starting from the bottom-right "corner" end point).
• VoronoiSite.ClockwiseEdgesWound (on-demand) contains these edges also "wound" in the clockwise order so their start/end points form a loop.
• VoronoiSite.Neighbours contains the site's neighbours (in the Delaunay Triangulation), that is, other sites across its edges.
• VoronoiSite.Points (on-demand) contains points/vertices of the site's cell, that is, edge end points / edge nodes.
• VoronoiSite.ClockwisePoints (on-demand) contains these points sorted clockwise (starting from the bottom-right "corner").
• VoronoiPoint.Edges are edges emerging from this point.
• VoronoiPoint.Sites (on-demand) are sites touching this point.

Border closing

If closing borders around the boundary is not desired (leaving sites with unclosed edges/polygons):

List<VoronoiEdge> edges = VoronoiPlane.TessellateOnce(
    sites, 
    0, 0, 
    600, 600,
    BorderEdgeGeneration.DoNotMakeBorderEdges
);

Closed versus unclosed:

Site generation

Sites can be quickly randomly-generated (this will guarantee no duplicates and no sites on edges):

VoronoiPlane plane = new VoronoiPlane(0, 0, 600, 600);

plane.GenerateRandomSites(1000, PointGenerationMethod.Uniform); // also supports .Gaussian

plane.Tessellate();

Uniform and Gaussian:

Site relaxation

Lloyds relaxation algorithm can be applied to "smooth" cells by spacing them out over several tessalation passes:

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 

→

Delaunay triangulation

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

Original library

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

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, notably:
  • KD tree algorithm by ericreg, originally by codeandcats

Original implementation inspired by:

• Ivan Kuckir's project
• Raymond Hill's project