
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 3: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);



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.



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?



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



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 5: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.



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 6:08 PM
Edited May 19, 2014 at 6: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 (2n1, 2n).
EDIT 2:
You can check if duplicate input vertices were discarded setting Behavior.Verbose = true and then look at
SimpleLog.Instance.Data .



@wo80: Thanks for the help.
As for my case setting the quality behaviour of the mesh solved my problem.



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 (2n1, 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!)

