1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Copyright 2014 Romain Chanoir <romain.chanoir@viacesi.fr>
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 # QuadTree API mostly used for 2 dimensional collision detection
19 # The QuadTree data structure partition a 2D space by recursively
20 # subdividing it into 4 regions when its capacity is reached.
21 # This module introduces 2 main implementation of the structure,
22 # a static and a dynamic QuadTree.
28 # Abstract QuadTree implementing the basic functions and data
29 abstract class QuadTree[E
: Boxed[Numeric]]
30 super BoxedCollection[E
]
32 # Center coordinate of the children
33 protected var center
: nullable Point[Numeric] = null
36 protected var data
= new Array[E
]
38 # Children nodes, if not `is_leaf`
48 protected var children
= new Array[QuadTree[E
]]
50 # Maximum number of items in this node before subdividing
51 protected var item_limit
: Int
53 # Parent node in the tree
54 protected var parent_node
: nullable QuadTree[E
] = null
56 # Create a child node to `parent`
57 init with_parent
(limit
: Int, parent
: QuadTree[E
])
60 self.parent_node
= parent
63 redef fun items_overlapping
(region
): SimpleCollection[E
] do
64 var res
= new Array[E
]
65 items_overlapping_in
(region
,res
)
69 # Add `item` to the tree, create children if `item_limit` is reached
70 redef fun add
(item
) do if self.is_leaf
then self.data
.add
(item
) else add_to_children
(item
)
72 private fun add_to_children
(item
: Boxed[Numeric])
74 if children
.not_empty
then
77 if center
.x
> item
.right
then
78 if center
.y
> item
.top
then
80 else if center
.y
< item
.bottom
then
85 else if center
.x
< item
.left
then
86 if center
.y
> item
.top
then
88 else if center
.y
< item
.bottom
then
93 else if center
.y
> item
.top
then
95 else if center
.y
< item
.bottom
then
105 if is_leaf
then return data
.is_empty
107 assert children
.length
>= 4
108 return data
.is_empty
and children
[0].is_empty
and children
[1].is_empty
and children
[2].is_empty
and children
[3].is_empty
111 # Return whether or not the Node is a leaf of the tree
112 fun is_leaf
: Bool do return children
.is_empty
114 # var dquadtree = new DQuadTree[Point[Int]](2)
115 # var p1 = new Point[Int](0,0)
116 # var p2 = new Point[Int](0,9)
117 # var p3 = new Point[Int](9,0)
121 # var result = dquadtree.items_overlapping(p3)
122 # assert result.length == 1
124 # var p4 = new Point[Int](9,9)
125 # result = dquadtree.items_overlapping(p4)
126 # assert result.length == 0
127 # result = dquadtree.items_overlapping(p4.padded(10))
128 # assert result.length == 3
129 private fun items_overlapping_in
(region
: Boxed[Numeric], mdata
: SimpleCollection[E
])
131 if self.is_leaf
and data
.length
>= item_limit
then
135 #add to the right Node
136 for d
in data_copy
do
140 for i
in data
do if i
.intersects
(region
) then mdata
.add
(i
)
142 if children
.not_empty
then
144 assert center
!= null
145 if center
.x
> region
.right
then
146 if center
.y
> region
.top
then
147 children
[0].items_overlapping_in
(region
, mdata
)
148 else if center
.y
< region
.bottom
then
149 children
[1].items_overlapping_in
(region
, mdata
)
151 children
[0].items_overlapping_in
(region
,mdata
)
152 children
[1].items_overlapping_in
(region
, mdata
)
154 else if center
.x
< region
.left
then
155 if center
.y
> region
.top
then
156 children
[3].items_overlapping_in
(region
, mdata
)
157 else if center
.y
< region
.bottom
then
158 children
[2].items_overlapping_in
(region
, mdata
)
160 children
[3].items_overlapping_in
(region
, mdata
)
161 children
[2].items_overlapping_in
(region
, mdata
)
163 else if center
.y
> region
.top
then
164 children
[0].items_overlapping_in
(region
, mdata
)
165 children
[3].items_overlapping_in
(region
, mdata
)
166 else if center
.y
< region
.bottom
then
167 children
[1].items_overlapping_in
(region
, mdata
)
168 children
[2].items_overlapping_in
(region
, mdata
)
170 children
[0].items_overlapping_in
(region
, mdata
)
171 children
[1].items_overlapping_in
(region
, mdata
)
172 children
[2].items_overlapping_in
(region
, mdata
)
173 children
[3].items_overlapping_in
(region
, mdata
)
178 # Create children nodes, depends on the concrete implementation
179 protected fun subdivide
is abstract
183 if is_leaf
then return data
.iterator
185 assert children
.length
>= 4
186 return data
.iterator
+ children
[0].iterator
+ children
[1].iterator
+ children
[2].iterator
+ children
[3].iterator
190 # A dynamic implementation of the quadtree data structure
192 # The center of the parent node is determined by the average
193 # values of the data it contains when `item_limit` is reached.
194 class DQuadTree[E
: Boxed[Numeric]]
199 self.center
= new Point[Numeric](average_x
, average_y
)
200 children
[0] = new DQuadTree[E
].with_parent
(self.item_limit
, self)
201 children
[1] = new DQuadTree[E
].with_parent
(self.item_limit
, self)
202 children
[2] = new DQuadTree[E
].with_parent
(self.item_limit
, self)
203 children
[3] = new DQuadTree[E
].with_parent
(self.item_limit
, self)
206 # Average X coordinate of the items in this node
207 fun average_x
: Numeric
209 var x_total
= data
.first
.left
.zero
210 for data
in self.data
do
211 x_total
+= (data
.left
+ data
.right
)/x_total
.value_of
(2)
213 return x_total
/x_total
.value_of
(self.data
.length
)
216 # Average Y coordinate of the items in this node
217 fun average_y
: Numeric
219 var y_total
= data
.first
.left
.zero
220 for data
in self.data
do
221 y_total
+= (data
.left
+ data
.right
)/y_total
.value_of
(2)
223 return y_total
/y_total
.value_of
(self.data
.length
)
227 # Static implementation of the quadtree structure
229 # You need to specify a zone when creating the quadtree,
230 # which will be the zone corresponding to the root node.
231 # Each subdivision cut the space in 4 equal regions from
232 # the center of the parent node.
233 class SQuadTree[E
: Boxed[Numeric]]
236 # Width of this node of the QuadTree
239 # Height of this node of the QuadTree
244 center
= new Point[Numeric](width
.div
(2), height
.div
(2))
247 # Create a child node to `parent`
248 init with_parent
(l
: Int, c
: Point[Numeric], w
, h
: Numeric, parent
: QuadTree[E
])
252 self.parent_node
= parent
258 assert center
!= null
260 children
[0] = new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric](center
.x
.div
(2), center
.y
.div
(2)), self.width
.div
(2), self.height
.div
(2), self)
261 children
[1] = new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric](center
.x
.div
(2), (center
.y
.mul
(3)).div
(2)), self.width
.div
(2), self.height
.div
(2), self)
262 children
[2] = new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric]((center
.x
.mul
(3)).div
(2), (center
.y
.mul
(3)).div
(2)), self.width
.div
(2), self.height
.div
(2), self)
263 children
[3] = new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric]((center
.x
.mul
(3)).div
(2), center
.y
.div
(2)), self.width
.div
(2), self.height
.div
(2), self)
268 var s
= "center : {center or else "null"}\n"
269 for d
in data
do s
+= d
.to_s
271 if children
.not_empty
then
272 s
+= "\n children[0]: {children[0]}\n"
273 s
+= " children[1]: {children[1]}\n"
274 s
+= " children[2]: {children[2]}\n"
275 s
+= " children[3]: {children[3]}\n"