1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Copyright 2014 Alexis Laferrière <alexis.laf@xymus.net>
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 # Provides interfaces and classes to represent basic geometry needs.
20 import points_and_lines
22 # An 2d abstract bounded object
23 interface Boxed[N
: Numeric]
26 # require: left <= right
27 fun left
: N
is abstract
31 # require: right >= left
32 fun right
: N
is abstract
36 # require: top >= bottom
37 fun top
: N
is abstract
41 # require: bottom <= top
42 fun bottom
: N
is abstract
44 # Is `other` contained within `self`?
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
57 return self.top
>= other
.top
and self.bottom
<= other
.bottom
and
58 self.left
<= other
.left
and self.right
>= other
.right
61 # Does `self` intersect with `other`?
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
74 return self.left
<= other
.right
and other
.left
<= self.right
and
75 self.top
>= other
.bottom
and other
.top
>= self.bottom
78 # Create a bounding box that englobes the actual bounding box.
79 # `dist` is the distance between the inner boundaries and the outer boundaries.
81 # var p = new Point[Int](5,10)
83 # assert b.top == 2 and b.bot = 8 and b.left == 7 and b.right == 13
85 fun padded
(dist
: N
): Box[N
] do return new Box[N
].lrtb
(left
- dist
, right
+ dist
, top
+ dist
, bottom
- dist
)
88 # A 2d bounded object and an implementation of `Boxed`
90 # This class offers many constructors specialized for different usage. They are
91 # named according to the order of their arguments.
100 # Create a `Box` covering all of the `boxed`
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
]...)
107 assert not boxed
.is_empty
109 var left
: nullable N
= null
110 var right
: nullable N
= null
111 var top
: nullable N
= null
112 var bottom
: nullable N
= null
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
121 assert left
!= null and right
!= null and top
!= null and bottom
!= null
129 # Create a `Box` using left, right, bottom and top
130 init lrbt
(left
, right
, bottom
, top
: N
)
138 # Create a `Box` using left, right, top and bottom
139 init lrtb
(left
, right
, top
, bottom
: N
)
147 # Create a `Box` using left, bottom, width and height
148 init lbwh
(left
, bottom
, width
, height
: N
)
153 self.right
= left
+ width
154 self.top
= bottom
+ height
157 # Create a `Box` using left, top, width and height
158 init ltwh
(left
, top
, width
, height
: N
)
163 self.right
= left
+ width
164 self.bottom
= top
- height
167 redef fun to_s
do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}>"
170 # An 3d abstract bounded object
171 interface Boxed3d[N
: Numeric]
176 # require: front >= back
177 fun front
: N
is abstract
181 # require: back <= bottom
182 fun back
: N
is abstract
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
)
195 return super and (not other
isa Boxed3d[N
] or
196 (self.front
>= other
.front
and self.back
<= other
.back
))
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
)
210 return super and (not other
isa Boxed3d[N
] or
211 (self.back
<= other
.front
and other
.back
<= self.front
))
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
)
217 # A 3d bounded object and an implementation of Boxed
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]
228 # Create a `Box` covering all of the `boxed`
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
]...)
235 assert not boxed
.is_empty
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
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
253 assert left
!= null and right
!= null and top
!= null and bottom
!= null
261 # Create a `Box3d` using left, right, bottom, top, front and back
262 init lrbtfb
(left
, right
, bottom
, top
, front
, back
: N
)
264 lrbt
(left
, right
, bottom
, top
)
270 # Create a `Box3d` using left, right, top, bottom, front and back
271 init lrtbfb
(left
, right
, top
, bottom
, front
, back
: N
)
273 lrtb
(left
, right
, top
, bottom
)
279 # Create a `Box3d` using left, top, front, width, height and depth
280 init lbfwhd
(left
, bottom
, front
, width
, height
, depth
: N
)
282 lbwh
(left
, bottom
, width
, height
)
285 self.back
= front
- depth
288 # Create a `Box3d` using left, top, front, width, height and depth
289 init ltfwhd
(left
, top
, front
, width
, height
, depth
: N
)
291 ltwh
(left
, top
, width
, height
)
294 self.back
= front
- depth
297 redef fun to_s
do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}, front: {front}, back: {back}"
300 redef class IPoint[N
]
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
309 redef class IPoint3d[N
]
312 redef fun front
do return z
313 redef fun back
do return z
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
)
325 redef class ILine3d[N
]
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
)
332 # Base for all data structures containing multiple Boxed Objects
333 interface BoxedCollection[E
: Boxed[Numeric]]
334 super SimpleCollection[E
]
336 # returns all the items overlapping with `region`
337 fun items_overlapping
(region
:Boxed[Numeric]): SimpleCollection[E
] is abstract
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
]
345 private var data
: Array[E
] = new Array[E
]
347 redef fun add
(item
: E
) do data
.add
(item
)
348 redef fun items_overlapping
(item
: Boxed[Numeric]): SimpleCollection[E
]
350 var arr
= new Array[E
]
352 if i
.intersects
(item
) then arr
.add
(i
)
357 redef fun iterator
do return data
.iterator