QuadTree API mostly used for 2 dimensional collision detection

The QuadTree data structure partition a 2D space by recursively subdividing it into 4 regions when its capacity is reached. This module introduces 2 main implementation of the structure, a static and a dynamic QuadTree.

Introduced classes

class DQuadTree[E: Boxed[Numeric]]

geometry :: DQuadTree

A dynamic implementation of the quadtree data structure
abstract class QuadTree[E: Boxed[Numeric]]

geometry :: QuadTree

Abstract QuadTree implementing the basic functions and data
class SQuadTree[E: Boxed[Numeric]]

geometry :: SQuadTree

Static implementation of the quadtree structure

All class definitions

class DQuadTree[E: Boxed[Numeric]]

geometry $ DQuadTree

A dynamic implementation of the quadtree data structure
abstract class QuadTree[E: Boxed[Numeric]]

geometry $ QuadTree

Abstract QuadTree implementing the basic functions and data
class SQuadTree[E: Boxed[Numeric]]

geometry $ SQuadTree

Static implementation of the quadtree structure
package_diagram geometry::quadtree quadtree geometry::boxes boxes geometry::quadtree->geometry::boxes pipeline pipeline geometry::quadtree->pipeline geometry::points_and_lines points_and_lines geometry::boxes->geometry::points_and_lines core core pipeline->core ...geometry::points_and_lines ... ...geometry::points_and_lines->geometry::points_and_lines ...core ... ...core->core a_star-m a_star-m a_star-m->geometry::quadtree

Ancestors

module abstract_collection

core :: abstract_collection

Abstract collection classes and services.
module abstract_text

core :: abstract_text

Abstract class for manipulation of sequences of characters
module array

core :: array

This module introduces the standard array structure.
module bitset

core :: bitset

Services to handle BitSet
module bytes

core :: bytes

Services for byte streams and arrays
module caching

serialization :: caching

Services for caching serialization engines
module circular_array

core :: circular_array

Efficient data structure to access both end of the sequence.
module codec_base

core :: codec_base

Base for codecs to use with streams
module codecs

core :: codecs

Group module for all codec-related manipulations
module collection

core :: collection

This module define several collection classes.
module core

core :: core

Standard classes and methods used by default by Nit programs and libraries.
module engine_tools

serialization :: engine_tools

Advanced services for serialization engines
module environ

core :: environ

Access to the environment variables of the process
module error

core :: error

Standard error-management infrastructure.
module exec

core :: exec

Invocation and management of operating system sub-processes.
module file

core :: file

File manipulations (create, read, write, etc.)
module fixed_ints

core :: fixed_ints

Basic integers of fixed-precision
module fixed_ints_text

core :: fixed_ints_text

Text services to complement fixed_ints
module flat

core :: flat

All the array-based text representations
module gc

core :: gc

Access to the Nit internal garbage collection mechanism
module hash_collection

core :: hash_collection

Introduce HashMap and HashSet.
module inspect

serialization :: inspect

Refine Serializable::inspect to show more useful information
module iso8859_1

core :: iso8859_1

Codec for ISO8859-1 I/O
module kernel

core :: kernel

Most basic classes and methods.
module list

core :: list

This module handle double linked lists
module math

core :: math

Mathematical operations
module meta

meta :: meta

Simple user-defined meta-level to manipulate types of instances as object.
module native

core :: native

Native structures for text and bytes
module numeric

core :: numeric

Advanced services for Numeric types
module points_and_lines

geometry :: points_and_lines

Interfaces and classes to represent basic geometry needs.
module protocol

core :: protocol

module queue

core :: queue

Queuing data structures and wrappers
module range

core :: range

Module for range of discrete objects.
module re

core :: re

Regular expression support for all services based on Pattern
module ropes

core :: ropes

Tree-based representation of a String.
module serialization

serialization :: serialization

General serialization services
module serialization_core

serialization :: serialization_core

Abstract services to serialize Nit objects to different formats
module sorter

core :: sorter

