# 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