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] = null
  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] = 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
  46
  47         # represent the threshold before subdividing the node
  48         protected var item_limit: Int
  49         protected var parent_node: nullable QuadTree[E] = null
  50
  51         # create a node, giving him self as a parent. Used to create children nodes
  52         init with_parent(limit: Int, parent: QuadTree[E])
  53         do
  54                 init(limit)
  55                 self.parent_node = parent
  56         end
  57
  58         redef fun items_overlapping(region :Boxed[Numeric]): SimpleCollection[E] do
  59         var res = new Array[E]
  60         items_overlapping_in(region,res)
  61         return res
  62      end
  63
  64         # add the item to the tree, create children if the limit is reached
  65         redef fun add(item: E) do if self.is_leaf then self.data.add(item) else add_to_children(item)
  66
  67         private fun add_to_children(item: Boxed[Numeric])
  68         do
  69                 if self.child0 != null then
  70                         if self.center.x > item.right then
  71                                 if self.center.y > item.top then
  72                                         child0.add(item)
  73                                 else if self.center.y < item.bottom then
  74                                         child1.add(item)
  75                                 else
  76                                         self.data.add(item)
  77                                 end
  78                         else if self.center.x < item.left then
  79                                 if self.center.y > item.top then
  80                                         child3.add(item)
  81                                 else if self.center.y < item.bottom then
  82                                         child2.add(item)
  83                                 else
  84                                         self.data.add(item)
  85                                 end
  86                         else if self.center.y > item.top then
  87                                 self.data.add(item)
  88                         else if self.center.y < item.bottom then
  89                                         self.data.add(item)
  90                         else
  91                                 self.data.add(item)
  92                         end
  93                 end
  94         end
  95
  96         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))
  97
  98         # Return whether or not the Node is a leaf of the tree
  99         fun is_leaf: Bool do return child0 == null
 100
 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)
 105         #     dquadtree.add(p1)
 106         #     dquadtree.add(p2)
 107         #     dquadtree.add(p3)
 108         #     var result = dquadtree.items_overlapping(p3)
 109         #     assert result.length == 1
 110         #     result.clear
 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])
 117         do
 118                 if self.is_leaf and data.length >= item_limit then
 119                         subdivide
 120                         var data_copy = data
 121                         data = new Array[E]
 122                         #add to the right Node
 123                         for d in data_copy do
 124                                 add_to_children(d)
 125                         end
 126                 end
 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)
 134                                 else
 135                                         child0.items_overlapping_in(region,mdata)
 136                                         child1.items_overlapping_in(region, mdata)
 137                                 end
 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)
 143                                 else
 144                                         child3.items_overlapping_in(region, mdata)
 145                                         child2.items_overlapping_in(region, mdata)
 146                                 end
 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)
 153                         else
 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)
 158                         end
 159                 end
 160         end
 161
 162         # this function is responsible of the creation of the children,
 163         # depending on your needs
 164         protected fun subdivide is abstract
 165
 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
 167 end
 168
 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]]
 173         super QuadTree[E]
 174
 175         redef fun subdivide
 176         do
 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)
 182         end
 183
 184         # average x of data in this node
 185         fun average_x: Numeric
 186         do
 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)
 190                 end
 191                 return x_total/x_total.value_of(self.data.length)
 192         end
 193
 194         # average y of data in this node
 195         fun average_y: Numeric
 196         do
 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)
 200                 end
 201                 return y_total/y_total.value_of(self.data.length)
 202         end
 203 end
 204
 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]]
 211         super QuadTree[E]
 212
 213         # the width of the current node of the QuadTree
 214         var width: Numeric
 215         # the height of the current node of the QuadTree
 216         var height: Numeric
 217
 218         init with_parent(l: Int, c: Point[Numeric], w: Numeric, h: Numeric, p: QuadTree[E])
 219         do
 220                 init(l, w, h)
 221                 center = c
 222                 self.parent_node = p
 223         end
 224
 225         redef fun subdivide
 226         do
 227                 var two = self.center.x.value_of(2)
 228                 var tree = self.center.x.value_of(3)
 229                 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)
 230                 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)
 231                 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)
 232                 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)
 233         end
 234 end