new Voronoi code

Jun 29, 2014 at 3:20 PM
Hello,

My current project uses the VoronoiRegion class quite a lot. (to get neighbour tiles, edge points etc). I noticed this is no longer used in the latest source. Is the new Face class a direct replacement, or does the new system work completely differently?

A bit cautious about upgrading, especially if it's still WIP :)

Thanks

Rob
Coordinator
Jun 29, 2014 at 6:04 PM
Edited Jun 29, 2014 at 7:21 PM
The new code isn't finished yet, so you should stick with the old code, now located in the TriangleNet.Voronoi.Legacy namespace.

The Face class will be the replacement for VoronoiRegion, but things work quite differently:
// Old Voronoi code
var voronoi1 = new SimpleVoronoi(mesh);

foreach (var region in voronoi1.Regions)
{
    foreach (var vertex in region.Vertices)
    {
        // Traverse vertices and corresponding neighbors.
        var neighbor = region.GetNeighbor(vertex);

        // Neighbor corresponding to last vertex is null for unbounded cells.
    }
}

// New Voronoi code
var voronoi2 = new StandardVoronoi(mesh);

foreach (var face in voronoi2.Faces)
{
    // Get half-edge connected to face.
    var edge = face.Edge;

    // Get the origin of first edge.
    var first = edge.Origin.ID;

    do
    {
        // Traverse edges and corresponding neighbors.
        if (edge.Twin != null)
        {
            // Get neighbor across current edge.
            var neighbor = edge.Twin.Face;
        }

        edge = edge.Next;
    }
    while (edge.Origin.ID != first);
}
If things work out well, the code for standard and bounded Voronoi diagrams will be a lot cleaner, and using DCEL as the common data structure will simplify accessing the Voronoi mesh a lot.

EDIT: if you are using the Voronoi class (which is now called SimpleVoronoi) and NOT BoundedVoronoi, feel free to play around with the new StandardVoronoi class. The code should be stable and also a bit faster.
Jul 1, 2014 at 9:04 AM
Very helpful! thank you!
Jul 18, 2014 at 10:27 AM
It seems edge.Next is returning null. Could this be a bug where the last edge isn't given the first.Origin?

Reverted to a copy and paste of the above code for testing
        TriangleNet.Geometry.Polygon poly = new TriangleNet.Geometry.Polygon(currentVornoiPoints.Count);
        
        foreach (Vector2 v2Point in currentVornoiPoints) {
            poly.Add(new TriangleNet.Geometry.Vertex(v2Point.x, v2Point.y));
        }

        TriangleNet.Meshing.GenericMesher mesher = new TriangleNet.Meshing.GenericMesher();
        TriangleNet.Meshing.IMesh mesh = mesher.Triangulate(poly);
        TriangleNet.Mesh vMesh = mesh as TriangleNet.Mesh;

        // New V code *test*

        TriangleNet.Voronoi.StandardVoronoi v = new TriangleNet.Voronoi.StandardVoronoi(vMesh);

        foreach (var face in v.Faces) {
            // Get half-edge connected to face.
            var edge = face.Edge;

            // Get the origin of first edge.
            var first = edge.Origin.ID;

            do {
                // Traverse edges and corresponding neighbors.
                if (edge.Twin != null) {
                    // Get neighbor across current edge.
                    var neighbor = edge.Twin.Face;
                }

                edge = edge.Next;
            } while (edge.Origin.ID != first);
        }
Coordinator
Jul 18, 2014 at 12:10 PM
Edited Jul 18, 2014 at 12:18 PM
This should only happen if the cell is open, ie. face.Bounded == false. Surely needs some documentation, but it makes sense:

The code above will traverse all edges of the DCEL face counterclockwise. If the face is unbounded there are exactly two (half-)infinite edges. In this case, edge = face.Edge will be the first infinite edge. edge.Origin is an infinite vertex, i.e. offically not part of the diagram. edge.Twin.Origin is the starting point of the infinite egde, so the infinite vertex is needed to know its direction.
If you reach the last infinite edge of the cell, edge.Next will be null. edge.Origin is the starting point of the infinite egde and edge.Twin.Origin is again an infinite vertex, lying in the direction of the infinite edge.

DCEL

There are two possible ways to go:
  1. Add a check while (edge != null && edge.Origin.ID != first) for unbounded cells.
  2. Use the bounded Voronoi diagram. Just add all your points into a manually added bounding box.
That's probably the last thing to do before publishing Beta 4: adding the option to intersect the standard Voronoi diagram with a bounding box, so all cells get closed.

PS: I think DCELs are quite awesome, so once you get your head around them, the insertion of a new cell won't be too hard ... it's all about careful bookkeeping of the edge pointers.
Jul 18, 2014 at 1:11 PM
Ahhh... that would be why. The infinite vertex thing has always thrown me a little. If I was creating a new cell from a point inside an existing cell with infinite edges do I need to do anything clever with the bisector calculations ?

PS: Agreed, after reading the idiots guide to DCEL's (http://www.cs.iastate.edu/~cs518/handouts/doubly-connected-edge%20list.pps) it all made sense :)