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
)
87 redef fun to_s
do return "<{class_name} left: {left}, right: {right}, top: {top}, bottom: {bottom}>"
90 # A 2d bounded object and an implementation of `Boxed`
92 # This class offers many constructors specialized for different usage. They are
93 # named according to the order of their arguments.
102 # Create a `Box` covering all of the `boxed`
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
]...)
109 assert not boxed
.is_empty
111 var left
: nullable N
= null
112 var right
: nullable N
= null
113 var top
: nullable N
= null
114 var bottom
: nullable N
= null
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
123 assert left
!= null and right
!= null and top
!= null and bottom
!= null
125 init(left
, right
, top
, bottom
)
128 # Create a `Box` using left, right, bottom and top
129 init lrbt
(left
, right
, bottom
, top
: N
)
131 init(left
, right
, top
, bottom
)
134 # Create a `Box` using left, right, top and bottom
135 init lrtb
(left
, right
, top
, bottom
: N
)
137 init(left
, right
, top
, bottom
)
140 # Create a `Box` using left, bottom, width and height
141 init lbwh
(left
, bottom
, width
, height
: N
)
143 init(left
, left
+ width
, bottom
+ height
, bottom
)
146 # Create a `Box` using left, top, width and height
147 init ltwh
(left
, top
, width
, height
: N
)
149 init(left
, left
+width
, top
, top
- height
)
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
)
199 redef fun to_s
do return "<{class_name} left: {left}, right: {right}, top: {top}, bottom: {bottom}, front: {front}, back: {back}>"
202 # A 3d bounded object and an implementation of Boxed
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]
213 # Create a `Box` covering all of the `boxed`
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
]...)
222 assert not boxed
.is_empty
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
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
240 assert left
!= null and right
!= null and top
!= null and bottom
!= null
248 # Create a `Box3d` using left, right, bottom, top, front and back
249 init lrbtfb
(left
, right
, bottom
, top
, front
, back
: N
)
251 lrbt
(left
, right
, bottom
, top
)
257 # Create a `Box3d` using left, right, top, bottom, front and back
258 init lrtbfb
(left
, right
, top
, bottom
, front
, back
: N
)
260 lrtb
(left
, right
, top
, bottom
)
266 # Create a `Box3d` using left, top, front, width, height and depth
267 init lbfwhd
(left
, bottom
, front
, width
, height
, depth
: N
)
269 lbwh
(left
, bottom
, width
, height
)
272 self.back
= front
- depth
275 # Create a `Box3d` using left, top, front, width, height and depth
276 init ltfwhd
(left
, top
, front
, width
, height
, depth
: N
)
278 ltwh
(left
, top
, width
, height
)
281 self.back
= front
- depth
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 # `BoxedCollection` implemented by an array
327 # Linear performances for searching, but really fast creation and filling.
328 class BoxedArray[E
: Boxed[Numeric]]
329 super BoxedCollection[E
]
332 redef fun items_overlapping
(item
)
334 var arr
= new Array[E
]
336 if i
.intersects
(item
) then arr
.add
(i
)