title: Computing a hole in a triangulated polygon mesh
body: <p>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:</p>
  
  <p><img src="https://i.stack.imgur.com/kT9ZG.png" alt="Full Geometry"></p>
  
  <p>... 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:</p>
  
  <p><img src="https://i.stack.imgur.com/iaI7O.png" alt="Cut Plane Image"> <img src="https://i.stack.imgur.com/ArSZ5.png" alt="enter image description here"></p>
  
  <p>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? </p>
  
  <p>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. </p>
  
  <p>EDIT: See the accepted answer; I'm making use of the C# implementation of <a href="http://code.google.com/p/poly2tri/" rel="nofollow noreferrer">Poly2Tri</a>, 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.</p>
  
  <p><img src="https://i.stack.imgur.com/sCh5U.jpg" alt="ComplexPoly"> <img src="https://i.stack.imgur.com/ujKic.jpg" alt="ComplexCDT"> <img src="https://i.stack.imgur.com/MlQkb.jpg" alt="ComplexEars"></p>