From 220958c29ad9c7a9a10a2f673d3b580658a1e32e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Alexis=20Laferri=C3=A8re?= Date: Tue, 23 Feb 2016 12:24:47 -0500 Subject: [PATCH] lib/geometry: change triangulate API for easier usage MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The old API was counter intuitive. The result was put in a parameter and the list of points was cleared in the process. Signed-off-by: Alexis Laferrière --- lib/geometry/polygon.nit | 47 +++++++++++++++++++++++++++------------------- 1 file changed, 28 insertions(+), 19 deletions(-) diff --git a/lib/geometry/polygon.nit b/lib/geometry/polygon.nit index 94ad1c9..1be832e 100644 --- a/lib/geometry/polygon.nit +++ b/lib/geometry/polygon.nit @@ -441,31 +441,40 @@ fun turn_left(p1, p2, p3: Point[Float]): Bool do end # 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) - pts = poly.points - recursive_triangulate(pts, results) +# +# 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 -private fun recursive_triangulate(pts: Array[Point[Float]], results: Array[ConvexPolygon]) do - if pts.length == 3 then - results.add(new ConvexPolygon(pts)) +# 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 = pts[pts.length - 1] - var curr = pts[0] - var next = pts[1] - for i in [1..pts.length[ do + 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 = pts[i-1] + prev = points[i-1] curr = next - if i+1 == pts.length then next = pts[pts.length - 1] else next = pts[i+1] + 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 pts do + for p in points do if p != prev and p != curr and p != next then if triangle.contain(p) then contains = true @@ -475,12 +484,12 @@ private fun recursive_triangulate(pts: Array[Point[Float]], results: Array[Conve end if not contains then results.add(triangle) - pts.remove(curr) - recursive_triangulate(pts, results) + points.remove(curr) + triangulate_recursive(points, results) break end - prev = pts[i-1] + prev = points[i-1] curr = next - if i+1 == pts.length then next = pts[pts.length - 1] else next = pts[i+1] + if i+1 == points.length then next = points[points.length - 1] else next = points[i+1] end end -- 1.7.9.5