Regions on BoundedVoronoi edge creating additional verts

May 22, 2014 at 3:42 PM
Was running into issues with mesh generation around the corners. Everything seemed fine:
Image

However, it looks like BoundedVoronoi is creating additional verts for the regions on the edge.

Image

To test I'm filling a poly shape with 300 random points. Is this intended behaviour?

Rob


Code:
    int totalPointsInternal = (inputPoly.Edges.Length*2);

    float totalPoints = 300;
    float totalArea = inputPoly.CalcArea();

    // for the initial triangle creation 
    // we use these trangles to put random points inside polygon.
    TriangleNet.Geometry.InputGeometry  subGeometryInternal = new TriangleNet.Geometry.InputGeometry(totalPointsInternal);

    // random points
    TriangleNet.Geometry.InputGeometry  internalPointsGeometry = new TriangleNet.Geometry.InputGeometry(totalPointsInternal+(int) totalPoints);


    for (int i =0; i <inputPoly.Edges.Length ; i++){
        if (i!= inputPoly.Edges.Length-1){
            if ( i==0){

                subGeometryInternal.AddPoint(inputPoly.Edges[i].Point0.x,inputPoly.Edges[i].Point0.y);
                subGeometryInternal.AddPoint(inputPoly.Edges[i].Point1.x,inputPoly.Edges[i].Point1.y);
                subGeometryInternal.AddSegment(i,(i+1));

                internalPointsGeometry.AddPoint(inputPoly.Edges[i].Point0.x,inputPoly.Edges[i].Point0.y);
                internalPointsGeometry.AddPoint(inputPoly.Edges[i].Point1.x,inputPoly.Edges[i].Point1.y);
                internalPointsGeometry.AddSegment(i,(i+1));
            }
            else{

                subGeometryInternal.AddPoint(inputPoly.Edges[i].Point1.x,inputPoly.Edges[i].Point1.y);
                subGeometryInternal.AddSegment(i,(i+1));

                internalPointsGeometry.AddPoint(inputPoly.Edges[i].Point1.x,inputPoly.Edges[i].Point1.y);
                internalPointsGeometry.AddSegment(i,(i+1));
            }
        }
        else{
            subGeometryInternal.AddSegment(i,0);

            internalPointsGeometry.AddSegment(i,0);

        }
    }

    TriangleNet.Mesh meshInternal = new TriangleNet.Mesh();
    meshInternal.Triangulate(subGeometryInternal);
    meshInternal.Behavior.ConformingDelaunay = true; 
    meshInternal.Behavior.Quality = true; 


    foreach (var triangle in meshInternal.Triangles){
        Debug.Log (triangle.vertices.Length + " " + triangle.P0 + " " + triangle.P1 + "  " + triangle.P2);

        Vector2 p0 = new Vector2 ((float)  meshInternal.vertices[triangle.P0].x,(float) meshInternal.vertices[triangle.P0].y);
        Vector2 p1 = new Vector2 ((float) meshInternal.vertices[triangle.P1].x,(float) meshInternal.vertices[triangle.P1].y);
        Vector2 p2 = new Vector2 ((float) meshInternal.vertices[triangle.P2].x,(float) meshInternal.vertices[triangle.P2].y);

        Triangle2 tri = new Triangle2(p0,p1,p2);
        float area = (float) tri.CalcArea();
        int percentageOfPoints = Mathf.FloorToInt ((area/totalArea)*totalPoints);
        for (int i=0; i <percentageOfPoints; i ++){
            Vector2 randomPoint = RandomPointInTriangle(p0,p1,p2);
            internalPointsGeometry.AddPoint(randomPoint.x,randomPoint.y);
        }

    }

    TriangleNet.Mesh meshInternalIncludingInternalPoints = new TriangleNet.Mesh();
    meshInternalIncludingInternalPoints.Triangulate(internalPointsGeometry);
    meshInternalIncludingInternalPoints.Behavior.ConformingDelaunay = true; 
    TriangleNet.Tools.BoundedVoronoi returnVoronoi = new TriangleNet.Tools.BoundedVoronoi (meshInternalIncludingInternalPoints);
    DrawBoundedVoronoi(returnVoronoi);
Coordinator
May 22, 2014 at 9:49 PM
Edited May 22, 2014 at 9:51 PM
However, it looks like BoundedVoronoi is creating additional verts for the regions on the edge.
[...] Is this intended behaviour?
What do you mean by additional verts? What's the second image supposed to show me?
May 22, 2014 at 10:30 PM
Sorry, should have highlighted it better - the corners in second image show long thin lines stretching to the middle of the region edge. (the light green and light brown). Each one of these edge regions has a couple of additional verts. Make more sense?
May 23, 2014 at 12:18 PM
If anyone else runs into this problem, a very quick hack to fix is to comment out :
regions.Add(region);
From the ConstructBoundaryCell function within BoundedVoronoi.

The corner regions will be missing (as well as one or two mid-edge) - however it stops the peculiar "V" shapes which play hell with region to mesh conversion. Below is the result

Image

If there's a more elegant solution, would be great to hear it - however I think I've taken up enough of your time :)
Coordinator
May 24, 2014 at 6:19 PM
Edited May 24, 2014 at 6:22 PM
Well, I see what you mean, but I can't reproduce the problem.

Maybe there's something wrong with your geometry:
Vector2 randomPoint = RandomPointInTriangle(p0,p1,p2);
internalPointsGeometry.AddPoint(randomPoint.x,randomPoint.y);
Are you sure that no points are created that lie on an existing segment?

You could also check for degenerate triangles:
const double eps = 1e-16;
float area = (float) tri.CalcArea();
if (area < eps) throw new Exception("degenerate triangle");
May 25, 2014 at 7:09 PM
Edited May 25, 2014 at 7:11 PM
I've added a check to ensure no random points are on the triangle line or outside of it. So that rules that out :( good idea though!

The math lib I'm using has a good check for degenerate triangles - no triangles were flagged. Then I worked out that when the BoundaryCell region is triangulated no triangles would be degenerated (obviously!).. So I sadly can't capture the dud points.

For the region created by ConstructBoundaryCell I've gone through each vert and put a yellow line:
Image

It looks like it's (correctly) filling in the corners to give a uniform shape to the BoundedVoronoi. Rather than create (n) small regions for each corner it makes one large region (with points mid-way along each edge)... which, actually, seems like a very sensible way of doing things. Just not ideal for what I'm trying to do, which is pretty obscure :)

I'm thinking it might be easier to not include BoundaryCell then go through each corner, find surrounding verts, then manually create mini corner regions.
Coordinator
May 26, 2014 at 12:29 PM
Edited May 26, 2014 at 12:30 PM
I still don't get it. If those additional vertices are created by the BoundedVoronoi code, it's obviously an error. But I've never encountered those strange "V" shapes. Could you dump all the geometry data and upload it somewhere so I can have a look at it?
 // Create .ele and .poly files
TriangleNet.IO.FileWriter.Write(meshInternalIncludingInternalPoints, "test.ele");

using (var voro = new StreamWriter("test.voro"))
{
    voro.WriteLine(returnVoronoi.Regions.Count);

    foreach (var region in returnVoronoi.Regions)
    {
        voro.WriteLine("{0} {1} {2} {3}", region.Vertices.Count, region.ID,
            region.Generator.X, region.Generator.Y);

        foreach (var p in region.Vertices)
        {
            voro.WriteLine("{0} {1} {2}", p.ID, p.X, p.Y);
        }
    }
}