title: How do you triangulate a polygon in Shapely?
body: <p>How do you triangulate a polygon in Shapely? Shapely actually offers a <a href="https://shapely.readthedocs.io/en/stable/manual.html#shapely.ops.triangulate" rel="nofollow noreferrer">triangulate()</a> function, but that only triangulates the vertices of the polygon as a point set. For convex polygons the solution is the same, but for non-convex you get extra triangles. I tried removing all triangles that are outside the polygon, but sometimes triangles can cross the polygon boundary (see below image). I guess I could remove those too, then substract the remaining triangles from the polygon and recursively triangulate the components of that difference. But is there a simpler way?</p>
  <p>Example where polygon triangulation is not a subset of vertices triangulation (polygon boundary wider and grey, triangle boundaries darker and thinner):
  <a href="https://i.stack.imgur.com/UBh3V.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/UBh3V.png" alt="Example where polygon triangulation is not a subset of vertices triangulation (polygon boundary wider and grey, triangle boundaries darker and thinner)" /></a>
  Code to produce this geometry:</p>
  <pre><code>from shapely.geometry import Polygon
  from shapely.ops import triangulate
  
  polygon = Polygon( [ (0,0), (0,3), (5,3), (2,4), (6,4), (6,0) ])
  delauney=triangulate(polygon)
  </code></pre>