Getting polygons from voronoi edges

问题:

I found this library by BenDi to create voronoi edges from a set of points. With the following code I can compute the edges of my voronoi cells.

using System;
using System.Collections.Generic;
using BenTools.Mathematics;
namespace Voronoi
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Vector[] V = new Vector[4];
            V[0] = new Vector(1.3, 2.8);
            V[1] = new Vector(0.5, 2.8);
            V[2] = new Vector(2, 1.8);
            V[3] = new Vector(1, 3);

            List<Vector> VoronoiSource = new List<Vector>();
            VoronoiSource.AddRange(V);

            VoronoiGraph Graph = Fortune.ComputeVoronoiGraph(VoronoiSource);
            Console.WriteLine("Graph has {0} edges", Graph.Edges.Count);

            foreach (var Edge in Graph.Edges)
            {
                Console.WriteLine("Edge: {0}", Edge.DirectionVector);
            }
        }
    }
}

Outputs:

Graph has 5 edges
Edge: (-0,5547;-0,8321)
Edge: (0,8192;0,5735)
Edge: (0;1)
Edge: (0,5547;0,8321)
Edge: (-0,3714;0,9285)

How can I compute the voronoi cells as polygons from these edges?

回答1:

Pick the midpoint of each edge and the distance to each site then sort the result and pick the first and second (when they are equal) and save them into polygons. For the borders there is of course only 1 edge.