core :: Sys :: triangulate_recursive
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.
# 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
lib/geometry/polygon.nit:455,1--495,3