This module contains classes used to compare things and sorts arrays.
module stream

core :: stream

Input and output streams of characters
module text

core :: text

All the classes and methods related to the manipulation of text entities
module time

core :: time

Management of time and dates
module union_find

core :: union_find

union–find algorithm using an efficient disjoint-set data structure
module utf8

core :: utf8

Codec for UTF-8 I/O

Parents

module boxes

geometry :: boxes

Provides interfaces and classes to represent basic geometry needs.
module pipeline

pipeline :: pipeline

Pipelined filters and operations on iterators.

Children

module a_star-m

a_star-m

# QuadTree API mostly used for 2 dimensional collision detection
#
# The QuadTree data structure partition a 2D space by recursively
# subdividing it into 4 regions when its capacity is reached.
# This module introduces 2 main implementation of the structure,
# a static and a dynamic QuadTree.
module quadtree

import boxes
import pipeline

# Abstract QuadTree implementing the basic functions and data
abstract class QuadTree[E: Boxed[Numeric]]
	super BoxedCollection[E]

	# Center coordinate of the children
	protected var center: nullable Point[Numeric] = null

	# Items in this node
	protected var data = new Array[E]

	# Children nodes, if not `is_leaf`
	#
	# ~~~raw
	# ________________
	# |       |       |
	# |   1   |   2   |
	# |-------|-------|
	# |   0   |   3   |
	# |_______|_______|
	# ~~~
	protected var children = new Array[QuadTree[E]]

	# Maximum number of items in this node before subdividing
	protected var item_limit: Int

	# Parent node in the tree
	protected var parent_node: nullable QuadTree[E] = null

	# Create a child node to `parent`
	init with_parent(limit: Int, parent: QuadTree[E])
	do
		init(limit)
		self.parent_node = parent
	end

	redef fun items_overlapping(region): SimpleCollection[E] do
		var res = new Array[E]
		items_overlapping_in(region,res)
		return res
	end

	# Add `item` to the tree, create children if `item_limit` is reached
	redef fun add(item) do if self.is_leaf then self.data.add(item) else add_to_children(item)

	private fun add_to_children(item: Boxed[Numeric])
	do
		if children.not_empty then
			var center = center
			assert center != null
			if center.x > item.right then
				if center.y > item.top then
					children[0].add(item)
				else if center.y < item.bottom then
					children[1].add(item)
				else
					self.data.add(item)
				end
			else if center.x < item.left then
				if center.y > item.top then
					children[3].add(item)
				else if center.y < item.bottom then
					children[2].add(item)
				else
					self.data.add(item)
				end
			else if center.y > item.top then
				self.data.add(item)
			else if center.y < item.bottom then
				self.data.add(item)
			else
				self.data.add(item)
			end
		end
	end

	redef fun is_empty
	do
		if is_leaf then return data.is_empty

		assert children.length >= 4
		return data.is_empty and children[0].is_empty and children[1].is_empty and children[2].is_empty and children[3].is_empty
	end

	# Return whether or not the Node is a leaf of the tree
	fun is_leaf: Bool do return children.is_empty

	#     var dquadtree = new DQuadTree[Point[Int]](2)
	#     var p1 = new Point[Int](0,0)
	#     var p2 = new Point[Int](0,9)
	#     var p3 = new Point[Int](9,0)
	#     dquadtree.add(p1)
	#     dquadtree.add(p2)
	#     dquadtree.add(p3)
	#     var result = dquadtree.items_overlapping(p3)
	#     assert result.length == 1
	#     result.clear
	#     var p4 = new Point[Int](9,9)
	#     result = dquadtree.items_overlapping(p4)
	#     assert result.length == 0
	#     result = dquadtree.items_overlapping(p4.padded(10))
	#     assert result.length == 3
	private fun items_overlapping_in(region: Boxed[Numeric], mdata: SimpleCollection[E])
	do
		if self.is_leaf and data.length >= item_limit then
			subdivide
			var data_copy = data
			data = new Array[E]
			#add to the right Node
			for d in data_copy do
				add_to_children(d)
			end
		end
		for i in data do if i.intersects(region) then mdata.add(i)

		if children.not_empty then
			var center = center
			assert center != null
			if center.x > region.right then
				if center.y > region.top then
					children[0].items_overlapping_in(region, mdata)
				else if center.y < region.bottom then
					children[1].items_overlapping_in(region, mdata)
				else
					children[0].items_overlapping_in(region,mdata)
					children[1].items_overlapping_in(region, mdata)
				end
			else if center.x < region.left then
				if center.y > region.top then
					children[3].items_overlapping_in(region, mdata)
				else if center.y < region.bottom then
					children[2].items_overlapping_in(region, mdata)
				else
					children[3].items_overlapping_in(region, mdata)
					children[2].items_overlapping_in(region, mdata)
				end
			else if center.y > region.top then
				children[0].items_overlapping_in(region, mdata)
				children[3].items_overlapping_in(region, mdata)
			else if center.y < region.bottom then
				children[1].items_overlapping_in(region, mdata)
				children[2].items_overlapping_in(region, mdata)
			else
				children[0].items_overlapping_in(region, mdata)
				children[1].items_overlapping_in(region, mdata)
				children[2].items_overlapping_in(region, mdata)
				children[3].items_overlapping_in(region, mdata)
			end
		end
	end

	# Create children nodes, depends on the concrete implementation
	protected fun subdivide is abstract

	redef fun iterator
	do
		if is_leaf then return data.iterator

		assert children.length >= 4
		return data.iterator + children[0].iterator + children[1].iterator + children[2].iterator + children[3].iterator
	end
