1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Copyright 2015 Romain Chanoir <romain.chanoir@viacesi.fr>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Convex Polygons manipulations
20 import points_and_lines
22 # Convex Polygon class
25 # Vertices of this polygon
26 var points
= new Array[Point[Float]]
28 # Init this polygon with a list of `points`
29 # REQUIRE `pts.length == 3`
30 init with_vertices
(pts
: Array[Point[Float]]) do
31 assert pts
.length
>= 3
35 # Get an array of the x coordinates of the vertices
36 private fun x_coordinates
: Array[Float] do
37 return [for p
in points
do p
.x
]
40 # Get an array of the y coordinates of the vertices
41 private fun y_coordinates
: Array[Float] do
42 return [for p
in points
do p
.y
]
45 # Get a matrice containing the coordinates of the vertices
46 private fun vertices
: Array[Array[Float]] do
47 var vertices
= new Array[Array[Float]]
48 for i
in [0..points
.length
[ do
49 var temp
= new Array[Float]
57 # Returns the axes corresponding to the edges of the polygon, used for collision detection
58 private fun axes
: Array[Point[Float]] do
59 var axes
= new Array[Point[Float]]
60 for i
in [0..points
.length
[ do
61 var p1
= new Point[Float](points
[i
].x
, points
[i
].y
)
62 var p2
= new Point[Float](points
[(i
+1) % points
.length
].x
, points
[(i
+1) % points
.length
].y
)
63 var edge
= new Point[Float](p1
.x
- p2
.x
, p1
.y
- p2
.y
)
64 var normal
= new Point[Float](-edge
.y
, edge
.x
)
70 # Sort the vertices in counter clockwise order
73 # var p1 = new Point[Float](0.0, 0.0)
74 # var p2 = new Point[Float](5.0, 0.0)
75 # var p3 = new Point[Float](0.0, 5.0)
76 # var p4 = new Point[Float](5.0, 5.0)
77 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
78 # var poly = new ConvexPolygon.with_vertices(arr)
80 # assert poly.points == [p4, p2, p1, p3]
83 var sorter
= new CounterClockWiseSort.with_center
(vertices
)
87 # Sort the vertices in clockwise order
90 # var p1 = new Point[Float](0.0, 0.0)
91 # var p2 = new Point[Float](5.0, 0.0)
92 # var p3 = new Point[Float](0.0, 5.0)
93 # var p4 = new Point[Float](5.0, 5.0)
94 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
95 # var poly = new ConvexPolygon.with_vertices(arr)
97 # assert poly.points == [p3, p1, p2, p4]
100 var sorter
= new ClockWiseSort.with_center
(vertices
)
104 # Does this polygon intersects `other` ?
107 # var p1 = new Point[Float](0.0, 0.0)
108 # var p2 = new Point[Float](5.0, 0.0)
109 # var p3 = new Point[Float](0.0, 5.0)
110 # var p4 = new Point[Float](5.0, 5.0)
111 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
112 # var poly = new ConvexPolygon.with_vertices(arr)
114 # p1 = new Point[Float](2.5, 2.5)
115 # p2 = new Point[Float](7.5, 2.5)
116 # p3 = new Point[Float](2.5, 7.5)
117 # p4 = new Point[Float](7.5, 7.5)
118 # arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
119 # var poly2 = new ConvexPolygon.with_vertices(arr)
121 # assert poly.intersects(poly2)
123 fun intersects
(other
: ConvexPolygon): Bool do
127 var axes2
= other
.axes
129 var project1
= project
(axis
)
130 var project2
= other
.project
(axis
)
131 if not project1
.overlap
(project2
) then return false
134 var project1
= project
(axis
)
135 var project2
= other
.project
(axis
)
136 if not project1
.overlap
(project2
) then return false
141 # Generate a projection of an edge of the polygon on a given axis
142 private fun project
(axis
: Point[Float]): Projection do
143 var min
= axis
.x
* points
[0].x
+ axis
.y
* points
[0].y
145 for i
in [0..points
.length
[ do
146 var p
= axis
.x
* points
[i
].x
+ axis
.y
* points
[i
].y
147 if p
< min
then min
= p
148 if p
> max
then max
= p
150 var projection
= new Projection(min
, max
)
154 # Is this polygon convex ?
157 # var p1 = new Point[Float](0.0, 0.0)
158 # var p2 = new Point[Float](5.0, 0.0)
159 # var p3 = new Point[Float](0.0, 5.0)
160 # var p4 = new Point[Float](5.0, 5.0)
161 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
162 # var poly = new ConvexPolygon.with_vertices(arr)
164 # assert poly.is_convex
166 fun is_convex
: Bool do
167 var prev
= points
[points
.length
- 2]
168 var curr
= points
[points
.length
- 1]
170 var is_ccw
= turn_left
(prev
, curr
, next
)
171 for i
in [1..points
.length
[ do
175 if turn_left
(prev
,curr
, next
) != is_ccw
then return false
180 # Check if `p` is in the polygon
183 # var p1 = new Point[Float](0.0, 0.0)
184 # var p2 = new Point[Float](5.0, 0.0)
185 # var p3 = new Point[Float](0.0, 5.0)
186 # var p4 = new Point[Float](5.0, 5.0)
187 # var p5 = new Point[Float](2.5, 2.5)
188 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
189 # var poly = new ConvexPolygon.with_vertices(arr)
191 # assert poly.contain(p5)
193 fun contain
(p
: Point[Float]): Bool do
194 var prev
= points
[points
.length
- 1]
197 var is_ccw
= turn_left
(prev
, curr
, next
)
198 for i
in [1..points
.length
[ do
201 if turn_left
(prev
, curr
, next
) != is_ccw
then return false
206 # Check if the order of the points in the polygon is counter-clockwise
207 # The vertices in the polygon need to be sorted
210 # var p1 = new Point[Float](0.0, 0.0)
211 # var p2 = new Point[Float](5.0, 0.0)
212 # var p3 = new Point[Float](0.0, 5.0)
213 # var p4 = new Point[Float](5.0, 5.0)
214 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
215 # var poly = new ConvexPolygon.with_vertices(arr)
220 var min
= points
[0].y
222 for i
in [1..points
.length
- 1[ do
223 if points
[i
].y
< min
then
228 var prev
= points
[(min_index
- 1 + points
.length
) % points
.length
]
229 var next
= points
[(min_index
+ 1) % points
.length
]
230 return not turn_left
(prev
, points
[min_index
], next
)
233 # Remove `p` from the vertices, keeping at least 3 vertices
234 fun delete_vertex
(p
: Point[Float]) do
235 if points
.length
> 3 then
240 # Add a vertex to the polygon
243 # var p1 = new Point[Float](0.0, 0.0)
244 # var p2 = new Point[Float](5.0, 0.0)
245 # var p3 = new Point[Float](0.0, 5.0)
246 # var p4 = new Point[Float](5.0, 5.0)
247 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
248 # var poly = new ConvexPolygon.with_vertices(arr)
249 # var p5 = new Point[Float](2.5, 7.5)
250 # assert poly.add_vertex(p5)
252 fun add_vertex
(p
: Point[Float]): Bool do
253 assert points
.length
>= 3
254 var temp_list
= points
.clone
256 var temp_polygon
= new ConvexPolygon.with_vertices
(temp_list
)
257 temp_polygon
.sort_ccw
258 if temp_polygon
.is_convex
then
259 points
= temp_polygon
.points
267 # Projection of an edge of a `ConvexPolygon` used for intersection test
268 private class Projection
269 var min
: Float is writable
270 var max
: Float is writable
272 fun overlap
(other
: Projection): Bool do
273 return not (min
> other
.max
or other
.min
> max
)
277 private class PointXCompare
280 redef type COMPARED: Point[Float]
282 redef fun compare
(a
,b
: COMPARED): Int do
284 if a
.y
== b
.y
then return 0
285 if a
.y
> b
.y
then return - 1
288 if a
.x
> b
.x
then return -1
294 # Sorter for polygon vertices
295 private abstract class PolygonSorter
298 redef type COMPARED: Point[Float]
300 # Center of the polygon's points
303 # init calculating the center
304 init with_center
(pts
: Array[Array[Float]]) do
305 init(calc_center
(pts
))
308 # Calculate the center
309 fun calc_center
(pts
: Array[Array[Float]]): COMPARED do
316 return new Point[Float](sumx
/ pts
.length
.to_f
, sumy
/ pts
.length
.to_f
)
320 # Sort the vertices of a polygon in counter clockwise order
321 private class CounterClockWiseSort
324 redef fun compare
(a
,b
: COMPARED): Int do
325 if a
.x
== b
.x
and a
.y
== b
.y
then return 0
326 if a
.x
- center
.x
>= 0.0 and b
.x
- center
.x
< 0.0 then return -1
327 if a
.x
- center
.x
< 0.0 and b
.x
- center
.x
>= 0.0 then return 1
328 if a
.x
- center
.x
== 0.0 and b
.x
- center
.x
== 0 then
329 if a
.y
- center
.y
>= 0.0 or b
.y
- center
.y
>= 0.0 then
330 if a
.y
> b
.y
then return -1
333 if b
.y
> a
.y
then return -1
337 var det
= (a
.x
- center
.x
) * (b
.y
- center
.y
) - (b
.x
- center
.x
) * (a
.y
- center
.y
)
338 if det
> 0.0 then return 1
339 if det
< 0.0 then return -1
341 var d1
= (a
.x
- center
.x
) * (a
.x
- center
.x
) + (a
.y
- center
.y
) * (a
.y
- center
.y
)
342 var d2
= (b
.x
- center
.x
) * (b
.x
- center
.x
) + (b
.y
- center
.y
) * (b
.y
- center
.y
)
343 if d1
> d2
then return -1
348 # Sort the vertices of a polygon in clockwise order
349 private class ClockWiseSort
352 redef fun compare
(a
,b
: COMPARED): Int do
353 if a
.x
== b
.x
and a
.y
== b
.y
then return 0
354 if a
.x
- center
.x
>= 0.0 and b
.x
- center
.x
< 0.0 then return 1
355 if a
.x
- center
.x
< 0.0 and b
.x
- center
.x
>= 0.0 then return -1
356 if a
.x
- center
.x
== 0.0 and b
.x
- center
.x
== 0 then
357 if a
.y
- center
.y
>= 0.0 or b
.y
- center
.y
>= 0.0 then
358 if a
.y
> b
.y
then return 1
361 if b
.y
> a
.y
then return 1
365 var det
= (a
.x
- center
.x
) * (b
.y
- center
.y
) - (b
.x
- center
.x
) * (a
.y
- center
.y
)
366 if det
> 0.0 then return -1
367 if det
< 0.0 then return 1
369 var d1
= (a
.x
- center
.x
) * (a
.x
- center
.x
) + (a
.y
- center
.y
) * (a
.y
- center
.y
)
370 var d2
= (b
.x
- center
.x
) * (b
.x
- center
.x
) + (b
.y
- center
.y
) * (b
.y
- center
.y
)
371 if d1
> d2
then return 1
377 # Get the convex hull of the set of `points`
380 # var p1 = new Point[Float](0.0, 0.0)
381 # var p2 = new Point[Float](5.0, 0.0)
382 # var p3 = new Point[Float](0.0, 5.0)
383 # var p4 = new Point[Float](5.0, 5.0)
384 # var p5 = new Point[Float](2.5, 2.5)
385 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4, p5)
386 # var poly = convex_hull(arr)
387 # assert poly.points == [p4, p3, p1, p2]
389 fun convex_hull
(points
: Array[Point[Float]]): ConvexPolygon do
390 var sorter
= new PointXCompare
392 var l
= points
.length
394 var pl1
= new Array[Point[Float]]
395 var pl2
= new Array[Point[Float]]
397 while pl2
.length
>= 2 and not turn_left
(pl2
[pl2
.length
- 2], pl2
[pl2
.length
- 1], points
[i
]) do
404 while pl1
.length
>= 2 and not turn_left
(pl1
[pl1
.length
- 2], pl1
[pl1
.length
- 1], points
[i
]) do
410 pl1
.remove_at
(pl1
.length
- 1)
411 pl2
.remove_at
(pl2
.length
-1)
413 return new ConvexPolygon.with_vertices
(pl2
)
416 # Is the angle between [p1,p2] and [p2,p3] going left (counter clockwise) or right (clockwise) ?
419 # var p1 = new Point[Float](0.0, 0.0)
420 # var p2 = new Point[Float](5.0, 0.0)
421 # var p3 = new Point[Float](0.0, 5.0)
422 # assert turn_left(p1, p2, p3)
424 fun turn_left
(p1
, p2
, p3
: Point[Float]): Bool do
425 return ((p2
.x
- p1
.x
) * (p3
.y
- p2
.y
) - (p3
.x
- p2
.x
) * (p2
.y
- p1
.y
)) > 0.0