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] = null
33 var data
: Array[E
] = new Array[E
]
42 protected var child0
: nullable QuadTree[E
] = null
43 protected var child1
: nullable QuadTree[E
] = null
44 protected var child2
: nullable QuadTree[E
] = null
45 protected var child3
: nullable QuadTree[E
] = null
47 # represent the threshold before subdividing the node
48 protected var item_limit
: Int
49 protected var parent_node
: nullable QuadTree[E
] = null
51 # create a node, giving him self as a parent. Used to create children nodes
52 init with_parent
(limit
: Int, parent
: QuadTree[E
])
55 self.parent_node
= parent
58 redef fun items_overlapping
(region
): SimpleCollection[E
] do
59 var res
= new Array[E
]
60 items_overlapping_in
(region
,res
)
64 # add the item to the tree, create children if the limit is reached
65 redef fun add
(item
) do if self.is_leaf
then self.data
.add
(item
) else add_to_children
(item
)
67 private fun add_to_children
(item
: Boxed[Numeric])
69 if self.child0
!= null then
70 if self.center
.x
> item
.right
then
71 if self.center
.y
> item
.top
then
73 else if self.center
.y
< item
.bottom
then
78 else if self.center
.x
< item
.left
then
79 if self.center
.y
> item
.top
then
81 else if self.center
.y
< item
.bottom
then
86 else if self.center
.y
> item
.top
then
88 else if self.center
.y
< item
.bottom
then
96 redef fun is_empty
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
))
98 # Return whether or not the Node is a leaf of the tree
99 fun is_leaf
: Bool do return child0
== null
101 # var dquadtree = new DQuadTree[Point[Int]](2)
102 # var p1 = new Point[Int](0,0)
103 # var p2 = new Point[Int](0,9)
104 # var p3 = new Point[Int](9,0)
108 # var result = dquadtree.items_overlapping(p3)
109 # assert result.length == 1
111 # var p4 = new Point[Int](9,9)
112 # result = dquadtree.items_overlapping(p4)
113 # assert result.length == 0
114 # result = dquadtree.items_overlapping(p4.padded(10))
115 # assert result.length == 3
116 fun items_overlapping_in
(region
: Boxed[Numeric], mdata
: SimpleCollection[E
])
118 if self.is_leaf
and data
.length
>= item_limit
then
122 #add to the right Node
123 for d
in data_copy
do
127 for i
in data
do if i
.intersects
(region
) then mdata
.add
(i
)
128 if self.child0
!= null then
129 if self.center
.x
> region
.right
then
130 if self.center
.y
> region
.top
then
131 child0
.items_overlapping_in
(region
, mdata
)
132 else if self.center
.y
< region
.bottom
then
133 child1
.items_overlapping_in
(region
, mdata
)
135 child0
.items_overlapping_in
(region
,mdata
)
136 child1
.items_overlapping_in
(region
, mdata
)
138 else if self.center
.x
< region
.left
then
139 if self.center
.y
> region
.top
then
140 child3
.items_overlapping_in
(region
, mdata
)
141 else if self.center
.y
< region
.bottom
then
142 child2
.items_overlapping_in
(region
, mdata
)
144 child3
.items_overlapping_in
(region
, mdata
)
145 child2
.items_overlapping_in
(region
, mdata
)
147 else if self.center
.y
> region
.top
then
148 child0
.items_overlapping_in
(region
, mdata
)
149 child3
.items_overlapping_in
(region
, mdata
)
150 else if self.center
.y
< region
.bottom
then
151 child1
.items_overlapping_in
(region
, mdata
)
152 child2
.items_overlapping_in
(region
, mdata
)
154 child0
.items_overlapping_in
(region
, mdata
)
155 child1
.items_overlapping_in
(region
, mdata
)
156 child2
.items_overlapping_in
(region
, mdata
)
157 child3
.items_overlapping_in
(region
, mdata
)
162 # this function is responsible of the creation of the children,
163 # depending on your needs
164 protected fun subdivide
is abstract
166 redef fun iterator
do if self.is_leaf
then return data
.iterator
else return data
.iterator
+ child0
.iterator
+ child1
.iterator
+ child2
.iterator
+ child3
.iterator
169 # A dynamic implementation of the quadtree data structure
170 # the center of the parent node is determined by the average
171 # values of the data it contains when the item limit is reached
172 class DQuadTree[E
: Boxed[Numeric]]
177 self.center
= new Point[Numeric](average_x
, average_y
)
178 child0
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
179 child1
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
180 child2
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
181 child3
= new DQuadTree[E
].with_parent
(self.item_limit
, self)
184 # average x of data in this node
185 fun average_x
: Numeric
187 var x_total
= data
.first
.left
.zero
188 for data
in self.data
do
189 x_total
+= (data
.left
+ data
.right
)/x_total
.value_of
(2)
191 return x_total
/x_total
.value_of
(self.data
.length
)
194 # average y of data in this node
195 fun average_y
: Numeric
197 var y_total
= data
.first
.left
.zero
198 for data
in self.data
do
199 y_total
+= (data
.left
+ data
.right
)/y_total
.value_of
(2)
201 return y_total
/y_total
.value_of
(self.data
.length
)
205 # Static implementation of the quadtree structure.
206 # You need to specify a zone when creating the quadtree,
207 # which will be the zone corresponding to the root node.
208 # each subdivision cut the space in 4 equal regions from
209 # the center of the parent node
210 class SQuadTree[E
: Boxed[Numeric]]
213 # the width of the current node of the QuadTree
215 # the height of the current node of the QuadTree
220 center
= new Point[Numeric](width
.div
(2), height
.div
(2))
223 init with_parent
(l
: Int, c
: Point[Numeric], w
: Numeric, h
: Numeric, p
: QuadTree[E
])
232 child0
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric](self.center
.x
.div
(2), self.center
.y
.div
(2)), self.width
.div
(2), self.height
.div
(2), self)
233 child1
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric](self.center
.x
.div
(2), (self.center
.y
.mul
(3)).div
(2)), self.width
.div
(2), self.height
.div
(2), self)
234 child2
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric]((self.center
.x
.mul
(3)).div
(2), (self.center
.y
.mul
(3)).div
(2)), self.width
.div
(2), self.height
.div
(2), self)
235 child3
= new SQuadTree[E
].with_parent
(self.item_limit
, new Point[Numeric]((self.center
.x
.mul
(3)).div
(2), self.center
.y
.div
(2)), self.width
.div
(2), self.height
.div
(2), self)
240 var s
= "center : {center.to_s}\n"
241 for d
in data
do s
+= d
.to_s
242 if child0
!= null then
243 s
+= "\nchild0: {child0.to_s}\n"
244 s
+= " child1: {child1.to_s}\n"
245 s
+= " child2: {child2.to_s}\n"
246 s
+= " child3: {child3.to_s}\n"