title: Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices
body: <p>I am implementing the Bowyer-Watson algorithm as presented at <a href="http://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm" rel="noreferrer">Wikipedia</a>.  In my implementation, everything works as I would expect up until the last part of the pseudocode:</p>
  
  <pre><code>for each triangle in triangulation // done inserting points, now clean up
       if triangle contains a vertex from original super-triangle
          remove triangle from triangulation
  </code></pre>
  
  <p>If I follow the pseudocode here literally, I can end up with missing triangles in my Delaunay triangulation.</p>
  
  <p>As an example, please consider the images below.  The sites I am triangulating are rendered as blue circles.  The triangles are rendered with black lines (excluding the image borders) and connect sites or bounding/super triangle vertices.  The circumcircles are rendered with gray and their centers are rendered with red circles.  The Voronoi cells are each painted with a different color to (hopefully) make the problem more apparent.</p>
  
  <p>This image shows the state of the triangulation right before performing the steps listed in the pseudocode above.  Note that two of the super triangle's vertices are beyond the right and the bottom of the image.</p>
  
  <p><img src="https://i.stack.imgur.com/dEfrg.png" alt="before super triangle removal"></p>
  
  <p>This image shows the step after removing any triangles that contain super triangle vertices without any further considerations:</p>
  
  <p><img src="https://i.stack.imgur.com/S1AeK.png" alt="after super triangle removal"></p>
  
  <p>The top three vertices should have a new triangle with a circumcenter at the point where the greenish/brownish cells meet.  The problem is that the corner vertex that was shown in the "before" image was inside this circumcircle, so the regular processing of the algorithm never generated this triangle.</p>
  
  <p><strong>How do I express this edge case in pseudocode so I can check for and solve it?</strong> I would like to avoid some horrific "try every combination of sites that shared a triangle with a super triangle vertex for valid circumcircle" loop.</p>
  
  <p>I read the Bowyer and Watson papers a couple years back and will read them again for my answer if necessary.  I was hoping that (1) somebody else might have the answer available and (2) I could use Stack Overflow to look the answer up if I ever run into this question again.</p>
  
  <hr>
  
  <p><strong>Edit</strong></p>
  
  <p>So I have found a relatively cheap but imperfect work-around.  My super triangle is programmatically determined to surround the sites' bounding box without intersecting its sides.  This idea was caused by all sorts of frustrating problems with Java considering some of my calculated circumcenter coordinates or distances between coordinates to be infinite.  This caution led me to make my super triangle so small that its vertices sometimes fell in valid triangles' circumcenters.  Increasing the size of the super triangle has made the problem seem to disappear.  However, it is possible that a triangle on the convex hull can be so obtuse that one of the vertices still could fall inside a valid circumcircle.</p>
  
  <p>I think this means that my initial question is still valid in the face of floating-point number limitations.  Is there a cheap way to guarantee that the Bowyer-Watson algorithm generates a valid triangulation?</p>