Computing a hole in a triangulated polygon mesh

Question

I'm working on a visualizer in WPF which has a function to display a cutting plane through a 3-D shape. For example, a 3-d geometry like this:

... is cut with a plane. After cutting, the algorithm identifies all the unique outlines along the cutting plane and populates a list of line segments, in either CW or CCW winding order. Any simple polygon is easy to triangulate and render using the Cutting Ears algorithm, like this:

Given an input of the triangulation on the right, and the inner polyline visible on the plane surface on the left, is there an algorithm which can reconfigure the triangulation to construct a hole outlined by the polyline?

If there are algorithms already rolled in C# or another CLR language, I'd love to learn about them. I'm using the Point3D lists called for by WPF to describe MeshGeometry3D triangle meshes, but I can obviously fill any data structure if needed or spin my own class by studying other language code or pseudocode.

EDIT: See the accepted answer; I'm making use of the C# implementation of Poly2Tri, a Constrained Delaunay Triangulation. However, (images not to scale) the Poly2Tri algorithm (center) failed with a 780-segment polyline, while Cutting Ears (right) did not, until I stripped the inputs of their precision, supplying single precision values upcast as doubles instead of doubles. It now produces a different triangulation than Cutting Ears but respects the boundaries of the outer polyline.

Answer 1

Compute a constrained Delaunay triangulation with the border segments as constraints. Determine an inner triangle. From there grow the area until you reach borders. As a positive side effect such a triangulation will have better shaped triangles.

Answer 2

Had to resolve the exact same problem when making a export/import plugin between SketchUp and 3DSMax. Sketchup use a concept or outer and inner loops while 3DS Max is pure geometry.

Sadly, I don't have the plugin around, so I will try to remember it as best as I can:

foreach point in outerLoop
{
    // Loop over all other point to find the nearest valid one
    foreach otherPoint in both outerLoop and all innerLoops where otherPoint is not point
    {
        if otherPoint is adjacent to point
            reject otherPoint 

        if distance between point and otherPoint is bigger than previous distance
            reject otherPoint 

        // Test is vector is point outside the geometry in case of convexe shapes
        if cross product of vector from (point - adjacent point) and (point - nearest point) is pointing away from cross product of vectors of (point - both adjacents point)
            reject otherPoint 

        nearestPoint = otherPoint
    }

    for the two adjacentPoint of nearestPoint
    {
        if adjacentPoint is also adjacent to point
            make triangle(point, adjacentPoint, nearestPoint)
        if cross product of vector from (point - adjacent point) and (point - nearest point) is pointing in the same direction as cross product of vectors of (point - both adjacents point)
            make triangle(point, adjacentPoint, nearestPoint)
    }
}

repeat the above for innerLoops point while only checking against other innerLoops

make triangle function should check if the triangle already exist from previous iteration.

It's not super pretty and is kinda brute, but it works with a unlimited number of inner loops and create always the best triangles possible.

I'm pretty sure there would be way to improve its performance, but I never gave it enough time.