Voronoi cells are not generated correctly

[ghostelet]

Hi,

In some cases when I draw the Voronoi diagram, I get points located outside of there Voronoi cell. Put differently, some Voronoi cells are hosting 2 (or more) points. Also, some Voronoi cells end up having a concave shape but if my understanding is correct all Voronoi cells should be convexe in 2D using Euclidean distances.

I'm attaching here the list of points I am using to reproduce my case. In the code of MainWindow.xaml.cs, just modify the method GenerateSamples as such to load the points:

        private void GenerateSamples()
        {
            int magnifier = 16;
            var samples = File.ReadAllLines("path\to\points_sorted.txt").Select(l => l.Split(' ')).Select(l => new Point(double.Parse(l[0])* magnifier, double.Parse(l[1]) * magnifier)).ToList();

            foreach (var sample in samples)
            {
                Points.Add(sample);
                DrawCircle(sample);
            }
        }

Note that I'm "magnifying" the location of the points otherwise they will all be cramped together. I'm also attaching a screenshot that show some points outside of their Voronoi cell. The one highlighted in green is the point located at line 833 in points_sorted.txt. Points highlighted in orange are other examples. But if you look carefully, you'll find some more, or some that are really borderline. Highlighted in purple is a clear example of a concave Voronoi cell. FYI, I tried to reproduce the same scenario with another library (https://github.com/Zalgo2462/VoronoiLib) and the Voronoi diagram generated is clearly different but looks accurate to me. The Delaunay triangulation looks however the same in the 2 libraries.

points_sorted.txt

[ghostelet]

I think the issue comes from the fact that GetTriangleCenter calls GetCentroid instead of GetCircumcenter...

[nol1fe]

Hi @ghostelet, Sorry for the late response and thanks for reporting the issue.

You are correct. I have updated package. Now you can call ForEachVoronoiCellBasedOnCircumcenters, ForEachVoronoiCellBasedOnCentroids or ForEachVornoiCell and provide your own custom triangle vertex selector which i left default to Centroids, so other people won't have any package update issues.

Remember that constructing the Voronoi cell along the convex hull requires additional steps. The Delaunator library doesn’t provide this functionality.

You can read more at https://mapbox.github.io/delaunator/

Cheers