+
+# Split a polygon into triangles
+#
+# Useful for converting a concave polygon into multiple convex ones.
+#
+# See: the alternative `triangulate_recursive` uses arrays in-place.
+fun triangulate(points: Array[Point[Float]]): Array[ConvexPolygon]
+do
+ var results = new Array[ConvexPolygon]
+ triangulate_recursive(points.clone, results)
+ return results
+end
+
+# Split a polygon into triangles using arrays in-place
+#
+# Consumes the content of `points` and add the triangles to `results`.
+#
+# See: the alternative `triangulate` which does not modify `points` and returns a new array.
+fun triangulate_recursive(points: Array[Point[Float]], results: Array[ConvexPolygon]) do
+ if points.length == 3 then
+ results.add(new ConvexPolygon(points))
+ return
+ end
+ var prev = points[points.length - 1]
+ var curr = points[0]
+ var next = points[1]
+ for i in [1..points.length[ do
+ if turn_left(prev, curr, next) then
+ prev = points[i-1]
+ curr = next
+ if i+1 == points.length then next = points[points.length - 1] else next = points[i+1]
+ continue
+ end
+ var contains = false
+ var triangle = new ConvexPolygon(new Array[Point[Float]].with_items(prev, curr, next))
+ for p in points 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)
+ points.remove(curr)
+ triangulate_recursive(points, results)
+ break
+ end
+ prev = points[i-1]
+ curr = next
+ if i+1 == points.length then next = points[points.length - 1] else next = points[i+1]
+ end
+end