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.

Introduced properties

init defaultinit(item_limit: Int, width: Numeric, height: Numeric)

geometry :: SQuadTree :: defaultinit

fun height: Numeric

geometry :: SQuadTree :: height

Height of this node of the QuadTree

protected fun height=(height: Numeric)

geometry :: SQuadTree :: height=

Height of this node of the QuadTree

fun width: Numeric

geometry :: SQuadTree :: width

Width of this node of the QuadTree

protected fun width=(width: Numeric)

geometry :: SQuadTree :: width=

Width of this node of the QuadTree

init with_parent(l: Int, c: Point[Numeric], w: Numeric, h: Numeric, parent: QuadTree[E])

geometry :: SQuadTree :: with_parent

Create a child node to parent

Redefined properties

redef type SELF: SQuadTree[E]

geometry $ SQuadTree :: SELF

Type of this instance, automatically specialized in every class

redef init init

geometry $ SQuadTree :: init

redef fun subdivide

geometry $ SQuadTree :: subdivide

Create children nodes, depends on the concrete implementation

redef fun to_s: String

geometry $ SQuadTree :: to_s

User readable representation of self.

All properties

fun !=(other: nullable Object): Bool

core :: Object :: !=

Have self and other different values?

fun ==(other: nullable Object): Bool

core :: Object :: ==

Have self and other the same value?

type CLASS: Class[SELF]

core :: Object :: CLASS

The type of the class of self.

type CONCURRENT: ConcurrentCollection[E]

core :: Collection :: CONCURRENT

Type of the concurrent variant of this collection

type SELF: Object

core :: Object :: SELF

Type of this instance, automatically specialized in every class

protected fun accept_json_serializer(v: JsonSerializer)

serialization :: Serializable :: accept_json_serializer

Refinable service to customize the serialization of this class to JSON

protected fun accept_msgpack_attribute_counter(v: AttributeCounter)

serialization :: Serializable :: accept_msgpack_attribute_counter

Hook to customize the behavior of the AttributeCounter

protected fun accept_msgpack_serializer(v: MsgPackSerializer)

serialization :: Serializable :: accept_msgpack_serializer

Hook to customize the serialization of this class to MessagePack

abstract fun add(item: E)

core :: SimpleCollection :: add

Add item to this collection.

fun add_all(coll: Collection[E])

core :: SimpleCollection :: add_all

Add each item of coll.

protected fun add_to_bundle(bundle: NativeBundle, key: JavaString)

serialization :: Serializable :: add_to_bundle

Called by []= to dynamically choose the appropriate method according

fun as_random: Queue[E]

core :: SimpleCollection :: as_random

Return a random proxy queue where result.take is random.

protected fun center: nullable Point[Numeric]

geometry :: QuadTree :: center

Center coordinate of the children

protected fun center=(center: nullable Point[Numeric])

geometry :: QuadTree :: center=

Center coordinate of the children

protected fun children: Array[QuadTree[E]]

geometry :: QuadTree :: children

Children nodes, if not is_leaf

protected fun children=(children: Array[QuadTree[E]])

geometry :: QuadTree :: children=

Children nodes, if not is_leaf

protected fun class_factory(name: String): CLASS

core :: Object :: class_factory

Implementation used by get_class to create the specific class.

fun class_name: String

core :: Object :: class_name

The class name of the object.

abstract fun clear

core :: RemovableCollection :: clear

Remove all items

fun combinations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations

All r-length combinations on self (in same order) without repeated elements.

