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 # Abstraction of a Polygon
23 abstract class APolygon
24 # Vertices of this polygon
25 var points
: Array[Point[Float]]
27 init do assert points
.length
>= 3
29 # Get an array of the x coordinates of the vertices
30 private fun x_coordinates
: Array[Float] do
31 return [for p
in points
do p
.x
]
34 # Get an array of the y coordinates of the vertices
35 private fun y_coordinates
: Array[Float] do
36 return [for p
in points
do p
.y
]
39 # Get a matrice containing the coordinates of the vertices
40 private fun vertices
: Array[Array[Float]] do
41 var vertices
= new Array[Array[Float]]
42 for i
in [0..points
.length
[ do
43 var temp
= new Array[Float]
51 # Returns the axes corresponding to the edges of the polygon, used for collision detection
52 private fun axes
: Array[Point[Float]] do
53 var axes
= new Array[Point[Float]]
54 for i
in [0..points
.length
[ do
55 var p1
= new Point[Float](points
[i
].x
, points
[i
].y
)
56 var p2
= new Point[Float](points
[(i
+1) % points
.length
].x
, points
[(i
+1) % points
.length
].y
)
57 var edge
= new Point[Float](p1
.x
- p2
.x
, p1
.y
- p2
.y
)
58 var normal
= new Point[Float](-edge
.y
, edge
.x
)
64 # Sort the vertices in counter clockwise order
67 # var p1 = new Point[Float](0.0, 0.0)
68 # var p2 = new Point[Float](5.0, 0.0)
69 # var p3 = new Point[Float](0.0, 5.0)
70 # var p4 = new Point[Float](5.0, 5.0)
71 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
72 # var poly = new ConvexPolygon(arr)
74 # assert poly.points == [p4, p2, p1, p3]
77 var sorter
= new CounterClockWiseSort.with_center
(vertices
)
81 # Sort the vertices in clockwise order
84 # var p1 = new Point[Float](0.0, 0.0)
85 # var p2 = new Point[Float](5.0, 0.0)
86 # var p3 = new Point[Float](0.0, 5.0)
87 # var p4 = new Point[Float](5.0, 5.0)
88 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
89 # var poly = new ConvexPolygon(arr)
91 # assert poly.points == [p3, p1, p2, p4]
94 var sorter
= new ClockWiseSort.with_center
(vertices
)
101 # var p1 = new Point[Float](0.0, 0.0)
102 # var p2 = new Point[Float](5.0, 0.0)
103 # var p3 = new Point[Float](0.0, 5.0)
104 # var p4 = new Point[Float](5.0, 5.0)
105 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
106 # var poly = new ConvexPolygon(arr)
108 # assert poly.is_convex
110 fun is_convex
: Bool do
111 var prev
= points
[points
.length
- 2]
112 var curr
= points
[points
.length
- 1]
114 var is_ccw
= turn_left
(prev
, curr
, next
)
115 for i
in [1..points
.length
[ do
119 if turn_left
(prev
,curr
, next
) != is_ccw
then return false
124 # Generate a projection of an edge of the polygon on a given axis
125 private fun project
(axis
: Point[Float]): Projection do
126 var min
= axis
.x
* points
[0].x
+ axis
.y
* points
[0].y
128 for i
in [0..points
.length
[ do
129 var p
= axis
.x
* points
[i
].x
+ axis
.y
* points
[i
].y
130 if p
< min
then min
= p
131 if p
> max
then max
= p
133 var projection
= new Projection(min
, max
)
137 # Remove `p` from the vertices, keeping at least 3 vertices
138 fun delete_vertex
(p
: Point[Float]) do
139 assert points
.length
> 3
143 # Does `self` intersects with `other`
144 fun intersects
(other
: APolygon): Bool is abstract
146 # Is `p` contained in `self` ?
147 fun contain
(p
: Point[Float]): Bool is abstract
149 # Add a vertex to `self`
150 fun add_vertex
(p
: Point[Float]): Bool do
159 # TODO: implement algorithms for concave polygons ?
162 # Convex Polygon class
166 # Does this polygon intersects `other` ?
169 # var p1 = new Point[Float](0.0, 0.0)
170 # var p2 = new Point[Float](5.0, 0.0)
171 # var p3 = new Point[Float](0.0, 5.0)
172 # var p4 = new Point[Float](5.0, 5.0)
173 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
174 # var poly = new ConvexPolygon(arr)
176 # p1 = new Point[Float](2.5, 2.5)
177 # p2 = new Point[Float](7.5, 2.5)
178 # p3 = new Point[Float](2.5, 7.5)
179 # p4 = new Point[Float](7.5, 7.5)
180 # arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
181 # var poly2 = new ConvexPolygon(arr)
183 # assert poly.intersects(poly2)
185 redef fun intersects
(other
) do
189 var axes2
= other
.axes
191 var project1
= project
(axis
)
192 var project2
= other
.project
(axis
)
193 if not project1
.overlap
(project2
) then return false
196 var project1
= project
(axis
)
197 var project2
= other
.project
(axis
)
198 if not project1
.overlap
(project2
) then return false
204 # var p1 = new Point[Float](0.0, 0.0)
205 # var p2 = new Point[Float](5.0, 0.0)
206 # var p3 = new Point[Float](0.0, 5.0)
207 # var p4 = new Point[Float](5.0, 5.0)
208 # var p5 = new Point[Float](2.5, 2.5)
209 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
210 # var poly = new ConvexPolygon(arr)
212 # assert poly.contain(p5)
214 redef fun contain
(p
) do
215 var prev
= points
[points
.length
- 1]
218 var is_ccw
= turn_left
(prev
, curr
, next
)
219 for i
in [1..points
.length
[ do
222 if turn_left
(prev
, curr
, next
) != is_ccw
then return false
227 # Check if the order of the points in the polygon is counter-clockwise
228 # The vertices in the polygon need to be sorted
231 # var p1 = new Point[Float](0.0, 0.0)
232 # var p2 = new Point[Float](5.0, 0.0)
233 # var p3 = new Point[Float](0.0, 5.0)
234 # var p4 = new Point[Float](5.0, 5.0)
235 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
236 # var poly = new ConvexPolygon(arr)
241 var min
= points
[0].y
243 for i
in [1..points
.length
- 1[ do
244 if points
[i
].y
< min
then
249 var prev
= points
[(min_index
- 1 + points
.length
) % points
.length
]
250 var next
= points
[(min_index
+ 1) % points
.length
]
251 return not turn_left
(prev
, points
[min_index
], next
)
256 # Add a vertex to the polygon
259 # var p1 = new Point[Float](0.0, 0.0)
260 # var p2 = new Point[Float](5.0, 0.0)
261 # var p3 = new Point[Float](0.0, 5.0)
262 # var p4 = new Point[Float](5.0, 5.0)
263 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4)
264 # var poly = new ConvexPolygon(arr)
265 # var p5 = new Point[Float](2.5, 7.5)
266 # assert poly.add_vertex(p5)
268 redef fun add_vertex
(p
) do
269 assert points
.length
>= 3
270 var temp_list
= points
.clone
272 var temp_polygon
= new ConvexPolygon(temp_list
)
273 temp_polygon
.sort_ccw
274 if temp_polygon
.is_convex
then
275 points
= temp_polygon
.points
283 # Projection of an edge of a `ConvexPolygon` used for intersection test
284 private class Projection
285 var min
: Float is writable
286 var max
: Float is writable
288 fun overlap
(other
: Projection): Bool do return not (min
> other
.max
or other
.min
> max
)
291 private class PointXCompare
294 redef type COMPARED: Point[Float]
296 redef fun compare
(a
,b
) do
298 if a
.y
== b
.y
then return 0
299 if a
.y
> b
.y
then return - 1
302 if a
.x
> b
.x
then return -1
308 # Sorter for polygon vertices
309 private abstract class PolygonSorter
312 redef type COMPARED: Point[Float]
314 # Center of the polygon's points
317 # init calculating the center
318 init with_center
(pts
: Array[Array[Float]]) do
319 init(calc_center
(pts
))
322 # Calculate the center
323 fun calc_center
(pts
: Array[Array[Float]]): COMPARED do
330 return new Point[Float](sumx
/ pts
.length
.to_f
, sumy
/ pts
.length
.to_f
)
334 #TODO: CounterClockWise and ClockWise sorts are broken in some cases of concave polygons
336 # Sort the vertices of a polygon in counter clockwise order
337 private class CounterClockWiseSort
340 redef fun compare
(a
,b
) do
341 if a
.x
== b
.x
and a
.y
== b
.y
then return 0
342 if a
.x
- center
.x
>= 0.0 and b
.x
- center
.x
< 0.0 then return -1
343 if a
.x
- center
.x
< 0.0 and b
.x
- center
.x
>= 0.0 then return 1
344 if a
.x
- center
.x
== 0.0 and b
.x
- center
.x
== 0.0 then
345 if a
.y
- center
.y
>= 0.0 or b
.y
- center
.y
>= 0.0 then
346 if a
.y
> b
.y
then return -1
349 if b
.y
> a
.y
then return -1
353 var det
= (a
.x
- center
.x
) * (b
.y
- center
.y
) - (b
.x
- center
.x
) * (a
.y
- center
.y
)
354 if det
> 0.0 then return 1
355 if det
< 0.0 then return -1
357 var d1
= (a
.x
- center
.x
) * (a
.x
- center
.x
) + (a
.y
- center
.y
) * (a
.y
- center
.y
)
358 var d2
= (b
.x
- center
.x
) * (b
.x
- center
.x
) + (b
.y
- center
.y
) * (b
.y
- center
.y
)
359 if d1
> d2
then return -1
364 # Sort the vertices of a polygon in clockwise order
365 private class ClockWiseSort
368 redef fun compare
(a
,b
) do
369 if a
.x
== b
.x
and a
.y
== b
.y
then return 0
370 if a
.x
- center
.x
>= 0.0 and b
.x
- center
.x
< 0.0 then return 1
371 if a
.x
- center
.x
< 0.0 and b
.x
- center
.x
>= 0.0 then return -1
372 if a
.x
- center
.x
== 0.0 and b
.x
- center
.x
== 0 then
373 if a
.y
- center
.y
>= 0.0 or b
.y
- center
.y
>= 0.0 then
374 if a
.y
> b
.y
then return 1
377 if b
.y
> a
.y
then return 1
381 var det
= (a
.x
- center
.x
) * (b
.y
- center
.y
) - (b
.x
- center
.x
) * (a
.y
- center
.y
)
382 if det
> 0.0 then return -1
383 if det
< 0.0 then return 1
385 var d1
= (a
.x
- center
.x
) * (a
.x
- center
.x
) + (a
.y
- center
.y
) * (a
.y
- center
.y
)
386 var d2
= (b
.x
- center
.x
) * (b
.x
- center
.x
) + (b
.y
- center
.y
) * (b
.y
- center
.y
)
387 if d1
> d2
then return 1
392 # Get the convex hull of the set of `points`
395 # var p1 = new Point[Float](0.0, 0.0)
396 # var p2 = new Point[Float](5.0, 0.0)
397 # var p3 = new Point[Float](0.0, 5.0)
398 # var p4 = new Point[Float](5.0, 5.0)
399 # var p5 = new Point[Float](2.5, 2.5)
400 # var arr = new Array[Point[Float]].with_items(p1, p2, p3, p4, p5)
401 # var poly = convex_hull(arr)
402 # assert poly.points == [p4, p3, p1, p2]
404 fun convex_hull
(points
: Array[Point[Float]]): ConvexPolygon do
405 var sorter
= new PointXCompare
407 var l
= points
.length
409 var pl1
= new Array[Point[Float]]
410 var pl2
= new Array[Point[Float]]
412 while pl2
.length
>= 2 and not turn_left
(pl2
[pl2
.length
- 2], pl2
[pl2
.length
- 1], points
[i
]) do
419 while pl1
.length
>= 2 and not turn_left
(pl1
[pl1
.length
- 2], pl1
[pl1
.length
- 1], points
[i
]) do
425 pl1
.remove_at
(pl1
.length
- 1)
426 pl2
.remove_at
(pl2
.length
-1)
428 return new ConvexPolygon(pl2
)
431 # Is the angle between [p1,p2] and [p2,p3] going left (counter clockwise) or right (clockwise) ?
434 # var p1 = new Point[Float](0.0, 0.0)
435 # var p2 = new Point[Float](5.0, 0.0)
436 # var p3 = new Point[Float](0.0, 5.0)
437 # assert turn_left(p1, p2, p3)
439 fun turn_left
(p1
, p2
, p3
: Point[Float]): Bool do
440 return ((p2
.x
- p1
.x
) * (p3
.y
- p2
.y
) - (p3
.x
- p2
.x
) * (p2
.y
- p1
.y
)) > 0.0
443 # Split a polygon into triangles
444 # Useful for converting a concave polygon into multiple convex ones
445 fun triangulate
(pts
: Array[Point[Float]], results
: Array[ConvexPolygon]) do
446 var poly
= new Polygon(pts
)
448 recursive_triangulate
(pts
, results
)
451 private fun recursive_triangulate
(pts
: Array[Point[Float]], results
: Array[ConvexPolygon]) do
452 if pts
.length
== 3 then
453 results
.add
(new ConvexPolygon(pts
))
456 var prev
= pts
[pts
.length
- 1]
459 for i
in [1..pts
.length
[ do
460 if turn_left
(prev
, curr
, next
) then
463 if i
+1 == pts
.length
then next
= pts
[pts
.length
- 1] else next
= pts
[i
+1]
467 var triangle
= new ConvexPolygon(new Array[Point[Float]].with_items
(prev
, curr
, next
))
469 if p
!= prev
and p
!= curr
and p
!= next
then
470 if triangle
.contain
(p
) then
477 results
.add
(triangle
)
479 recursive_triangulate
(pts
, results
)
484 if i
+1 == pts
.length
then next
= pts
[pts
.length
- 1] else next
= pts
[i
+1]