Method to get boundary of a Mesh as a polygon

[burningmime]

While it's possible to enumerate boundary triangles from a point cloud mesh, it's not clear if these are ordered such that a Polygon could be created from them (in fact given they're from a .NET dictionary, the order seems to be random).

It seems like the best way to do this would be to enumerate boundary vertices, pick one arbitrarily, and then follow boundary edges. This might work (I'm implementing it now). But could I suggest that as a feature?

[wo80]

Hi.
You might want to take a look at example 2. Does this work for you?

[burningmime]

Thanks for the response! So that polygon has all the points, not just boundary ones. Triangulating only the convex hull may be appropriate for some use cases, but I need the concave hull/alpha-shape. With convex=false, the resulting triangulation is a bit of a mess and includes interior points. Eg, I tossed together a sphere and a rotated cylinder, then triangulated the intersection with the XY plane:

Here's the same if I follow the boundary of the mesh; it is much "cleaner".

Here's how I'm getting the bounday...

static Contour findBoundaryContour(IMesh mesh)
{
    mesh.Renumber();
    Vertex first = mesh.Vertices.FirstOrDefault(v => v.Label > 0);
    if(ReferenceEquals(first, null))
        throw new Exception("Could not find any boundary vertices");
    VertexCirculator circulator = new((TriangleNet.Mesh) mesh);
    BitArray visited = new(mesh.Vertices.Count);
    List<Vertex> boundary = new();
    Vertex current = first;
    
LNextVertex:
    {
        boundary.Add(new Vertex(current.X, current.Y));
        visited[current.ID] = true;
        foreach(Vertex next in circulator.EnumerateVertices(current))
        {
            if(next.Label > 0 && !visited[next.ID])
            {
                current = next;
                goto LNextVertex;
            }
        }
    }

    if(boundary.Count < 3)
    {
        throw new Exception("Did not enumerate enough boundary vertices to create a polygon -- this can " +
            "happen if you have only a quad or something intersecting the XY plane. Make sure all " +
            "intersecting geometry is solid.");
    }
    
    return new Contour(boundary);
}

Except that's not always in counterclockwise order (easy to fix), but also it might not work in all cases since it picks the first boundary triangle it encounters at each point.

(My ultimate goal is, given a mesh for a window or door, get a mesh for a wall with an appropriately-sized hole cut out for that window or door. The door or window mesh may cross the XY plane at many points, but only the outermost are of interest.)

[wo80]

Ok, so you mentioned a point cloud mesh which made me think you were triangulating a point cloud (no segments involved).

To get the boundary of a non-convex mesh, try the following gist (as a starting point):

https://gist.github.com/wo80/f6a119a5f46afc02fda8765b07099348

The image shows the mesh of the input polygon (two intersecting circles) and the mesh of the extracted boundary polygon.

[burningmime]

It is point cloud -- the inputs are just all the points at which any edge intersects the XY plane and any ordering is not guarunteed. The initial IMesh is created via...

Vertex[] inputVertices = /* ... */;
IMesh pointCloudMesh = new Dwyer().Triangulate(inputVertices, new Configuration());

It seems like the Segments property is empty after creating a mesh that way.

[wo80]

Alright, I'm beginning to understand the problem...

With the setup you describe, there is no way to reliably extract the boundary. The best thing you can do is to project and triangulate each object separately, extract the boundary contour of each object and then extract the boundary of the union of these contours. Something along the lines

var obj1 = Generate.Circle(2d, new Point(3d, 0d), 0.2, 2);
var obj2 = Generate.Circle(3d, new Point(0d, 0d), 0.5, 3);

var contour1 = GetConvexHull(obj1.Points);
var contour2 = GetConvexHull(obj2.Points);

var poly = new Polygon();

// Union of boundary contours.
poly.Add(contour1);
poly.Add(contour2);

// Make sure there are no duplicate vertex ids.
int i = 0;
poly.Points.ForEach(v => v.ID = i++);

var mesh = poly.Triangulate();

// Now use code from gist to get the boundary...
var boundary = Issue32.GetBoundaryContour(mesh);

var contourPoly = new Polygon();
contourPoly.Add(boundary);

SvgImage.Save(contourPoly.Triangulate(), "issue32-contour-2.svg", 500, points: false);

Contour GetConvexHull(List<Vertex> points)
{
    var poly = new Polygon();
    poly.Points.AddRange(points);
    var mesh = poly.Triangulate(new ConstraintOptions() { Convex = true });
    return new Contour(mesh.Segments.Select(s => s.GetVertex(0)));
}