+
+# Split a polygon into triangles
+# Useful for converting a concave polygon into multiple convex ones
+fun triangulate(pts: Array[Point[Float]], results: Array[ConvexPolygon]) do
+ var poly = new Polygon(pts)
+ poly.sort_ccw
+ pts = poly.points
+ recursive_triangulate(pts, results)
+end
+
+private fun recursive_triangulate(pts: Array[Point[Float]], results: Array[ConvexPolygon]) do
+ if pts.length == 3 then
+ results.add(new ConvexPolygon(pts))
+ return
+ end
+ var prev = pts[pts.length - 1]
+ var curr = pts[0]
+ var next = pts[1]
+ for i in [1..pts.length[ do
+ if turn_left(prev, curr, next) then
+ prev = pts[i-1]
+ curr = next
+ if i+1 == pts.length then next = pts[pts.length - 1] else next = pts[i+1]
+ continue
+ end
+ var contains = false
+ var triangle = new ConvexPolygon(new Array[Point[Float]].with_items(prev, curr, next))
+ for p in pts do
+ if p != prev and p != curr and p != next then
+ if triangle.contain(p) then
+ contains = true
+ break
+ end
+ end
+ end
+ if not contains then
+ results.add(triangle)
+ pts.remove(curr)
+ recursive_triangulate(pts, results)
+ break
+ end
+ prev = pts[i-1]
+ curr = next
+ if i+1 == pts.length then next = pts[pts.length - 1] else next = pts[i+1]
+ end
+end