Do the random points for a Voronoi diagram need to be ordered?

[nmill99]

I'm having a problem with a set of randomly generated points that don't produce Voronoi cells properly unless I order them on the X-axis from smallest to largest.

Here are the problem sites in the order they were generated: randomSites.Add(new Vector3(2.58301f, -0.07231092f, 0f)); randomSites.Add(new Vector3(4.260807f, 1.725296f, 0f)); randomSites.Add(new Vector3(8.839731f, -3.794293f, 0f)); randomSites.Add(new Vector3(-12.11187f, -0.3448925f, 0f)); randomSites.Add(new Vector3(8.466095f, 2.583772f, 0f)); randomSites.Add(new Vector3(3.597496f, -1.383692f, 0f)); randomSites.Add(new Vector3(3.421845f, 0.8252826f, 0f)); randomSites.Add(new Vector3(-7.763506f, -1.487227f, 0f)); randomSites.Add(new Vector3(-0.6644406f, 1.276973f, 0f)); randomSites.Add(new Vector3(7.997253f, 2.485325f, 0f)); randomSites.Add(new Vector3(3.234119f, -3.716683f, 0f)); randomSites.Add(new Vector3(11.37916f, 3.904939f, 0f)); randomSites.Add(new Vector3(11.13493f, -0.3131549f, 0f)); randomSites.Add(new Vector3(6.510168f, 7.292708f, 0f)); randomSites.Add(new Vector3(-2.473285f, 5.793113f, 0f)); randomSites.Add(new Vector3(-8.900781f, -1.143157f, 0f));

If I reorder these, the Voronoi diagrams are generated correctly: randomSites.Add(new Vector3(-12.11187f, -0.3448925f, 0f)); randomSites.Add(new Vector3(-8.900781f, -1.143157f, 0f)); randomSites.Add(new Vector3(-7.763506f, -1.487227f, 0f)); randomSites.Add(new Vector3(-2.473285f, 5.793113f, 0f)); randomSites.Add(new Vector3(-0.6644406f, 1.276973f, 0f)); randomSites.Add(new Vector3(2.58301f, -0.07231092f, 0f)); randomSites.Add(new Vector3(3.234119f, -3.716683f, 0f)); randomSites.Add(new Vector3(3.421845f, 0.8252826f, 0f)); randomSites.Add(new Vector3(3.597496f, -1.383692f, 0f)); randomSites.Add(new Vector3(4.260807f, 1.725296f, 0f)); randomSites.Add(new Vector3(6.510168f, 7.292708f, 0f)); randomSites.Add(new Vector3(7.997253f, 2.485325f, 0f)); randomSites.Add(new Vector3(8.466095f, 2.583772f, 0f)); randomSites.Add(new Vector3(8.839731f, -3.794293f, 0f)); randomSites.Add(new Vector3(11.13493f, -0.3131549f, 0f)); randomSites.Add(new Vector3(11.37916f, 3.904939f, 0f));

I've uploaded a picture of the Voronoi gizmos before after sorting here (look in Orion's belt): https://imgur.com/a/2MpFrIu

[nmill99]

I've just tried to recreate this issue in the Habrador Test Scene and haven't had any luck. The issue might very well be in my own code. If I don't update for a few days, then it's probably my own issue.

[nmill99]

I've been able to recreate the issue in the Habrardor Test Scene. Below is the original code from the test scene and below that is the problem scenario.

` //// Original code: //float max = halfMapSize; //float min = -halfMapSize;

    //for (int i = 0; i < numberOfPoints; i++)
    //{
    //    float randomX = Random.Range(min, max);
    //    float randomZ = Random.Range(min, max);

    //    randomSites.Add(new Vector3(randomX, 0f, randomZ));
    //}

    ////Points outside of the screen for voronoi which has some cells that are infinite
    //float bigSize = halfMapSize * 5f;

    ////Star shape which will give a better result when a cell is infinite large
    ////When using other shapes, some of the infinite cells misses triangles
    //randomSites.Add(new Vector3(0f, 0f, bigSize));
    //randomSites.Add(new Vector3(0f, 0f, -bigSize));
    //randomSites.Add(new Vector3(bigSize, 0f, 0f));
    //randomSites.Add(new Vector3(-bigSize, 0f, 0f));

    //Problem scenario
    float xMax = 12.40375f;
    float xMin = -12.40375f;
    float zMax = 5.945362f;
    float zMin = -6.285754f;

    randomSites.Add(new Vector3(2.58301f, 0f, -2.07231092f));
    randomSites.Add(new Vector3(4.260807f, 0f, -0.274704f));
    randomSites.Add(new Vector3(8.839731f, 0f, -5.794293f));
    randomSites.Add(new Vector3(-12.11187f, 0f, -3.3448925f));
    randomSites.Add(new Vector3(8.466095f, 0f, 0.583772f));
    randomSites.Add(new Vector3(3.597496f, 0f, -3.383692f));
    randomSites.Add(new Vector3(3.421845f, 0f, -1.1747174f));
    randomSites.Add(new Vector3(-7.763506f, 0f, -3.487227f));
    randomSites.Add(new Vector3(-0.6644406f, 0f, -0.723027f));
    randomSites.Add(new Vector3(7.997253f, 0f, 0.485325f));
    randomSites.Add(new Vector3(3.234119f, 0f, -5.716683f));
    randomSites.Add(new Vector3(11.37916f, 0f, 1.904939f));
    randomSites.Add(new Vector3(11.13493f, 0f, -2.3131549f));
    randomSites.Add(new Vector3(6.510168f, 0f, 5.292708f));
    randomSites.Add(new Vector3(-2.473285f, 0f, 3.793113f));
    randomSites.Add(new Vector3(-8.900781f, 0f, -3.143157f));

    // Set outerbound size (star shape) & image center points
    float xBigSize = (xMax - xMin) * 5f;
    float zBigSize = (zMax - zMin) * 5f;

    randomSites.Add(new Vector3(0f, 0f, zBigSize));
    randomSites.Add(new Vector3(0f, 0f, -zBigSize));
    randomSites.Add(new Vector3(xBigSize, 0f, 0f));
    randomSites.Add(new Vector3(-xBigSize, 0f, 0f));

`

[Habrador]

I fixed the problem. To generate the Voronoi I'm using a Delaunay triangulation. I've implemented several algorithms to generate Delaunay and the one I was using to generate Voronoi has apparently some problems with colinear points, so it was generating a really flat triangle, which broke the Voronoi:

So I changed the Delaunay algorithm to another one which is both faster and more accurate. But that one requires that the points are normalized or it will not work. You can see that it's generating a better triangulation and thus a better Voronoi.

[nmill99]

Just wanted to say thanks for your fast turnaround! New method seem to work great so far.