lib/geometry/quadtree.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   3 # Copyright 2014 Romain Chanoir <romain.chanoir@viacesi.fr>
   4 #
   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
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  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.
  16
  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
  22 module quadtree
  23
  24 import boxes
  25 import pipeline
  26
  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]
  31
  32         protected var center: nullable Point[Numeric]
  33         var data: Array[E] = new Array[E]
  34
  35         #  ________________
  36         #  |       |       |
  37         #  |   1   |   2   |
  38         #  |-------|-------|
  39         #  |   0   |   3   |
  40         #  |_______|_______|
  41
  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]
  46
  47         # represent the threshold before subdividing the node
  48         protected var item_limit = 4
  49         protected var parent_node: nullable QuadTree[E]
  50
  51         # create the quadtree and set the item limit for each node
  52         init(limit: Int)
  53         do
  54                 self.item_limit = limit
  55         end
  56
  57         # create a node, giving him self as a parent. Used to create children nodes
  58         init with_parent(limit: Int, parent: QuadTree[E])
  59         do
  60                 init(limit)
  61                 self.parent_node = parent
  62         end
  63
  64         redef fun items_overlapping(region :Boxed[Numeric]): SimpleCollection[E] do
  65         var res = new Array[E]
  66         items_overlapping_in(region,res)
  67         return res
  68      end
  69
  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)
  72
  73         private fun add_to_children(item: Boxed[Numeric])
  74         do
  75                 if self.child0 != null then
  76                         if self.center.x > item.right then
  77                                 if self.center.y > item.top then
  78                                         child0.add(item)
  79                                 else if self.center.y < item.bottom then
  80                                         child1.add(item)
  81                                 else
  82                                         self.data.add(item)
  83                                 end
  84                         else if self.center.x < item.left then
  85                                 if self.center.y > item.top then
  86                                         child3.add(item)
  87                                 else if self.center.y < item.bottom then
  88                                         child2.add(item)
  89                                 else
  90                                         self.data.add(item)
  91                                 end
  92                         else if self.center.y > item.top then
  93                                 self.data.add(item)
  94                         else if self.center.y < item.bottom then
  95                                         self.data.add(item)
  96                         else
  97                                 self.data.add(item)
  98                         end
  99                 end
 100         end
 101
 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))
 103
 104         # Return whether or not the Node is a leaf of the tree
 105         fun is_leaf: Bool do return child0 == null
 106
 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)
 111         #     dquadtree.add(p1)
 112         #     dquadtree.add(p2)
 113         #     dquadtree.add(p3)
 114         #     var result = dquadtree.items_overlapping(p3)
 115         #     assert result.length == 1
 116         #     result.clear
 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])
 123         do
 124                 if self.is_leaf and data.length >= item_limit then
 125                         subdivide
 126                         var data_copy = data
 127                         data = new Array[E]
 128                         #add to the right Node
 129                         for d in data_copy do
 130                                 add_to_children(d)
 131                         end
 132                 end
 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)
 140                                 else
 141                                         child0.items_overlapping_in(region,mdata)
 142                                         child1.items_overlapping_in(region, mdata)
 143                                 end
 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)
 149                                 else
 150                                         child3.items_overlapping_in(region, mdata)
 151                                         child2.items_overlapping_in(region, mdata)
 152                                 end
 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)
 159                         else
 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)
 164                         end
 165                 end
 166         end
 167
 168         # this function is responsible of the creation of the children,
 169         # depending on your needs
 170         protected fun subdivide is abstract
 171
 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
 173 end
 174
 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]]
 179         super QuadTree[E]
 180
 181         redef fun subdivide
 182         do
 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)
 188         end
 189
 190         # average x of data in this node
 191         fun average_x: Numeric
 192         do
 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)
 196                 end
 197                 return x_total/x_total.value_of(self.data.length)
 198         end
 199
 200         # average y of data in this node
 201         fun average_y: Numeric
 202         do
 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)
 206                 end
 207                 return y_total/y_total.value_of(self.data.length)
 208         end
 209 end
 210
 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]]
 217         super QuadTree[E]
 218
 219         # the width of the current node of the QuadTree
 220         var width: Numeric
 221         # the height of the current node of the QuadTree
 222         var height: Numeric
 223
 224         init(l: Int, c: Point[Numeric], w: Numeric, h: Numeric)
 225         do
 226                 self.item_limit = l
 227                 self.center = c
 228                 self.width = w
 229                 self.height = h
 230         end
 231
 232         init with_parent(l: Int, c: Point[Numeric], w: Numeric, h: Numeric, p: QuadTree[E])
 233         do
 234                 init(l, c, w, h)
 235                 self.parent_node = p
 236         end
 237
 238         redef fun subdivide
 239         do
 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)
 246         end
 247 end