end

# A dynamic implementation of the quadtree data structure
#
# The center of the parent node is determined by the average
# values of the data it contains when `item_limit` is reached.
class DQuadTree[E: Boxed[Numeric]]
	super QuadTree[E]

	redef fun subdivide
	do
		self.center = new Point[Numeric](average_x, average_y)
		children[0] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[1] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[2] = new DQuadTree[E].with_parent(self.item_limit, self)
		children[3] = new DQuadTree[E].with_parent(self.item_limit, self)
	end

	# Average X coordinate of the items in this node
	fun average_x: Numeric
	do
		var x_total = data.first.left.zero
		for data in self.data do
			x_total += (data.left + data.right)/x_total.value_of(2)
		end
		return x_total/x_total.value_of(self.data.length)
	end

	# Average Y coordinate of the items in this node
	fun average_y: Numeric
	do
		var y_total = data.first.left.zero
		for data in self.data do
			y_total += (data.left + data.right)/y_total.value_of(2)
		end
		return y_total/y_total.value_of(self.data.length)
	end
end

# Static implementation of the quadtree structure
#
# You need to specify a zone when creating the quadtree,
# which will be the zone corresponding to the root node.
# Each subdivision cut the space in 4 equal regions from
# the center of the parent node.
class SQuadTree[E: Boxed[Numeric]]
	super QuadTree[E]

	# Width of this node of the QuadTree
	var width: Numeric

	# Height of this node of the QuadTree
	var height: Numeric

	init
	do
		center = new Point[Numeric](width.div(2), height.div(2))
	end

	# Create a child node to `parent`
	init with_parent(l: Int, c: Point[Numeric], w, h: Numeric, parent: QuadTree[E])
	do
		init(l, w, h)
		center = c
		self.parent_node = parent
	end

	redef fun subdivide
	do
		var center = center
		assert center != null

		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)
		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)
		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)
		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)
	end

	redef fun to_s
	do
		var s = "center : {center or else "null"}\n"
		for d in data do s += d.to_s

		if children.not_empty then
			s += "\n   children[0]: {children[0]}\n"
			s += "   children[1]: {children[1]}\n"
			s += "   children[2]: {children[2]}\n"
			s += "   children[3]: {children[3]}\n"
		end
		return s
	end
end
lib/geometry/quadtree.nit:17,1--279,3