lib/geometry/polygon.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   3 # Copyright 2015 Romain Chanoir <romain.chanoir@viacesi.fr>
   4 #
   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
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  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.
  16
  17 # Convex Polygons manipulations
  18 module polygon
  19
  20 import points_and_lines
  21
  22 # Convex Polygon class
  23 class ConvexPolygon
  24
  25         # Vertices of this polygon
  26         var points = new Array[Point[Float]]
  27
  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
  32                 points.add_all(pts)
  33         end
  34
  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]
  38         end
  39
  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]
  43         end
  44
  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]
  50                         temp.add(points[i].x)
  51                         temp.add(points[i].y)
  52                         vertices.add(temp)
  53                 end
  54                 return vertices
  55         end
  56
  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)
  65                         axes[i] = normal
  66                 end
  67                 return axes
  68         end
  69
  70         # Sort the vertices in counter clockwise order
  71         #
  72         # ~~~
  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)
  79         # poly.sort_ccw
  80         # assert poly.points == [p4, p2, p1, p3]
  81         # ~~~
  82         fun sort_ccw do
  83                 var sorter = new CounterClockWiseSort.with_center(vertices)
  84                 sorter.sort(points)
  85         end
  86
  87         # Sort the vertices in clockwise order
  88         #
  89         # ~~~
  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)
  96         # poly.sort_cw
  97         # assert poly.points == [p3, p1, p2, p4]
  98         # ~~~
  99         fun sort_cw do
 100                 var sorter = new ClockWiseSort.with_center(vertices)
 101                 sorter.sort(points)
 102         end
 103
 104         # Does this polygon intersects `other` ?
 105         #
 106         # ~~~
 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)
 113         # poly.sort_ccw
 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)
 120         # poly2.sort_ccw
 121         # assert poly.intersects(poly2)
 122         # ~~~
 123         fun intersects(other: ConvexPolygon): Bool do
 124                 assert is_convex
 125
 126                 var axes1 = axes
 127                 var axes2 = other.axes
 128                 for axis in axes1 do
 129                         var project1 = project(axis)
 130                         var project2 = other.project(axis)
 131                         if not project1.overlap(project2) then return false
 132                 end
 133                 for axis in axes2 do
 134                         var project1 = project(axis)
 135                         var project2 = other.project(axis)
 136                         if not project1.overlap(project2) then return false
 137                 end
 138                 return true
 139         end
 140
 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
 144                 var max = min
 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
 149                 end
 150                 var projection = new Projection(min, max)
 151                 return projection
 152         end
 153
 154         # Is this polygon convex ?
 155         #
 156         # ~~~
 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)
 163         # poly.sort_ccw
 164         # assert poly.is_convex
 165         # ~~~
 166         fun is_convex: Bool do
 167                 var prev = points[points.length - 2]
 168                 var curr = points[points.length - 1]
 169                 var next = points[0]
 170                 var is_ccw = turn_left(prev, curr, next)
 171                 for i in [1..points.length[ do
 172                         prev = curr
 173                         curr= next
 174                         next = points[i]
 175                         if turn_left(prev ,curr, next) != is_ccw then return false
 176                 end
 177                 return true
 178         end
 179
 180         # Check if `p` is in the polygon
 181         #
 182         # ~~~
 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)
 190         # poly.sort_ccw
 191         # assert poly.contain(p5)
 192         # ~~~
 193         fun contain(p : Point[Float]): Bool do
 194                 var prev = points[points.length - 1]
 195                 var curr = p
 196                 var next = points[0]
 197                 var is_ccw = turn_left(prev, curr, next)
 198                 for i in [1..points.length[ do
 199                         prev = next
 200                         next = points[i]
 201                         if turn_left(prev, curr, next) != is_ccw then return false
 202                 end
 203                 return true
 204         end
 205
 206         # Check if the order of the points in the polygon is counter-clockwise
 207         # The vertices in the polygon need to be sorted
 208         #
 209         # ~~~
 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)
 216         # poly.sort_ccw
 217         # assert poly.is_ccw
 218         # ~~~
 219         fun is_ccw: Bool do
 220                 var min = points[0].y
 221                 var min_index = 0
 222                 for i in [1..points.length - 1[ do
 223                         if points[i].y < min then
 224                                 min = points[i].y
 225                                 min_index = i
 226                         end
 227                 end
 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)
 231         end
 232
 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
 236                         points.remove(p)
 237                 end
 238         end
 239
 240         # Add a vertex to the polygon
 241         #
 242         # ~~~
 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)
 251         # ~~~
 252         fun add_vertex(p: Point[Float]): Bool do
 253                 assert points.length >= 3
 254                 var temp_list = points.clone
 255                 temp_list.add(p)
 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
 260                         return true
 261                 else
 262                         return false
 263                 end
 264         end
 265 end
 266
 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
 271
 272         fun overlap(other: Projection): Bool do
 273                 return not (min > other.max or other.min > max)
 274         end
 275 end
 276
 277 private class PointXCompare
 278         super Comparator
 279
 280         redef type COMPARED: Point[Float]
 281
 282         redef fun compare(a,b : COMPARED): Int do
 283                 if a.x == b.x then
 284                         if a.y == b.y then return 0
 285                         if a.y > b.y then return - 1
 286                         return 1
 287                 else
 288                         if a.x > b.x then return -1
 289                         return 1
 290                 end
 291         end
 292 end
 293
 294 # Sorter for polygon vertices
 295 private abstract class PolygonSorter
 296         super Comparator
 297
 298         redef type COMPARED: Point[Float]
 299
 300         # Center of the polygon's points
 301         var center: COMPARED
 302
 303         # init calculating the center
 304         init with_center(pts : Array[Array[Float]]) do
 305                 init(calc_center(pts))
 306         end
 307
 308         # Calculate the center
 309         fun calc_center(pts : Array[Array[Float]]): COMPARED do
 310                 var sumx = 0.0
 311                 var sumy = 0.0
 312                 for ap in pts do
 313                         sumx += ap[0]
 314                         sumy += ap[1]
 315                 end
 316                 return new Point[Float](sumx / pts.length.to_f, sumy / pts.length.to_f)
 317         end
 318 end
 319
 320 # Sort the vertices of a polygon in counter clockwise order
 321 private class CounterClockWiseSort
 322         super PolygonSorter
 323
 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
 331                                 return 1
 332                         end
 333                         if b.y > a.y then return -1
 334                         return 1
 335                 end
 336
 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
 340
 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
 344                 return 1
 345         end
 346 end
 347
 348 # Sort the vertices of a polygon in clockwise order
 349 private class ClockWiseSort
 350         super PolygonSorter
 351
 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
 359                                 return -1
 360                         end
 361                         if b.y > a.y then return 1
 362                         return -1
 363                 end
 364
 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
 368
 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
 372                 return -1
 373         end
 374 end
 375
 376
 377 # Get the convex hull of the set of `points`
 378 #
 379 # ~~~
 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]
 388 # ~~~
 389 fun convex_hull(points: Array[Point[Float]]): ConvexPolygon do
 390         var sorter = new PointXCompare
 391         sorter.sort(points)
 392         var l = points.length
 393
 394         var pl1 = new Array[Point[Float]]
 395         var pl2 = new Array[Point[Float]]
 396         for i in [0..l[ do
 397                 while pl2.length >= 2 and not turn_left(pl2[pl2.length - 2], pl2[pl2.length - 1], points[i]) do
 398                         pl2.remove(pl2.last)
 399                 end
 400                 pl2.add(points[i])
 401         end
 402         var i = l - 1
 403         while i >= 0 do
 404                 while pl1.length >= 2 and not turn_left(pl1[pl1.length - 2], pl1[pl1.length - 1], points[i]) do
 405                         pl1.remove(pl1.last)
 406                 end
 407                 pl1.add(points[i])
 408                 i-= 1
 409         end
 410         pl1.remove_at(pl1.length - 1)
 411         pl2.remove_at(pl2.length -1)
 412         pl2.add_all(pl1)
 413         return new ConvexPolygon.with_vertices(pl2)
 414 end
 415
 416 # Is the angle between [p1,p2] and [p2,p3] going left (counter clockwise) or right (clockwise) ?
 417 #
 418 # ~~~
 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)
 423 # ~~~
 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
 426 end