Voronoi Diagram with triangle boundaries

May 19, 2014 at 3:41 PM
Hi,

Is there an easy way to create a voronoi diagram that is bounded by a triangle?

I generate several random disconnected points in a triangle, triangulate them with delaunay and create a voronoi diagram after that. unfortunately i cant find a way to generate the diagram within the triangle bounds only. I already looked up the documentation but can't seem to find a way to properly achieve what i want. (i already tried bounded voronoi but they seem to work for connected regions only, the points that i have are completely disconnected)
Coordinator
May 19, 2014 at 4:35 PM
Lets say your triangle has points a, b and c. Then, additionally to adding just the points to the InputGeometry, you also have to add the boundary segments:
var geometry = new InputGeometry();
geoemtry.AddPoint(a.X, a.Y);
geoemtry.AddPoint(b.X, b.Y);
geoemtry.AddPoint(c.X, c.Y);
geometry.AddSegment(0, 1);
geometry.AddSegment(1, 2);
geometry.AddSegment(2, 0);

// Add more random points.

var mesh = new Mesh();
mesh.Triangulate(geometry);

var voronoi = new BoundedVoronoi (mesh);
May 19, 2014 at 4:45 PM
Hi,

Thanks for the reply.
When i run that code with my random points added the bounded voronoi class throws a index out of range exception on line 434.
May 19, 2014 at 5:07 PM
I'm also running into issues. As a quick test : I'm creating the outer segments to the shape by jumping through the poly edges. Then I'm adding a test point in the center (there will be more later). I'm getting an "ConstructBvdCell: inconsistent topology." error:
        int totalPoints = (thisTile.poly.Edges.Length*2)+;
        int counter = 0;
        TriangleNet.Geometry.InputGeometry  subGeometry = new TriangleNet.Geometry.InputGeometry(totalPoints);
        for (int i =0; i <thisTile.poly.Edges.Length ; i++){
            Vector3 asV30= new Vector3(thisTile.poly.Edges[i].Point0.x,0,thisTile.poly.Edges[i].Point0.y);
            subGeometry.AddPoint(asV30.x,asV30.z);
            int point0Pos = counter;
            counter ++;

            Vector3 asV31 = new Vector3(thisTile.poly.Edges[i].Point1.x,0,thisTile.poly.Edges[i].Point1.y);
            int point1Pos = counter;
            subGeometry.AddPoint(asV30.x,asV30.z);
            counter ++;
            subGeometry.AddSegment(point0Pos,point1Pos);
            Debug.Log ("segment " + point0Pos + " " + point1Pos);

        }
        Vector2 center = thisTile.poly.CalcCenter();

        subGeometry.AddPoint(center.x,center.y);


        TriangleNet.Mesh newMesh = new TriangleNet.Mesh();
        newMesh.Triangulate(subGeometry);

        TriangleNet.Tools.BoundedVoronoi _subVoronoi = new TriangleNet.Tools.BoundedVoronoi (newMesh);
Any idea what I'm doing wrong?
May 19, 2014 at 5:13 PM
I just tested my polygon within the supplied triangle.net test program and seem to got it working by setting following parameters:

mesh.Behavior.ConformingDelaunay = true;
mesh.Behavior.Quality = true;

I
May 19, 2014 at 5:40 PM
Well, I'd made a typo with my initial code (adding the save value twice) which explains my error. It's now :
int totalPoints = (thisTile.poly.Edges.Length*2)+1;
        int counter = 0;
        TriangleNet.Geometry.InputGeometry  subGeometry = new TriangleNet.Geometry.InputGeometry(totalPoints);
        for (int i =0; i <thisTile.poly.Edges.Length ; i++){
            subGeometry.AddPoint(thisTile.poly.Edges[i].Point0.x,thisTile.poly.Edges[i].Point0.y);
            int point0Pos = counter;
            counter ++;

            subGeometry.AddPoint(thisTile.poly.Edges[i].Point1.x,thisTile.poly.Edges[i].Point1.y);
            int point1Pos = counter;
            counter ++;

            subGeometry.AddSegment(point0Pos,point1Pos);
        }

        Vector2 center = thisTile.poly.CalcCenter();
        subGeometry.AddPoint(center.x,center.y);

        TriangleNet.Mesh newMesh = new TriangleNet.Mesh();
        newMesh.Triangulate(subGeometry);
        newMesh.Behavior.ConformingDelaunay = true; 
        newMesh.Behavior.Quality = true; 
        TriangleNet.Tools.BoundedVoronoi _subVoronoi = new TriangleNet.Tools.BoundedVoronoi (newMesh);
Throwing up the error :
NullReferenceException: Object reference not set to an instance of an object
TriangleNet.Data.Otri.Org () (at Assets/Libs/Triangle/Data/Otri.cs:327)
TriangleNet.Tools.BoundedVoronoi.ConstructCell (TriangleNet.Data.Vertex vertex) (at Assets/Libs/Triangle/Tools/BoundedVoronoi.cs:286)
TriangleNet.Tools.BoundedVoronoi.Generate () (at Assets/Libs/Triangle/Tools/BoundedVoronoi.cs:98)
TriangleNet.Tools.BoundedVoronoi..ctor (TriangleNet.Mesh mesh, Boolean includeBoundary) (at Assets/Libs/Triangle/Tools/BoundedVoronoi.cs:56)
TriangleNet.Tools.BoundedVoronoi..ctor (TriangleNet.Mesh mesh)
Coordinator
May 19, 2014 at 6:36 PM
@both:
Make sure you're using the latest source code. And using the ConformingDelaunay option is always a good idea when working with Voronoi diagrams.

@Gonzorob:
You are adding incorrect segment indices to the geometry.
May 19, 2014 at 6:43 PM
Thats confusing , how are the indices incorrect? Perhaps I've been looking at it too long, but they appear to match the positions of the points...
Coordinator
May 19, 2014 at 7:08 PM
Edited May 19, 2014 at 7:25 PM
Again: I don't know how your geometry is defined, but here's my guess:

thisTile.poly.Edges contains the edges of a closed contour of your polygon. This means (well, at least should mean) that there are exactly n = thisTile.poly.Edges.Length points making up the contour. You are adding 2n points and segments.

EDIT: not 2n segments but n segments with indices (0, 1) to (2n-1, 2n).

EDIT 2:
You can check if duplicate input vertices were discarded setting Behavior.Verbose = true and then look at SimpleLog.Instance.Data.
May 19, 2014 at 7:19 PM
@wo80: Thanks for the help.

As for my case setting the quality behaviour of the mesh solved my problem.
May 19, 2014 at 8:06 PM
wo80 wrote:
Again: I don't know how your geometry is defined, but here's my guess:

thisTile.poly.Edges contains the edges of a closed contour of your polygon. This means (well, at least should mean) that there are exactly n = thisTile.poly.Edges.Length points making up the contour. You are adding 2n points and segments.

EDIT: not 2n segments but n segments with indices (0, 1) to (2n-1, 2n).

EDIT 2:
You can check if duplicate input vertices were discarded setting Behavior.Verbose = true and then look at SimpleLog.Instance.Data.
Of course ! Thanks for your help (again!)