fun combinations_with_replacement(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations_with_replacement

All r-length combination on self (in same order) with repeated elements.

fun core_serialize_to(serializer: Serializer)

serialization :: Serializable :: core_serialize_to

Actual serialization of self to serializer

fun count(item: nullable Object): Int

core :: Collection :: count

How many occurrences of item are in the collection?

protected fun data: Array[E]

geometry :: QuadTree :: data

Items in this node

protected fun data=(data: Array[E])

geometry :: QuadTree :: data=

Items in this node

Return the first item of the collection

init from_deserializer(deserializer: Deserializer)

serialization :: Serializable :: from_deserializer

Create an instance of this class from the deserializer

fun get_class: CLASS

core :: Object :: get_class

The meta-object representing the dynamic type of self.

fun has(item: nullable Object): Bool

core :: Collection :: has

Is item in the collection ?

fun has_all(other: Collection[nullable Object]): Bool

core :: Collection :: has_all

Does the collection contain at least each element of other?

fun has_any(other: Collection[nullable Object]): Bool

core :: Collection :: has_any

Does the collection contain at least one element of other?

fun has_exactly(other: Collection[nullable Object]): Bool

core :: Collection :: has_exactly

Does the collection contain exactly all the elements of other?

fun has_only(item: nullable Object): Bool

core :: Collection :: has_only

Is the collection contain only item?

fun hash: Int

core :: Object :: hash

The hash code of the object.

fun height: Numeric

geometry :: SQuadTree :: height

Height of this node of the QuadTree

protected fun height=(height: Numeric)

geometry :: SQuadTree :: height=

Height of this node of the QuadTree

init init

core :: Object :: init

fun inspect: String

core :: Object :: inspect

Developer readable representation of self.

protected fun inspect_head: String

core :: Object :: inspect_head

Return "CLASSNAME:#OBJECTID".

fun is_empty: Bool

core :: Collection :: is_empty

Is there no item in the collection?

fun is_leaf: Bool

geometry :: QuadTree :: is_leaf

Return whether or not the Node is a leaf of the tree

intern fun is_same_instance(other: nullable Object): Bool

core :: Object :: is_same_instance

Return true if self and other are the same instance (i.e. same identity).

fun is_same_serialized(other: nullable Object): Bool

core :: Object :: is_same_serialized

Is self the same as other in a serialization context?

intern fun is_same_type(other: Object): Bool

core :: Object :: is_same_type

Return true if self and other have the same dynamic type.

protected fun item_limit: Int

geometry :: QuadTree :: item_limit

Maximum number of items in this node before subdividing

protected fun item_limit=(item_limit: Int)

geometry :: QuadTree :: item_limit=

Maximum number of items in this node before subdividing

abstract fun items_overlapping(region: Boxed[Numeric]): SimpleCollection[E]

geometry :: BoxedCollection :: items_overlapping

returns all the items overlapping with region

abstract fun iterator: Iterator[E]

core :: Collection :: iterator

Get a new iterator on the collection.

fun join(separator: nullable Text, last_separator: nullable Text): String

core :: Collection :: join

Concatenate and separate each elements with separator.

fun length: Int

core :: Collection :: length

Number of items in the collection.

protected fun msgpack_extra_array_items: Int

serialization :: Serializable :: msgpack_extra_array_items

Hook to request a larger than usual metadata array

fun not_empty: Bool

core :: Collection :: not_empty

Alias for not is_empty.

intern fun object_id: Int

core :: Object :: object_id

An internal hash code for the object based on its identity.

fun output

core :: Object :: output

Display self on stdout (debug only).

intern fun output_class_name

core :: Object :: output_class_name

Display class name on stdout (debug only).

protected fun parent_node: nullable QuadTree[E]

geometry :: QuadTree :: parent_node

Parent node in the tree

protected fun parent_node=(parent_node: nullable QuadTree[E])

geometry :: QuadTree :: parent_node=

Parent node in the tree

fun permutations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: permutations

All r-length permutations on self (all possible ordering) without repeated elements.

fun plain_to_s: String

core :: Collection :: plain_to_s

Concatenate elements without separators

fun product(r: Int): Collection[SequenceRead[E]]

core :: Collection :: product

Cartesian product, over r times self.

fun rand: E

core :: Collection :: rand

Return a random element form the collection

abstract fun remove(item: nullable Object)

core :: RemovableCollection :: remove

Remove an occurrence of item

fun remove_all(item: nullable Object)

core :: RemovableCollection :: remove_all

Remove all occurrences of item

fun sample(length: Int): Array[E]

core :: Collection :: sample

Return a new array made of (at most) length elements randomly chosen.

fun serialization_hash: Int

core :: Object :: serialization_hash

Hash value use for serialization

fun serialize_msgpack(plain: nullable Bool): Bytes

serialization :: Serializable :: serialize_msgpack

Serialize self to MessagePack bytes

fun serialize_to(serializer: Serializer)

serialization :: Serializable :: serialize_to

Serialize self to serializer

fun serialize_to_json(plain: nullable Bool, pretty: nullable Bool): String

serialization :: Serializable :: serialize_to_json

Serialize self to JSON

protected abstract fun subdivide

geometry :: QuadTree :: subdivide

Create children nodes, depends on the concrete implementation

intern fun sys: Sys

core :: Object :: sys

Return the global sys object, the only instance of the Sys class.

fun to_a: Array[E]

core :: Collection :: to_a

Build a new array from a collection

abstract fun to_concurrent: CONCURRENT

core :: Collection :: to_concurrent

Wraps self in a thread-safe collection

fun to_counter: Counter[E]

core :: Collection :: to_counter

Create and fill up a counter with the elements of `self.

fun to_curlslist: CURLSList

core :: Collection :: to_curlslist

Convert Collection[String] to CURLSList

fun to_json: String

serialization :: Serializable :: to_json

Serialize self to plain JSON

abstract fun to_jvalue(env: JniEnv): JValue

core :: Object :: to_jvalue

fun to_pretty_json: String

serialization :: Serializable :: to_pretty_json

Serialize self to plain pretty JSON

fun to_s: String

core :: Object :: to_s

User readable representation of self.

fun to_shuffle: Array[E]

core :: Collection :: to_shuffle

Return a new array made of elements in a random order.

fun width: Numeric

geometry :: SQuadTree :: width

Width of this node of the QuadTree

protected fun width=(width: Numeric)

geometry :: SQuadTree :: width=

Width of this node of the QuadTree

init with_parent(l: Int, c: Point[Numeric], w: Numeric, h: Numeric, parent: QuadTree[E])

geometry :: SQuadTree :: with_parent

Create a child node to parent

init with_parent(limit: Int, parent: QuadTree[E])

geometry :: QuadTree :: with_parent

Create a child node to parent

Ancestors

interface BoxedCollection[E: Boxed[Numeric]]

geometry :: BoxedCollection

Base for all data structures containing multiple Boxed Objects

interface Collection[E: nullable Object]

core :: Collection

The root of the collection hierarchy.

interface Object

core :: Object

The root of the class hierarchy.

interface RemovableCollection[E: nullable Object]

core :: RemovableCollection

Items can be removed from this collection

interface Serializable

serialization :: Serializable

Instances of this class can be passed to Serializer::serialize

interface SimpleCollection[E: nullable Object]

core :: SimpleCollection

Items can be added to these collections.

Parents

abstract class QuadTree[E: Boxed[Numeric]]

geometry :: QuadTree

Abstract QuadTree implementing the basic functions and data

Class definitions

geometry $ SQuadTree

# 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:227,1--279,3

class SQuadTree[E: Boxed[Numeric]]

Summary

Static implementation of the quadtree structure

Introduced properties

defaultinit

height

height=

width

width=

with_parent

Redefined properties

SELF

init

subdivide

to_s

Static implementation of the quadtree structure

Introduced properties

init defaultinit(item_limit: Int, width: Numeric, height: Numeric)

fun height: Numeric

protected fun height=(height: Numeric)

fun width: Numeric

protected fun width=(width: Numeric)

init with_parent(l: Int, c: Point[Numeric], w: Numeric, h: Numeric, parent: QuadTree[E])

Redefined properties

redef type SELF: SQuadTree[E]

redef init init

redef fun subdivide

redef fun to_s: String

Summary

All properties

!=

==

CLASS

CONCURRENT

SELF

accept_json_serializer

accept_msgpack_attribute_counter

accept_msgpack_serializer

add

add_all

add_to_bundle

as_random

center

center=

children

children=

class_factory

class_name

clear

combinations

combinations_with_replacement

core_serialize_to

count

data

data=

defaultinit

defaultinit

defaultinit

defaultinit

defaultinit

defaultinit

defaultinit

defaultinit

first

from_deserializer

get_class

has

has_all

has_any

has_exactly

has_only

hash

height

height=

init

inspect

inspect_head

is_empty

is_leaf

is_same_instance