"ForEachVoronoiCell" and "ForEachVoronoiEdge" yield inconsistent drawing results.

[KiroJong-Zero]

Hello, I used the ForEachVoronoiCell method to draw all the edges of the cells, and the result is inconsistent with using ForEachVoronoiEdge. There are overlapping parts in ForEachVoronoiCell. I found that there is also this situation in the example of the documentation.

[nol1fe]

Hey, thanks for pointing this out!

To help check out the issue, could you share a minimal example, mainly the list of points you're using? That would make it easier to reproduce the problem with ForEachVoronoiCell and ForEachVoronoiEdge and see what’s going on.

Thanks!

[KiroJong-Zero]

Test.json`

Thank you for your reply, I am using this library in Unity.

using DelaunatorSharp;
using DelaunatorSharp.Unity.Extensions;
using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

namespace Assets.Test
{
    public class Test : MonoBehaviour
    {

        private Delaunator _delaunator; 

        void Awake()
        {
            var jsonPath = "Test";
            var json = Resources.Load<TextAsset>(jsonPath).text;
            var points = JsonUtility.FromJson<Vector2Wrapper>(json).vectors;
            _delaunator = new Delaunator(points.Select(point => new Vector2(point.x, point.y)).ToPoints());
        }

        [System.Serializable]
        private class Vector2Wrapper
        {
            public List<Vector2> vectors;
        }

        private void OnDrawGizmos()
        {
            if(_delaunator == null) return;
            _delaunator.ForEachVoronoiCell(cell =>
            {

                IPoint[] newArray = new IPoint[cell.Points.Length + 1];
                Array.Copy(cell.Points, newArray, cell.Points.Length);
                newArray[newArray.Length - 1] = cell.Points[0];
                for (int i = 0; i < newArray.Length; i++)
                {
                    if (i == newArray.Length - 1) return;
                    var point = newArray[i];
                    var nextPoint = newArray[i + 1];
                    Gizmos.color = Color.white;
                    Gizmos.DrawLine(new Vector3((float)point.X, 0, (float)point.Y), new Vector3((float)nextPoint.X, 0, (float)nextPoint.Y));
                    Gizmos.color = Color.yellow;
                    Gizmos.DrawCube(new Vector3((float)point.X, 0, (float)point.Y), Vector3.one * 2);
                }

            });

            //_delaunator.ForEachVoronoiEdge(edge =>
            //{
            //    Gizmos.DrawLine(new Vector3((float)edge.P.X, 0, (float)edge.P.Y), new Vector3((float)edge.Q.X, 0, (float)edge.Q.Y));
            //});
        }
    }
}

[nol1fe]

Unfortunately, I couldn't find a solution to this problem.

I suspect it might be related to LINK
"...constructing the Voronoi cell along the convex hull requires projecting the edges outwards and clipping them. The Delaunator library doesn’t provide this functionality."

I've committed an update to the WPF example, where I recreated a minimal case. The issue occurs for DrawVoronoi > ForEachVoronoiCell > cell.Index == 3. If anyone can find a solution, contributions are welcome.

[DominicBeerAlloyed]

These crossing Voronoi edges are happening because the default behaviour is to draw the voronoi diagram using the triangle centroids (not the circumcenters) as the voronoi diagram's nodes. The true voronoi diagram uses circumcenters (which is in the library but it is not the default behaviour). I was about to post a v similar issue and saw this one.

Changing lines 556 & 573 to:
if(triangleVerticeSelector == null) triangleVerticeSelector = GetTriangleCircumcenter;
meant that the example wpf app draws a 'proper' voronoi diagram.
(In my opinion this should be the default behaviour)

[nol1fe]

Ah, you just gave me flashbacks to the past! I totally forgot this was discussed in previous issue