--- /dev/null
+# This file is part of NIT (http://www.nitlanguage.org).
+#
+# Copyright 2015 Romain Chanoir <romain.chanoir@viacesi.fr>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Convex Polygons manipulations
+module polygon
+
+import points_and_lines
+
+# Convex Polygon class
+class ConvexPolygon
+
+ # Vertices of this polygon
+ var points = new Array[Point[Float]]
+
+ # Init this polygon with a list of `points`
+ # REQUIRE `pts.length == 3`
+ init with_vertices(pts: Array[Point[Float]]) do
+ assert pts.length >= 3
+ points.add_all(pts)
+ end
+
+ # Get an array of the x coordinates of the vertices
+ private fun x_coordinates: Array[Float] do
+ return [for p in points do p.x]
+ end
+
+ # Get an array of the y coordinates of the vertices
+ private fun y_coordinates: Array[Float] do
+ return [for p in points do p.y]
+ end
+
+ # Get a matrice containing the coordinates of the vertices
+ private fun vertices: Array[Array[Float]] do
+ var vertices = new Array[Array[Float]]
+ for i in [0..points.length[ do
+ var temp = new Array[Float]
+ temp.add(points[i].x)
+ temp.add(points[i].y)
+ vertices.add(temp)
+ end
+ return vertices
+ end
+
+ # Returns the axes corresponding to the edges of the polygon, used for collision detection
+ private fun axes: Array[Point[Float]] do
+ var axes = new Array[Point[Float]]
+ for i in [0..points.length[ do
+ var p1 = new Point[Float](points[i].x, points[i].y)
+ var p2 = new Point[Float](points[(i+1) % points.length].x, points[(i+1) % points.length].y)
+ var edge = new Point[Float](p1.x - p2.x, p1.y - p2.y)
+ var normal = new Point[Float](-edge.y, edge.x)
+ axes[i] = normal
+ end
+ return axes
+ end
+
+ # Sort the vertices in counter clockwise order
+ #
+ # ~~~
+ # var p1 = new Point[Float](0.0, 0.0)
+ # var p2 = new Point[Float](5.0, 0.0)
+ # var p3 = new Point[Float](0.0, 5.0)
+ # var p4 = new Point[Float](5.0, 5.0)
+ # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly = new ConvexPolygon.with_vertices(arr)
+ # poly.sort_ccw
+ # assert poly.points == [p4, p2, p1, p3]
+ # ~~~
+ fun sort_ccw do
+ var sorter = new CounterClockWiseSort.with_center(vertices)
+ sorter.sort(points)
+ end
+
+ # Sort the vertices in clockwise order
+ #
+ # ~~~
+ # var p1 = new Point[Float](0.0, 0.0)
+ # var p2 = new Point[Float](5.0, 0.0)
+ # var p3 = new Point[Float](0.0, 5.0)
+ # var p4 = new Point[Float](5.0, 5.0)
+ # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly = new ConvexPolygon.with_vertices(arr)
+ # poly.sort_cw
+ # assert poly.points == [p3, p1, p2, p4]
+ # ~~~
+ fun sort_cw do
+ var sorter = new ClockWiseSort.with_center(vertices)
+ sorter.sort(points)
+ end
+
+ # Does this polygon intersects `other` ?
+ #
+ # ~~~
+ # var p1 = new Point[Float](0.0, 0.0)
+ # var p2 = new Point[Float](5.0, 0.0)
+ # var p3 = new Point[Float](0.0, 5.0)
+ # var p4 = new Point[Float](5.0, 5.0)
+ # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly = new ConvexPolygon.with_vertices(arr)
+ # poly.sort_ccw
+ # p1 = new Point[Float](2.5, 2.5)
+ # p2 = new Point[Float](7.5, 2.5)
+ # p3 = new Point[Float](2.5, 7.5)
+ # p4 = new Point[Float](7.5, 7.5)
+ # arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly2 = new ConvexPolygon.with_vertices(arr)
+ # poly2.sort_ccw
+ # assert poly.intersects(poly2)
+ # ~~~
+ fun intersects(other: ConvexPolygon): Bool do
+ assert is_convex
+
+ var axes1 = axes
+ var axes2 = other.axes
+ for axis in axes1 do
+ var project1 = project(axis)
+ var project2 = other.project(axis)
+ if not project1.overlap(project2) then return false
+ end
+ for axis in axes2 do
+ var project1 = project(axis)
+ var project2 = other.project(axis)
+ if not project1.overlap(project2) then return false
+ end
+ return true
+ end
+
+ # Generate a projection of an edge of the polygon on a given axis
+ private fun project(axis: Point[Float]): Projection do
+ var min = axis.x * points[0].x + axis.y * points[0].y
+ var max = min
+ for i in [0..points.length[ do
+ var p = axis.x * points[i].x + axis.y * points[i].y
+ if p < min then min = p
+ if p > max then max = p
+ end
+ var projection = new Projection(min, max)
+ return projection
+ end
+
+ # Is this polygon convex ?
+ #
+ # ~~~
+ # var p1 = new Point[Float](0.0, 0.0)
+ # var p2 = new Point[Float](5.0, 0.0)
+ # var p3 = new Point[Float](0.0, 5.0)
+ # var p4 = new Point[Float](5.0, 5.0)
+ # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly = new ConvexPolygon.with_vertices(arr)
+ # poly.sort_ccw
+ # assert poly.is_convex
+ # ~~~
+ fun is_convex: Bool do
+ var prev = points[points.length - 2]
+ var curr = points[points.length - 1]
+ var next = points[0]
+ var is_ccw = turn_left(prev, curr, next)
+ for i in [1..points.length[ do
+ prev = curr
+ curr= next
+ next = points[i]
+ if turn_left(prev ,curr, next) != is_ccw then return false
+ end
+ return true
+ end
+
+ # Check if `p` is in the polygon
+ #
+ # ~~~
+ # var p1 = new Point[Float](0.0, 0.0)
+ # var p2 = new Point[Float](5.0, 0.0)
+ # var p3 = new Point[Float](0.0, 5.0)
+ # var p4 = new Point[Float](5.0, 5.0)
+ # var p5 = new Point[Float](2.5, 2.5)
+ # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly = new ConvexPolygon.with_vertices(arr)
+ # poly.sort_ccw
+ # assert poly.contain(p5)
+ # ~~~
+ fun contain(p : Point[Float]): Bool do
+ var prev = points[points.length - 1]
+ var curr = p
+ var next = points[0]
+ var is_ccw = turn_left(prev, curr, next)
+ for i in [1..points.length[ do
+ prev = next
+ next = points[i]
+ if turn_left(prev, curr, next) != is_ccw then return false
+ end
+ return true
+ end
+
+ # Check if the order of the points in the polygon is counter-clockwise
+ # The vertices in the polygon need to be sorted
+ #
+ # ~~~
+ # var p1 = new Point[Float](0.0, 0.0)
+ # var p2 = new Point[Float](5.0, 0.0)
+ # var p3 = new Point[Float](0.0, 5.0)
+ # var p4 = new Point[Float](5.0, 5.0)
+ # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly = new ConvexPolygon.with_vertices(arr)
+ # poly.sort_ccw
+ # assert poly.is_ccw
+ # ~~~
+ fun is_ccw: Bool do
+ var min = points[0].y
+ var min_index = 0
+ for i in [1..points.length - 1[ do
+ if points[i].y < min then
+ min = points[i].y
+ min_index = i
+ end
+ end
+ var prev = points[(min_index - 1 + points.length) % points.length]
+ var next = points[(min_index + 1) % points.length]
+ return not turn_left(prev, points[min_index], next)
+ end
+
+ # Remove `p` from the vertices, keeping at least 3 vertices
+ fun delete_vertex(p: Point[Float]) do
+ if points.length > 3 then
+ points.remove(p)
+ end
+ end
+
+ # Add a vertex to the polygon
+ #
+ # ~~~
+ # var p1 = new Point[Float](0.0, 0.0)
+ # var p2 = new Point[Float](5.0, 0.0)
+ # var p3 = new Point[Float](0.0, 5.0)
+ # var p4 = new Point[Float](5.0, 5.0)
+ # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
+ # var poly = new ConvexPolygon.with_vertices(arr)
+ # var p5 = new Point[Float](2.5, 7.5)
+ # assert poly.add_vertex(p5)
+ # ~~~
+ fun add_vertex(p: Point[Float]): Bool do
+ assert points.length >= 3
+ var temp_list = points.clone
+ temp_list.add(p)
+ var temp_polygon = new ConvexPolygon.with_vertices(temp_list)
+ temp_polygon.sort_ccw
+ if temp_polygon.is_convex then
+ points = temp_polygon.points
+ return true
+ else
+ return false
+ end
+ end
+end
+
+# Projection of an edge of a `ConvexPolygon` used for intersection test
+private class Projection
+ var min: Float is writable
+ var max: Float is writable
+
+ fun overlap(other: Projection): Bool do
+ return not (min > other.max or other.min > max)
+ end
+end
+
+private class PointXCompare
+ super Comparator
+
+ redef type COMPARED: Point[Float]
+
+ redef fun compare(a,b : COMPARED): Int do
+ if a.x == b.x then
+ if a.y == b.y then return 0
+ if a.y > b.y then return - 1
+ return 1
+ else
+ if a.x > b.x then return -1
+ return 1
+ end
+ end
+end
+
+# Sorter for polygon vertices
+private abstract class PolygonSorter
+ super Comparator
+
+ redef type COMPARED: Point[Float]
+
+ # Center of the polygon's points
+ var center: COMPARED
+
+ # init calculating the center
+ init with_center(pts : Array[Array[Float]]) do
+ center = calc_center(pts)
+ end
+
+ # Calculate the center
+ fun calc_center(pts : Array[Array[Float]]): COMPARED do
+ var sumx = 0.0
+ var sumy = 0.0
+ for ap in pts do
+ sumx += ap[0]
+ sumy += ap[1]
+ end
+ return new Point[Float](sumx / pts.length.to_f, sumy / pts.length.to_f)
+ end
+end
+
+# Sort the vertices of a polygon in counter clockwise order
+private class CounterClockWiseSort
+ super PolygonSorter
+
+ redef fun compare(a,b: COMPARED): Int do
+ if a.x == b.x and a.y == b.y then return 0
+ if a.x - center.x >= 0.0 and b.x - center.x < 0.0 then return -1
+ if a.x - center.x < 0.0 and b.x - center.x >= 0.0 then return 1
+ if a.x - center.x == 0.0 and b.x - center.x == 0 then
+ if a.y - center.y >= 0.0 or b.y - center.y >= 0.0 then
+ if a.y > b.y then return -1
+ return 1
+ end
+ if b.y > a.y then return -1
+ return 1
+ end
+
+ var det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
+ if det > 0.0 then return 1
+ if det < 0.0 then return -1
+
+ var d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
+ var d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
+ if d1 > d2 then return -1
+ return 1
+ end
+end
+
+# Sort the vertices of a polygon in clockwise order
+private class ClockWiseSort
+ super PolygonSorter
+
+ redef fun compare(a,b: COMPARED): Int do
+ if a.x == b.x and a.y == b.y then return 0
+ if a.x - center.x >= 0.0 and b.x - center.x < 0.0 then return 1
+ if a.x - center.x < 0.0 and b.x - center.x >= 0.0 then return -1
+ if a.x - center.x == 0.0 and b.x - center.x == 0 then
+ if a.y - center.y >= 0.0 or b.y - center.y >= 0.0 then
+ if a.y > b.y then return 1
+ return -1
+ end
+ if b.y > a.y then return 1
+ return -1
+ end
+
+ var det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
+ if det > 0.0 then return -1
+ if det < 0.0 then return 1
+
+ var d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
+ var d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
+ if d1 > d2 then return 1
+ return -1
+ end
+end
+
+
+# Get the convex hull of the set of `points`
+#
+# ~~~
+# var p1 = new Point[Float](0.0, 0.0)
+# var p2 = new Point[Float](5.0, 0.0)
+# var p3 = new Point[Float](0.0, 5.0)
+# var p4 = new Point[Float](5.0, 5.0)
+# var p5 = new Point[Float](2.5, 2.5)
+# var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4, p5)
+# var poly = convex_hull(arr)
+# assert poly.points == [p4, p3, p1, p2]
+# ~~~
+fun convex_hull(points: Array[Point[Float]]): ConvexPolygon do
+ var sorter = new PointXCompare
+ sorter.sort(points)
+ var l = points.length
+
+ var pl1 = new Array[Point[Float]]
+ var pl2 = new Array[Point[Float]]
+ for i in [0..l[ do
+ while pl2.length >= 2 and not turn_left(pl2[pl2.length - 2], pl2[pl2.length - 1], points[i]) do
+ pl2.remove(pl2.last)
+ end
+ pl2.add(points[i])
+ end
+ var i = l - 1
+ while i >= 0 do
+ while pl1.length >= 2 and not turn_left(pl1[pl1.length - 2], pl1[pl1.length - 1], points[i]) do
+ pl1.remove(pl1.last)
+ end
+ pl1.add(points[i])
+ i-= 1
+ end
+ pl1.remove_at(pl1.length - 1)
+ pl2.remove_at(pl2.length -1)
+ pl2.add_all(pl1)
+ return new ConvexPolygon.with_vertices(pl2)
+end
+
+# Is the angle between [p1,p2] and [p2,p3] going left (counter clockwise) or right (clockwise) ?
+#
+# ~~~
+# var p1 = new Point[Float](0.0, 0.0)
+# var p2 = new Point[Float](5.0, 0.0)
+# var p3 = new Point[Float](0.0, 5.0)
+# assert turn_left(p1, p2, p3)
+# ~~~
+fun turn_left(p1, p2, p3: Point[Float]): Bool do
+ return ((p2.x - p1.x) * (p3.y - p2.y) - (p3.x - p2.x) * (p2.y - p1.y)) > 0.0
+end
nitlanguage / nit.git / commitdiff