boristhebrave / voronator-sharp

.NET / Unity library for creating Voronoi Diagrams

VoronatorSharp

VoronatorSharp is a C# library that computes Voronoi diagrams. The Voronoi diagram for a collection of points is the polygons that enclose the areas nearest each of those sites.

Voronoi diagrams have applications in a number of areas such as computer graphics.

This library features:

• Computes Voronoi diagrams and Delaunay triangulations.
• Voronoi polygons can be clipped to a rectangular area.
• Uses a n log(n) sweephull algorithm.
• The implementation attempts to minimize memory allocations.
• Integrates with Unity or can be be used standalone.
• Uses robust orientation code.
• Handles Voronoi diagrams with only 1 or 2 points, and collinear points.

Credits

The majority of this code is adapted from:

• delaunator-sharp - computes Delaunay triangulation
• d3-delaunay - clip polygons to a rectangle
• RobustGeometry.NET - robust geometry predicates

All code is licensed on MIT-like terms.

Installation

Currently this is not listed on NuGet nor available as a Unity package. Please contact me if these interest you.

You can find pre-compiled dlls on the GitHub release page, these can be directly refenced by other projects and have no dependencies.

For Unity, copy the pre-compiled for Unity dll into your project, or copy the source code itself.

Usage

Voronator

The Voronator class computes a Voronoi diagram for a set of points.

var points = new Vector2[]{ new Vector2(0, 0), new Vector2(0, 1), new Vector2(1, 0)};
var v = new VoronatorSharp.Voronator(points);
for (var i=0; i < points.Length; i++)
{
    var vertices = v.GetClippedPolygon(i);
}

Voronoi cells on the outside of the diagram can be unbounded meaning they extend off to infinity, and may have less than 3 vertices. For this reason, some methods come in a "clipped" and "unclipped" variety. A clipped method works with voronoi cells that have been cut to fit inside a rectangle called the clipping rectangle.

The clipping rectangle is by default large enough to cover all bounded cells, but can be set to anything in the constructor.

Methods

The key methods are documented below - there are further methods and comments in the source.

public List<Vector2> Voronator.GetPolygon(int i)

Returns the vertices of the voronoi cell, without any clipping.

public bool Voronator.GetPolygon(int i, List<Vector2> vertices, out Vector2 ray1, out Vector2 ray2)

A version of GetPolygon that avoids allocating memory for vertices, and can return the rays associated with an unbounded cell.

public List<Vector2> Voronator.GetClippedPolygon(int i)

Returns the vertices of the voronoi cell i after clipping to the clipping rectangle. Returns null if the polygon is fully outside the clipping rectangle.

public IEnumerable<int> Voronator.Neighbors(int i)

Returns the Voronoi cells that border the given cell. This ignores clipping and may return odd results in some degenerate cases.

public IEnumerable<int> Voronator.ClippedNeighbors(int i)

Returns the Voronoi cells that border the given cell inside the clipping rectangle.

public int Voronator.Find(Vector2 u, int i = 0)

Finds the Voronoi cell that contains the given point, or equivalently, finds the point that is nearest the given point. This ignores clipping, so it always succeeds.

• u - The point to search for.
• i - Optional, the voronoi cell to start the search at. Useful if you know the returned cell will be nearby.

public List<Vector2> Voronator.GetRelaxedPoints()

Returns the centroid of each voronoi cell. This is suitable for use with Lloyd relaxation. Unbounded cells are clipped down, which tends to move them inwards.

public Voronator.PolygonStatus GetPolygonStatus(int i)

Returns an enum indicating how this polygon was handled. Usually it is Voronator.PolygonStatus.Normal, but there are other values corresponding to edge cases described below.

Edge cases

There are some tricky cases that you should be aware of. In all cases, if you stick with the "clipped" methods, these are effectively handled for you.

Unbounded cells

Cells on the boundary of the diagram extend to infinity, which means they are not representable with a polygon. "Clipped" methods truncate the cells down to a polygon.

Degenerate triangulation

VoronatorSharp is based on forming a Delaunay triangulation, then finding the dual.

So it can struggle to deal with the case of more than 3 Voronoi cells meeting at a single point. "Clipped" methods automatically strip zero-sized edges.

Collinear points

If all the input points lie in a line (or if there are only two points), then the points are collinear and a triangulation cannot be formed. Voronator contails fallback code to handle this case. The case of a single point is handled similarly.

Duplicate points

Additional points that are an exact duplicate of an earlier point will return a null polygon.

Delaunator

The Delaunator class computes a Delaunay triangulation for a set of points. The API similar to DelaunatorSharp, and you can find a helpful description of this datastructure here.

Methods

The key methods are documented below - there are further methods and comments in the source.

public IEnumerable<Triangle> Delaunator.GetTriangles()

Returns the points of all triangles in the Delaunay triangulation. A Triangle has the vector location of exactly 3 points, Point1, Point2 and Point3, and properties for computing the Centroid and Circumcenter.

public IEnumerable<(Vector2, Vector2)> Delaunator.GetEdges()

Returns all edges in the triangulation. Each edge is only represented once, even if there is a triangle on either side.

public int[] Delaunator.Triangles { get; }

One value per half-edge, containing the point index of where a given half edge starts.

public int[] Delaunator.Halfedges { get; }

One value per half-edge, containing the opposite half-edge in the adjacent triangle, or -1 if there is no adjacent triangle

public Vector2[] Delaunator.Points { get; }

The initial points Delaunator was constructed with.

voronator-sharp's Issues

Exception when create diagram

When I use the following set of points,

List<Vector2> points = new List<Vector2>
{
    new Vector2(8.481889f, -10.29803f),
    new Vector2(14.8841f, -11.41214f),
    new Vector2(17.28493f, -16.59971f),
    new Vector2(11.40464f, -14.75447f),
    new Vector2(4.44571f, -21.02133f),
    new Vector2(14.29259f, -22.76213f),
    new Vector2(3.437411f, -9.220477f),
    new Vector2(17.73516f, -7.305126f),
    new Vector2(21.68072f, -22.66702f),
    new Vector2(13.86774f, -26.88861f),
    new Vector2(2.343594f, -24.34784f),
    new Vector2(3.437411f, -9.220477f)
};

this code crashes with an error.

var points = new Vector2[]{ new Vector2(0, 0), new Vector2(0, 1), new Vector2(1, 0)};
var v = new VoronatorSharp.Voronator(points);
for (var i=0; i < points.Length; i++)
{
    var vertices = v.GetClippedPolygon(i);
}

Error in first line of function. Argument points is null.

private List<Vector2> ClipFinite(int i, List<Vector2> points)
{
    var n = points.Count;
    ...
};

Boundary of diagram

Boris, can I specify the boundary polygon before creating the Voronoi diagram? There is an array of points and a polygon some distance away from the points. In the polygon, I need to build a Voronoi diagram.
How to do this?