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 #
  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.
  23 module quadtree
  24
  25 import boxes
  26 import pipeline
  27
  28 # Abstract QuadTree implementing the basic functions and data
  29 abstract class QuadTree[E: Boxed[Numeric]]
  30         super BoxedCollection[E]
  31
  32         # Center coordinate of the children
  33         protected var center: nullable Point[Numeric] = null
  34
  35         # Items in this node
  36         protected var data = new Array[E]
  37
  38         # Children nodes, if not `is_leaf`
  39         #
  40         # ~~~raw
  41         # ________________
  42         # |       |       |
  43         # |   1   |   2   |
  44         # |-------|-------|
  45         # |   0   |   3   |
  46         # |_______|_______|
  47         # ~~~
  48         protected var children = new Array[QuadTree[E]]
  49
  50         # Maximum number of items in this node before subdividing
  51         protected var item_limit: Int
  52
  53         # Parent node in the tree
  54         protected var parent_node: nullable QuadTree[E] = null
  55
  56         # Create a child node to `parent`
  57         init with_parent(limit: Int, parent: QuadTree[E])
  58         do
  59                 init(limit)
  60                 self.parent_node = parent
  61         end
  62
  63         redef fun items_overlapping(region): SimpleCollection[E] do
  64                 var res = new Array[E]
  65                 items_overlapping_in(region,res)
  66                 return res
  67         end
  68
  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)
  71
  72         private fun add_to_children(item: Boxed[Numeric])
  73         do
  74                 if children.not_empty then
  75                         var center = center
  76                         assert center != null
  77                         if center.x > item.right then
  78                                 if center.y > item.top then
  79                                         children[0].add(item)
  80                                 else if center.y < item.bottom then
  81                                         children[1].add(item)
  82                                 else
  83                                         self.data.add(item)
  84                                 end
  85                         else if center.x < item.left then
  86                                 if center.y > item.top then
  87                                         children[3].add(item)
  88                                 else if center.y < item.bottom then
  89                                         children[2].add(item)
  90                                 else
  91                                         self.data.add(item)
  92                                 end
  93                         else if center.y > item.top then
  94                                 self.data.add(item)
  95                         else if center.y < item.bottom then
  96                                 self.data.add(item)
  97                         else
  98                                 self.data.add(item)
  99                         end
 100                 end
 101         end
 102
 103         redef fun is_empty
 104         do
 105                 if is_leaf then return data.is_empty
 106
 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
 109         end
 110
 111         # Return whether or not the Node is a leaf of the tree
 112         fun is_leaf: Bool do return children.is_empty
 113
 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)
 118         #     dquadtree.add(p1)
 119         #     dquadtree.add(p2)
 120         #     dquadtree.add(p3)
 121         #     var result = dquadtree.items_overlapping(p3)
 122         #     assert result.length == 1
 123         #     result.clear
 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])
 130         do
 131                 if self.is_leaf and data.length >= item_limit then
 132                         subdivide
 133                         var data_copy = data
 134                         data = new Array[E]
 135                         #add to the right Node
 136                         for d in data_copy do
 137                                 add_to_children(d)
 138                         end
 139                 end
 140                 for i in data do if i.intersects(region) then mdata.add(i)
 141
 142                 if children.not_empty then
 143                         var center = center
 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)
 150                                 else
 151                                         children[0].items_overlapping_in(region,mdata)
 152                                         children[1].items_overlapping_in(region, mdata)
 153                                 end
 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)
 159                                 else
 160                                         children[3].items_overlapping_in(region, mdata)
 161                                         children[2].items_overlapping_in(region, mdata)
 162                                 end
 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)
 169                         else
 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)
 174                         end
 175                 end
 176         end
 177
 178         # Create children nodes, depends on the concrete implementation
 179         protected fun subdivide is abstract
 180
 181         redef fun iterator
 182         do
 183                 if is_leaf then return data.iterator
 184
 185                 assert children.length >= 4
 186                 return data.iterator + children[0].iterator + children[1].iterator + children[2].iterator + children[3].iterator
 187         end
 188 end
 189
 190 # A dynamic implementation of the quadtree data structure
 191 #
 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]]
 195         super QuadTree[E]
 196
 197         redef fun subdivide
 198         do
 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)
 204         end
 205
 206         # Average X coordinate of the items in this node
 207         fun average_x: Numeric
 208         do
 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)
 212                 end
 213                 return x_total/x_total.value_of(self.data.length)
 214         end
 215
 216         # Average Y coordinate of the items in this node
 217         fun average_y: Numeric
 218         do
 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)
 222                 end
 223                 return y_total/y_total.value_of(self.data.length)
 224         end
 225 end
 226
 227 # Static implementation of the quadtree structure
 228 #
 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]]
 234         super QuadTree[E]
 235
 236         # Width of this node of the QuadTree
 237         var width: Numeric
 238
 239         # Height of this node of the QuadTree
 240         var height: Numeric
 241
 242         init
 243         do
 244                 center = new Point[Numeric](width.div(2), height.div(2))
 245         end
 246
 247         # Create a child node to `parent`
 248         init with_parent(l: Int, c: Point[Numeric], w, h: Numeric, parent: QuadTree[E])
 249         do
 250                 init(l, w, h)
 251                 center = c
 252                 self.parent_node = parent
 253         end
 254
 255         redef fun subdivide
 256         do
 257                 var center = center
 258                 assert center != null
 259
 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)
 264         end
 265
 266         redef fun to_s
 267         do
 268                 var s = "center : {center or else "null"}\n"
 269                 for d in data do s += d.to_s
 270
 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"
 276                 end
 277                 return s
 278         end
 279 end