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
  87         redef fun to_s do return "<{class_name} left: {left}, right: {right}, top: {top}, bottom: {bottom}>"
  88 end
  89
  90 # A 2d bounded object and an implementation of `Boxed`
  91 #
  92 # This class offers many constructors specialized for different usage. They are
  93 # named according to the order of their arguments.
  94 class Box[N: Numeric]
  95         super Boxed[N]
  96
  97         redef var left: N
  98         redef var right: N
  99         redef var top: N
 100         redef var bottom: N
 101
 102         # Create a `Box` covering all of the `boxed`
 103         #
 104         #     var box = new Box[Int].around(new Point[Int](-4,-4), new Point[Int](4,4))
 105         #     assert box.left == -4 and box.bottom == -4
 106         #     assert box.right == 4 and box.top == 4
 107         init around(boxed: Boxed[N]...)
 108         do
 109                 assert not boxed.is_empty
 110
 111                 var left: nullable N = null
 112                 var right: nullable N = null
 113                 var top: nullable N = null
 114                 var bottom: nullable N = null
 115
 116                 for box in boxed do
 117                         if left == null or box.left < left then left = box.left
 118                         if right == null or box.right > right then right = box.right
 119                         if top == null or box.top > top then top = box.top
 120                         if bottom == null or box.bottom < bottom then bottom = box.bottom
 121                 end
 122
 123                 assert left != null and right != null and top != null and bottom != null
 124
 125                 init(left, right, top, bottom)
 126         end
 127
 128         # Create a `Box` using left, right, bottom and top
 129         init lrbt(left, right, bottom, top: N)
 130         do
 131                 init(left, right, top, bottom)
 132         end
 133
 134         # Create a `Box` using left, right, top and bottom
 135         init lrtb(left, right, top, bottom: N)
 136         do
 137                 init(left, right, top, bottom)
 138         end
 139
 140         # Create a `Box` using left, bottom, width and height
 141         init lbwh(left, bottom, width, height: N)
 142         do
 143                 init(left, left + width, bottom + height, bottom)
 144         end
 145
 146         # Create a `Box` using left, top, width and height
 147         init ltwh(left, top, width, height: N)
 148         do
 149                 init(left, left+width, top, top - height)
 150         end
 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
 199         redef fun to_s do return "<{class_name} left: {left}, right: {right}, top: {top}, bottom: {bottom}, front: {front}, back: {back}>"
 200 end
 201
 202 # A 3d bounded object and an implementation of Boxed
 203 #
 204 # This class offers many constructors specialized for different usage. They are
 205 # named according to the order of their arguments.
 206 class Box3d[N: Numeric]
 207         super Boxed3d[N]
 208         super Box[N]
 209
 210         redef var front: N
 211         redef var back: N
 212
 213         # Create a `Box` covering all of the `boxed`
 214         #
 215         #     var box = new Box[Int].around(new Point[Int](-4,-4), new Point[Int](4,4))
 216         #     assert box.left == -4 and box.bottom == -4
 217         #     assert box.right == 4 and box.top == 4
 218         init around(boxed: Boxed3d[N]...)
 219         do
 220                 super
 221
 222                 assert not boxed.is_empty
 223
 224                 var left: nullable N = null
 225                 var right: nullable N = null
 226                 var top: nullable N = null
 227                 var bottom: nullable N = null
 228                 var front: nullable N = null
 229                 var back: nullable N= null
 230
 231                 for box in boxed do
 232                         if left == null or box.left < left then left = box.left
 233                         if right == null or box.right > right then right = box.right
 234                         if top == null or box.top > top then top = box.top
 235                         if bottom == null or box.bottom < bottom then bottom = box.bottom
 236                         if front == null or box.front > front then front = box.front
 237                         if back == null or box.back < back then back = box.back
 238                 end
 239
 240                 assert left != null and right != null and top != null and bottom != null
 241
 242                 self.left = left
 243                 self.right = right
 244                 self.top = top
 245                 self.bottom = bottom
 246         end
 247
 248         # Create a `Box3d` using left, right, bottom, top, front and back
 249         init lrbtfb(left, right, bottom, top, front, back: N)
 250         do
 251                 lrbt(left, right, bottom, top)
 252
 253                 self.front = front
 254                 self.back = back
 255         end
 256
 257         # Create a `Box3d` using left, right, top, bottom, front and back
 258         init lrtbfb(left, right, top, bottom, front, back: N)
 259         do
 260                 lrtb(left, right, top, bottom)
 261
 262                 self.front = front
 263                 self.back = back
 264         end
 265
 266         # Create a `Box3d` using left, top, front, width, height and depth
 267         init lbfwhd(left, bottom, front, width, height, depth: N)
 268         do
 269                 lbwh(left, bottom, width, height)
 270
 271                 self.front = front
 272                 self.back = front - depth
 273         end
 274
 275         # Create a `Box3d` using left, top, front, width, height and depth
 276         init ltfwhd(left, top, front, width, height, depth: N)
 277         do
 278                 ltwh(left, top, width, height)
 279
 280                 self.front = front
 281                 self.back = front - depth
 282         end
 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 # `BoxedCollection` implemented by an array
 326 #
 327 # Linear performances for searching, but really fast creation and filling.
 328 class BoxedArray[E: Boxed[Numeric]]
 329         super BoxedCollection[E]
 330         super Array[E]
 331
 332         redef fun items_overlapping(item)
 333         do
 334                 var arr = new Array[E]
 335                 for i in self do
 336                         if i.intersects(item) then arr.add(i)
 337                 end
 338                 return arr
 339         end
 340 end