lib/geometry/boxes.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   3 # Copyright 2014 Alexis Laferrière <alexis.laf@xymus.net>
   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 # Provides interfaces and classes to represent basic geometry needs.
  18 module boxes
  19
  20 import points_and_lines
  21
  22 # An 2d abstract bounded object
  23 interface Boxed[N: Numeric]
  24         # Left bound
  25         #
  26         # require: left <= right
  27         fun left: N is abstract
  28
  29         # Right bound
  30         #
  31         # require: right >= left
  32         fun right: N is abstract
  33
  34         # Top bound
  35         #
  36         # require: top >= bottom
  37         fun top: N is abstract
  38
  39         # Bottom bound
  40         #
  41         # require: bottom <= top
  42         fun bottom: N is abstract
  43
  44         # Is `other` contained within `self`?
  45         #
  46         #     var a = new Box[Int].lbwh(1, 1, 4, 4)
  47         #     var b = new Box[Int].lbwh(2, 2, 2, 2)
  48         #     var c = new Box[Int].lbwh(0, 2, 8, 2)
  49         #     assert a.contains(b)
  50         #     assert not b.contains(a)
  51         #     assert c.contains(b)
  52         #     assert not b.contains(c)
  53         #     assert not a.contains(c)
  54         #     assert not c.contains(a)
  55         fun contains(other: Boxed[N]): Bool
  56         do
  57                 return self.top >= other.top and self.bottom <= other.bottom and
  58                         self.left <= other.left and self.right >= other.right
  59         end
  60
  61         # Does `self` intersect with `other`?
  62         #
  63         #     var a = new Box[Int].lbwh(0, 0, 2, 2)
  64         #     var b = new Box[Int].lbwh(1, 1, 8, 2)
  65         #     var c = new Box[Int].lbwh(3, 0, 2, 8)
  66         #     assert a.intersects(b)
  67         #     assert b.intersects(a)
  68         #     assert b.intersects(c)
  69         #     assert c.intersects(b)
  70         #     assert not c.intersects(a)
  71         #     assert not a.intersects(c)
  72         fun intersects(other: Boxed[N]): Bool
  73         do
  74                 return self.left <= other.right and other.left <= self.right and
  75                         self.top >= other.bottom and other.top >= self.bottom
  76         end
  77
  78         # Create a bounding box that encloses the actual bounding box.
  79         # `dist` is the distance between the inner boundaries and the outer boundaries.
  80         # ~~~
  81         # var p = new Point[Int](5,10)
  82         # var b = p.padded(3)
  83         # assert b.left == 2 and b.right == 8 and b.top == 13 and b.bottom == 7
  84         # ~~~
  85         fun padded(dist: N): Box[N] do return new Box[N].lrtb(left - dist, right + dist, top + dist, bottom - dist)
  86 end
  87
  88 # A 2d bounded object and an implementation of `Boxed`
  89 #
  90 # This class offers many constructors specialized for different usage. They are
  91 # named according to the order of their arguments.
  92 class Box[N: Numeric]
  93         super Boxed[N]
  94
  95         redef var left: N
  96         redef var right: N
  97         redef var top: N
  98         redef var bottom: N
  99
 100         # Create a `Box` covering all of the `boxed`
 101         #
 102         #     var box = new Box[Int].around(new Point[Int](-4,-4), new Point[Int](4,4))
 103         #     assert box.left == -4 and box.bottom == -4
 104         #     assert box.right == 4 and box.top == 4
 105         init around(boxed: Boxed[N]...)
 106         do
 107                 assert not boxed.is_empty
 108
 109                 var left: nullable N = null
 110                 var right: nullable N = null
 111                 var top: nullable N = null
 112                 var bottom: nullable N = null
 113
 114                 for box in boxed do
 115                         if left == null or box.left < left then left = box.left
 116                         if right == null or box.right > right then right = box.right
 117                         if top == null or box.top > top then top = box.top
 118                         if bottom == null or box.bottom < bottom then bottom = box.bottom
 119                 end
 120
 121                 assert left != null and right != null and top != null and bottom != null
 122
 123                 self.left = left
 124                 self.right = right
 125                 self.top = top
 126                 self.bottom = bottom
 127         end
 128
 129         # Create a `Box` using left, right, bottom and top
 130         init lrbt(left, right, bottom, top: N)
 131         do
 132                 self.left = left
 133                 self.right = right
 134                 self.top = top
 135                 self.bottom = bottom
 136         end
 137
 138         # Create a `Box` using left, right, top and bottom
 139         init lrtb(left, right, top, bottom: N)
 140         do
 141                 self.left = left
 142                 self.right = right
 143                 self.top = top
 144                 self.bottom = bottom
 145         end
 146
 147         # Create a `Box` using left, bottom, width and height
 148         init lbwh(left, bottom, width, height: N)
 149         do
 150                 self.left = left
 151                 self.bottom = bottom
 152
 153                 self.right = left + width
 154                 self.top = bottom + height
 155         end
 156
 157         # Create a `Box` using left, top, width and height
 158         init ltwh(left, top, width, height: N)
 159         do
 160                 self.left = left
 161                 self.top = top
 162
 163                 self.right = left + width
 164                 self.bottom = top - height
 165         end
 166
 167         redef fun to_s do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}>"
 168 end
 169
 170 # An 3d abstract bounded object
 171 interface Boxed3d[N: Numeric]
 172         super Boxed[N]
 173
 174         # Front bound
 175         #
 176         # require: front >= back
 177         fun front: N is abstract
 178
 179         # Back bound
 180         #
 181         # require: back <= bottom
 182         fun back: N is abstract
 183
 184         #     var a = new Box3d[Int].lbfwhd(1, 1, -1, 4, 4, 4)
 185         #     var b = new Box3d[Int].lbfwhd(2, 2, -2, 2, 2, 2)
 186         #     var c = new Box3d[Int].lbfwhd(2, 2,  0, 2, 2, 8)
 187         #     assert a.contains(b)
 188         #     assert not b.contains(a)
 189         #     assert c.contains(b)
 190         #     assert not b.contains(c)
 191         #     assert not a.contains(c)
 192         #     assert not c.contains(a)
 193         redef fun contains(other)
 194         do
 195                 return super and (not other isa Boxed3d[N] or
 196                         (self.front >= other.front and self.back <= other.back))
 197         end
 198
 199         #     var a = new Box3d[Int].lbfwhd(0, 0, 0, 2, 2, 2)
 200         #     var b = new Box3d[Int].lbfwhd(1, 1, 1, 8, 2, 2)
 201         #     var c = new Box3d[Int].lbfwhd(3, 0, 0, 2, 2, 8)
 202         #     assert a.intersects(b)
 203         #     assert b.intersects(a)
 204         #     assert b.intersects(c)
 205         #     assert c.intersects(b)
 206         #     assert not c.intersects(a)
 207         #     assert not a.intersects(c)
 208         redef fun intersects(other)
 209         do
 210                 return super and (not other isa Boxed3d[N] or
 211                         (self.back <= other.front and other.back <= self.front))
 212         end
 213
 214         redef fun padded(dist: N): Box3d[N] do return new Box3d[N].lrtbfb(left - dist, right + dist, top + dist, bottom - dist, front + dist, back - dist)
 215 end
 216
 217 # A 3d bounded object and an implementation of Boxed
 218 #
 219 # This class offers many constructors specialized for different usage. They are
 220 # named according to the order of their arguments.
 221 class Box3d[N: Numeric]
 222         super Boxed3d[N]
 223         super Box[N]
 224
 225         redef var front: N
 226         redef var back: N
 227
 228         # Create a `Box` covering all of the `boxed`
 229         #
 230         #     var box = new Box[Int].around(new Point[Int](-4,-4), new Point[Int](4,4))
 231         #     assert box.left == -4 and box.bottom == -4
 232         #     assert box.right == 4 and box.top == 4
 233         init around(boxed: Boxed3d[N]...)
 234         do
 235                 assert not boxed.is_empty
 236
 237                 var left: nullable N = null
 238                 var right: nullable N = null
 239                 var top: nullable N = null
 240                 var bottom: nullable N = null
 241                 var front: nullable N = null
 242                 var back: nullable N= null
 243
 244                 for box in boxed do
 245                         if left == null or box.left < left then left = box.left
 246                         if right == null or box.right > right then right = box.right
 247                         if top == null or box.top > top then top = box.top
 248                         if bottom == null or box.bottom < bottom then bottom = box.bottom
 249                         if front == null or box.front > front then front = box.front
 250                         if back == null or box.back < back then back = box.back
 251                 end
 252
 253                 assert left != null and right != null and top != null and bottom != null
 254
 255                 self.left = left
 256                 self.right = right
 257                 self.top = top
 258                 self.bottom = bottom
 259         end
 260
 261         # Create a `Box3d` using left, right, bottom, top, front and back
 262         init lrbtfb(left, right, bottom, top, front, back: N)
 263         do
 264                 lrbt(left, right, bottom, top)
 265
 266                 self.front = front
 267                 self.back = back
 268         end
 269
 270         # Create a `Box3d` using left, right, top, bottom, front and back
 271         init lrtbfb(left, right, top, bottom, front, back: N)
 272         do
 273                 lrtb(left, right, top, bottom)
 274
 275                 self.front = front
 276                 self.back = back
 277         end
 278
 279         # Create a `Box3d` using left, top, front, width, height and depth
 280         init lbfwhd(left, bottom, front, width, height, depth: N)
 281         do
 282                 lbwh(left, bottom, width, height)
 283
 284                 self.front = front
 285                 self.back = front - depth
 286         end
 287
 288         # Create a `Box3d` using left, top, front, width, height and depth
 289         init ltfwhd(left, top, front, width, height, depth: N)
 290         do
 291                 ltwh(left, top, width, height)
 292
 293                 self.front = front
 294                 self.back = front - depth
 295         end
 296
 297         redef fun to_s do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}, front: {front}, back: {back}"
 298 end
 299
 300 redef class IPoint[N]
 301         super Boxed[N]
 302
 303         redef fun left do return x
 304         redef fun right do return x
 305         redef fun top do return y
 306         redef fun bottom do return y
 307 end
 308
 309 redef class IPoint3d[N]
 310         super Boxed3d[N]
 311
 312         redef fun front do return z
 313         redef fun back do return z
 314 end
 315
 316 redef class ILine[N]
 317         super Boxed[N]
 318
 319         redef fun left do return point_left.x
 320         redef fun right do return point_right.x
 321         redef fun top do return point_left.y.min(point_right.y)
 322         redef fun bottom do return point_left.y.max(point_right.y)
 323 end
 324
 325 redef class ILine3d[N]
 326         super Boxed3d[N]
 327
 328         redef fun front do return point_left.z.min(point_right.z)
 329         redef fun back do return point_left.z.max(point_right.z)
 330 end
 331
 332 # Base for all data structures containing multiple Boxed Objects
 333 interface BoxedCollection[E: Boxed[Numeric]]
 334         super SimpleCollection[E]
 335
 336         # returns all the items overlapping with `region`
 337         fun items_overlapping(region :Boxed[Numeric]): SimpleCollection[E] is abstract
 338 end
 339
 340 # A BoxedCollection implemented with an array, linear performances for searching but really
 341 # fast for creation and filling
 342 class BoxedArray[E: Boxed[Numeric]]
 343         super BoxedCollection[E]
 344
 345         private var data: Array[E] = new Array[E]
 346
 347         redef fun add(item: E) do data.add(item)
 348         redef fun items_overlapping(item: Boxed[Numeric]): SimpleCollection[E]
 349         do
 350                 var arr = new Array[E]
 351                 for i in data do
 352                         if i.intersects(item) then arr.add(i)
 353                 end
 354                 return arr
 355         end
 356
 357         redef fun iterator do return data.iterator
 358 end