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 encloses 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.left == 2 and b.right == 8 and b.top == 13 and b.bottom == 7
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
123 init(left
, right
, top
, bottom
)
126 # Create a `Box` using left, right, bottom and top
127 init lrbt
(left
, right
, bottom
, top
: N
)
129 init(left
, right
, top
, bottom
)
132 # Create a `Box` using left, right, top and bottom
133 init lrtb
(left
, right
, top
, bottom
: N
)
135 init(left
, right
, top
, bottom
)
138 # Create a `Box` using left, bottom, width and height
139 init lbwh
(left
, bottom
, width
, height
: N
)
141 init(left
, left
+ width
, bottom
+ height
, bottom
)
144 # Create a `Box` using left, top, width and height
145 init ltwh
(left
, top
, width
, height
: N
)
147 init(left
, left
+width
, top
, top
- height
)
150 redef fun to_s
do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}>"
153 # An 3d abstract bounded object
154 interface Boxed3d[N
: Numeric]
159 # require: front >= back
160 fun front
: N
is abstract
164 # require: back <= bottom
165 fun back
: N
is abstract
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
)
178 return super and (not other
isa Boxed3d[N
] or
179 (self.front
>= other
.front
and self.back
<= other
.back
))
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
)
193 return super and (not other
isa Boxed3d[N
] or
194 (self.back
<= other
.front
and other
.back
<= self.front
))
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
)
200 # A 3d bounded object and an implementation of Boxed
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]
211 # Create a `Box` covering all of the `boxed`
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
]...)
220 assert not boxed
.is_empty
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
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
238 assert left
!= null and right
!= null and top
!= null and bottom
!= null
246 # Create a `Box3d` using left, right, bottom, top, front and back
247 init lrbtfb
(left
, right
, bottom
, top
, front
, back
: N
)
249 lrbt
(left
, right
, bottom
, top
)
255 # Create a `Box3d` using left, right, top, bottom, front and back
256 init lrtbfb
(left
, right
, top
, bottom
, front
, back
: N
)
258 lrtb
(left
, right
, top
, bottom
)
264 # Create a `Box3d` using left, top, front, width, height and depth
265 init lbfwhd
(left
, bottom
, front
, width
, height
, depth
: N
)
267 lbwh
(left
, bottom
, width
, height
)
270 self.back
= front
- depth
273 # Create a `Box3d` using left, top, front, width, height and depth
274 init ltfwhd
(left
, top
, front
, width
, height
, depth
: N
)
276 ltwh
(left
, top
, width
, height
)
279 self.back
= front
- depth
282 redef fun to_s
do return "<left: {left}, right: {right}, top: {top}, bottom: {bottom}, front: {front}, back: {back}"
285 redef class IPoint[N
]
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
294 redef class IPoint3d[N
]
297 redef fun front
do return z
298 redef fun back
do return z
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
)
310 redef class ILine3d[N
]
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
)
317 # Base for all data structures containing multiple Boxed Objects
318 interface BoxedCollection[E
: Boxed[Numeric]]
319 super SimpleCollection[E
]
321 # returns all the items overlapping with `region`
322 fun items_overlapping
(region
:Boxed[Numeric]): SimpleCollection[E
] is abstract
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
]
330 private var data
: Array[E
] = new Array[E
]
332 redef fun add
(item
) do data
.add
(item
)
333 redef fun items_overlapping
(item
): SimpleCollection[E
]
335 var arr
= new Array[E
]
337 if i
.intersects
(item
) then arr
.add
(i
)
342 redef fun iterator
do return data
.iterator