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
18 # The QuadTree data structure partition a 2D space by recursively
19 # subdividing it into 4 regions when it's capacity is reached
20 # This module introduce 2 principal implementation of the structure,
21 # the static and the dynamic QuadTree
27 # Abstract QuadTree implementing most of the basic functions
28 # and introducing specific QuadTree data
29 abstract class QuadTree[E
: Boxed[Numeric]]
30 super BoxedCollection[E
]
32 protected var center
: nullable Point[Numeric]
33 var data
: Array[E
] = new Array[E
]
42 protected var child0
: nullable QuadTree[E
]
43 protected var child1
: nullable QuadTree[E
]
44 protected var child2
: nullable QuadTree[E
]
45 protected var child3
: nullable QuadTree[E
]
47 # represent the threshold before subdividing the node
48 protected var item_limit
= 4
49 protected var parent_node
: nullable QuadTree[E
]
51 # create the quadtree and set the item limit for each node
54 self.item_limit
= limit
57 # create a node, giving him self as a parent. Used to create children nodes
58 init with_parent
(limit
: Int, parent
: QuadTree[E
])
61 self.parent_node
= parent
64 redef fun items_overlapping
(region
:Boxed[Numeric]): SimpleCollection[E
] do
65 var res
= new Array[E
]
66 items_overlapping_in
(region
,res
)
70 # add the item to the tree, create children if the limit is reached
71 redef fun add
(item
: E
) do if self.is_leaf
then self.data
.add
(item
) else add_to_children
(item
)
73 private fun add_to_children
(item
: Boxed[Numeric])
75 if self.child0
!= null then
76 if self.center
.x
> item
.right
then
77 if self.center
.y
> item
.top
then
79 else if self.center
.y
< item
.bottom
then
84 else if self.center
.x
< item
.left
then
85 if self.center
.y
> item
.top
then
87 else if self.center
.y
< item
.bottom
then
92 else if self.center
.y
> item
.top
then
94 else if self.center
.y
< item
.bottom
then
102 redef fun is_empty
: Bool do return data
.is_empty
and (self.is_leaf
or (child0
.is_empty
and child1
.is_empty
and child2
.is_empty
and child3
.is_empty
))
104 # Return whether or not the Node is a leaf of the tree
105 fun is_leaf
: Bool do return child0
== null
107 # var dquadtree = new DQuadTree[Point[Int]](2)
108 # var p1 = new Point[Int](0,0)
109 # var p2 = new Point[Int](0,9)
110 # var p3 = new Point[Int](9,0)
114 # var result = dquadtree.items_overlapping(p3)
115 # assert result.length == 1
117 # var p4 = new Point[Int](9,9)
118 # result = dquadtree.items_overlapping(p4)
119 # assert result.length == 0
120 # result = dquadtree.items_overlapping(p4.padded(10))
121 # assert result.length == 3
122 fun items_overlapping_in
(region
: Boxed[Numeric], mdata
: SimpleCollection[E
])
124 if self.is_leaf
and data
.length
>= item_limit
then
128 #add to the right Node
129 for d
in data_copy
do
133 for i
in data
do if i
.intersects
(region
) then mdata
.add
(i
)
134 if self.child0
!= null then
135 if self.center
.x
> region
.right
then
136 if self.center
.y
> region
.top
then
137 child0
.items_overlapping_in
(region
, mdata
)
138 else if self.center
.y
< region
.bottom
then
139 child1
.items_overlapping_in
(region
, mdata
)
141 child0
.items_overlapping_in
(region
,mdata
)
142 child1
.items_overlapping_in
(region
, mdata
)
144 else if self.center
.x
< region
.left
then
145 if self.center
.y
> region
.top
then
146 child3
.items_overlapping_in
(region
, mdata
)
147 else if self.center
.y
< region
.bottom
then
148 child2
.items_overlapping_in
(region
, mdata
)
150 child3
.items_overlapping_in
(region
, mdata
)
151 child2
.items_overlapping_in
(region
, mdata
)
153 else if self.center
.y
> region
.top
then
154 child0
.items_overlapping_in
(region
, mdata
)
155 child3
.items_overlapping_in
(region
, mdata
)
156 else if self.center
.y
< region
.bottom
then
157 child1
.items_overlapping_in
(region
, mdata
)
158 child2
.items_overlapping_in
(region
, mdata
)
160 child0
.items_overlapping_in
(region
, mdata
)
161 child1
.items_overlapping_in
(region
, mdata
)
162 child2
.items_overlapping_in
(region
, mdata
)
163 child3
.items_overlapping_in
(region
, mdata
)
168 # this function is responsible of the creation of the children,
169 # depending on your needs
170 protected fun subdivide
is abstract
172 redef fun iterator
do if self.is_leaf
then return data
.iterator
else return data
.iterator
+ child0
.iterator
+ child1
.iterator
+ child2
.iterator
+ child3
.iterator
175 # A dynamic implementation of the quadtree data structure
176 # the center of the parent node is determined by the average
177 # values of the data it contains when the item limit is reached
178 class DQuadTree[E
: Boxed[Numeric]]
183 self.center
= new Point[Numeric](average_x
, average_y
)
184 child0
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
185 child1
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
186 child2
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
187 child3
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
190 # average x of data in this node
191 fun average_x
: Numeric
193 var x_total
= data
.first
.left
.zero
194 for data
in self.data
do
195 x_total
+= (data
.left
+ data
.right
)/x_total
.value_of
(2)
197 return x_total
/x_total
.value_of
(self.data
.length
)
200 # average y of data in this node
201 fun average_y
: Numeric
203 var y_total
= data
.first
.left
.zero
204 for data
in self.data
do
205 y_total
+= (data
.left
+ data
.right
)/y_total
.value_of
(2)
207 return y_total
/y_total
.value_of
(self.data
.length
)
211 # Static implementation of the quadtree structure.
212 # You need to specify a zone when creating the quadtree,
213 # which will be the zone corresponding to the root node.
214 # each subdivision cut the space in 4 equal regions from
215 # the center of the parent node
216 class SQuadTree[E
: Boxed[Numeric]]
219 # the width of the current node of the QuadTree
221 # the height of the current node of the QuadTree
224 init(l
: Int, c
: Point[Numeric], w
: Numeric, h
: Numeric)
232 init with_parent
(l
: Int, c
: Point[Numeric], w
: Numeric, h
: Numeric, p
: QuadTree[E
])
240 var two
= self.center
.x
.value_of
(2)
241 var tree
= self.center
.x
.value_of
(3)
242 child0
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric](self.center
.x
/two
, self.center
.y
/two
), self.width
/two
, self.height
/two
, self)
243 child1
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric](self.center
.x
/two
, (self.center
.y
*tree
)/two
), self.width
/two
, self.height
/two
, self)
244 child2
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric]((self.center
.x
*tree
)/two
, (self.center
.y
*tree
)/two
), self.width
/two
, self.height
/two
, self)
245 child3
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric]((self.center
.x
*tree
)/two
, self.center
.y
/two
), self.width
/two
, self.height
/two
, self)