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                 init(left, right, top, bottom)
 124         end
 125
 126         # Create a `Box` using left, right, bottom and top
 127         init lrbt(left, right, bottom, top: N)
 128         do
 129                 init(left, right, top, bottom)
 130         end
 131
 132         # Create a `Box` using left, right, top and bottom
 133         init lrtb(left, right, top, bottom: N)
 134         do
 135                 init(left, right, top, bottom)
 136         end
 137
 138         # Create a `Box` using left, bottom, width and height
 139         init lbwh(left, bottom, width, height: N)
 140         do
 141                 init(left, left + width, bottom + height, bottom)
 142         end
 143
 144         # Create a `Box` using left, top, width and height
 145         init ltwh(left, top, width, height: N)
 146         do
 147                 init(left, left+width, top, top - height)
 148         end
 149
 150         redef fun to_s do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}>"
 151 end
 152
 153 # An 3d abstract bounded object
 154 interface Boxed3d[N: Numeric]
 155         super Boxed[N]
 156
 157         # Front bound
 158         #
 159         # require: front >= back
 160         fun front: N is abstract
 161
 162         # Back bound
 163         #
 164         # require: back <= bottom
 165         fun back: N is abstract
 166
 167         #     var a = new Box3d[Int].lbfwhd(1, 1, -1, 4, 4, 4)
 168         #     var b = new Box3d[Int].lbfwhd(2, 2, -2, 2, 2, 2)
 169         #     var c = new Box3d[Int].lbfwhd(2, 2,  0, 2, 2, 8)
 170         #     assert a.contains(b)
 171         #     assert not b.contains(a)
 172         #     assert c.contains(b)
 173         #     assert not b.contains(c)
 174         #     assert not a.contains(c)
 175         #     assert not c.contains(a)
 176         redef fun contains(other)
 177         do
 178                 return super and (not other isa Boxed3d[N] or
 179                         (self.front >= other.front and self.back <= other.back))
 180         end
 181
 182         #     var a = new Box3d[Int].lbfwhd(0, 0, 0, 2, 2, 2)
 183         #     var b = new Box3d[Int].lbfwhd(1, 1, 1, 8, 2, 2)
 184         #     var c = new Box3d[Int].lbfwhd(3, 0, 0, 2, 2, 8)
 185         #     assert a.intersects(b)
 186         #     assert b.intersects(a)
 187         #     assert b.intersects(c)
 188         #     assert c.intersects(b)
 189         #     assert not c.intersects(a)
 190         #     assert not a.intersects(c)
 191         redef fun intersects(other)
 192         do
 193                 return super and (not other isa Boxed3d[N] or
 194                         (self.back <= other.front and other.back <= self.front))
 195         end
 196
 197         redef fun padded(dist): Box3d[N] do return new Box3d[N].lrtbfb(left - dist, right + dist, top + dist, bottom - dist, front + dist, back - dist)
 198 end
 199
 200 # A 3d bounded object and an implementation of Boxed
 201 #
 202 # This class offers many constructors specialized for different usage. They are
 203 # named according to the order of their arguments.
 204 class Box3d[N: Numeric]
 205         super Boxed3d[N]
 206         super Box[N]
 207
 208         redef var front: N
 209         redef var back: N
 210
 211         # Create a `Box` covering all of the `boxed`
 212         #
 213         #     var box = new Box[Int].around(new Point[Int](-4,-4), new Point[Int](4,4))
 214         #     assert box.left == -4 and box.bottom == -4
 215         #     assert box.right == 4 and box.top == 4
 216         init around(boxed: Boxed3d[N]...)
 217         do
 218                 super
 219
 220                 assert not boxed.is_empty
 221
 222                 var left: nullable N = null
 223                 var right: nullable N = null
 224                 var top: nullable N = null
 225                 var bottom: nullable N = null
 226                 var front: nullable N = null
 227                 var back: nullable N= null
 228
 229                 for box in boxed do
 230                         if left == null or box.left < left then left = box.left
 231                         if right == null or box.right > right then right = box.right
 232                         if top == null or box.top > top then top = box.top
 233                         if bottom == null or box.bottom < bottom then bottom = box.bottom
 234                         if front == null or box.front > front then front = box.front
 235                         if back == null or box.back < back then back = box.back
 236                 end
 237
 238                 assert left != null and right != null and top != null and bottom != null
 239
 240                 self.left = left
 241                 self.right = right
 242                 self.top = top
 243                 self.bottom = bottom
 244         end
 245
 246         # Create a `Box3d` using left, right, bottom, top, front and back
 247         init lrbtfb(left, right, bottom, top, front, back: N)
 248         do
 249                 lrbt(left, right, bottom, top)
 250
 251                 self.front = front
 252                 self.back = back
 253         end
 254
 255         # Create a `Box3d` using left, right, top, bottom, front and back
 256         init lrtbfb(left, right, top, bottom, front, back: N)
 257         do
 258                 lrtb(left, right, top, bottom)
 259
 260                 self.front = front
 261                 self.back = back
 262         end
 263
 264         # Create a `Box3d` using left, top, front, width, height and depth
 265         init lbfwhd(left, bottom, front, width, height, depth: N)
 266         do
 267                 lbwh(left, bottom, width, height)
 268
 269                 self.front = front
 270                 self.back = front - depth
 271         end
 272
 273         # Create a `Box3d` using left, top, front, width, height and depth
 274         init ltfwhd(left, top, front, width, height, depth: N)
 275         do
 276                 ltwh(left, top, width, height)
 277
 278                 self.front = front
 279                 self.back = front - depth
 280         end
 281
 282         redef fun to_s do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}, front: {front}, back: {back}"
 283 end
 284
 285 redef class IPoint[N]
 286         super Boxed[N]
 287
 288         redef fun left do return x
 289         redef fun right do return x
 290         redef fun top do return y
 291         redef fun bottom do return y
 292 end
 293
 294 redef class IPoint3d[N]
 295         super Boxed3d[N]
 296
 297         redef fun front do return z
 298         redef fun back do return z
 299 end
 300
 301 redef class ILine[N]
 302         super Boxed[N]
 303
 304         redef fun left do return point_left.x
 305         redef fun right do return point_right.x
 306         redef fun top do return point_left.y.max(point_right.y)
 307         redef fun bottom do return point_left.y.min(point_right.y)
 308 end
 309
 310 redef class ILine3d[N]
 311         super Boxed3d[N]
 312
 313         redef fun front do return point_left.z.min(point_right.z)
 314         redef fun back do return point_left.z.max(point_right.z)
 315 end
 316
 317 # Base for all data structures containing multiple Boxed Objects
 318 interface BoxedCollection[E: Boxed[Numeric]]
 319         super SimpleCollection[E]
 320
 321         # returns all the items overlapping with `region`
 322         fun items_overlapping(region :Boxed[Numeric]): SimpleCollection[E] is abstract
 323 end
 324
 325 # A BoxedCollection implemented with an array, linear performances for searching but really
 326 # fast for creation and filling
 327 class BoxedArray[E: Boxed[Numeric]]
 328         super BoxedCollection[E]
 329
 330         private var data: Array[E] = new Array[E]
 331
 332         redef fun add(item) do data.add(item)
 333         redef fun items_overlapping(item): SimpleCollection[E]
 334         do
 335                 var arr = new Array[E]
 336                 for i in data do
 337                         if i.intersects(item) then arr.add(i)
 338                 end
 339                 return arr
 340         end
 341
 342         redef fun iterator do return data.iterator
 343 end