Import std.collections.spatial

std.collections.spatial

Spatial hashes, quadtrees, and octrees, which find values by where they are.

SpatialHash<T>, QuadTree<T>, and Octree<T>: values at points, found by where they are, the ones in a box or near a point, without going over the others. A SpatialHash keeps the points in square cells of a size, for things spread over a world of any size; a QuadTree splits its bounds in four where points crowd, and an Octree, in 3D, in eight. A box holds the points on its edges, a point near another is no more than the radius from it, so a negative or NaN radius finds nothing and an infinite one finds everything, and what's found comes in no order to count on. A coordinate that's NaN panics. Distances and boxes are worked out in Doubles, so no Float overflows on the way.

std/collections/spatial.fb

Types

`SpatialHash` class

@DebugElements Public Class SpatialHash<T> Implements Iterable<T>, Cloneable

Values at 2D points, kept in square cells of a size, for things spread over a world of any size.

Examples

Local places = SpatialHash<String>(10)
places.Add("near", 3, 4)
places.Add("far", 100, 100)
Expect(places.Near(0, 0, 5) == ["near"])
Expect(places.Query(90, 90, 110, 110) == ["far"])

std/collections/spatial.fb, line 116

@PanicsAtCaller Public New(size: Float) constructor #

An empty SpatialHash whose cells are size across, which has to be above 0 and finite.
Public Property Count: Int property #

How many values it holds.
@PanicsAtCaller Public Method Add(value: T, x: Float, y: Float) method #

Adds the value at (x, y).
@PanicsAtCaller Public Method Remove(value: T, x: Float, y: Float): Bool method #

Removes the first value equal to value at (x, y), and tells whether there was one.
@PanicsAtCaller Public Method Contains(value: T, x: Float, y: Float): Bool method #

Whether a value equal to value is at (x, y).
@PanicsAtCaller Public Method Move(value: T, x: Float, y: Float, toX: Float, toY: Float): Bool method #

Moves the first value equal to value at (x, y) to (toX, toY), and tells whether there was one.
Public Method Clear() method #

Takes every value out.
@PanicsAtCaller Public Method Query(minX: Float, minY: Float, maxX: Float, maxY: Float): T[] method #

The values in the box from (minX, minY) to (maxX, maxY), in a new array.
@PanicsAtCaller Public Method Near(x: Float, y: Float, radius: Float): T[] method #

The values no more than radius from (x, y), in a new array.
Public Method ToArray(): T[] method #

Every value, in a new array.
Public Method Clone(): SpatialHash<T> method #

A new SpatialHash with the same cells and values at the same points.
Public Method Iterate(): SpatialIterator<T> method #

Every value. Adding or removing one while going over them panics.

`SpatialIterator` struct

Public Struct SpatialIterator<T> Implements Iterator<T>

The values of a SpatialHash, a QuadTree, or an Octree, as they were when the loop began, which a For loop goes over.

std/collections/spatial.fb, line 295

@PanicsAtCaller Public ByRef Method Next(): T? method #

The next value, in no order to count on, or Null after the last. Panics when the collection changed since the loop began.

`QuadTree` class

@DebugElements Public Class QuadTree<T> Implements Iterable<T>, Cloneable

Values at 2D points, in bounds it splits in four where points crowd.

Examples

Local tree = QuadTree<Int>(0, 0, 100, 100)
tree.Add(1, 10, 10)
tree.Add(2, 20, 20)
tree.Add(3, 60, 60)
Expect(tree.Query(0, 0, 25, 25).Count == 2)
Expect(tree.Move(1, 10, 10, 90, 5))
Expect(tree.Query(0, 0, 25, 25) == [2])

std/collections/spatial.fb, line 561

@PanicsAtCaller Public New(minX: Float, minY: Float, maxX: Float, maxY: Float) constructor #

An empty QuadTree for the points in the box from (minX, minY) to (maxX, maxY), which has to be finite. A box whose max is below its min along an axis panics.
Public Property Count: Int property #

How many values it holds.
@PanicsAtCaller Public Method Add(value: T, x: Float, y: Float) method #

Adds the value at (x, y). A point outside the QuadTree's box panics.
@PanicsAtCaller Public Method Remove(value: T, x: Float, y: Float): Bool method #

Removes the first value equal to value at (x, y), and tells whether there was one.
@PanicsAtCaller Public Method Contains(value: T, x: Float, y: Float): Bool method #

Whether a value equal to value is at (x, y).
@PanicsAtCaller Public Method Move(value: T, x: Float, y: Float, toX: Float, toY: Float): Bool method #

Moves the first value equal to value at (x, y) to (toX, toY), and tells whether there was one. A point outside the QuadTree's box panics.
Public Method Clear() method #

Takes every value out.
@PanicsAtCaller Public Method Query(minX: Float, minY: Float, maxX: Float, maxY: Float): T[] method #

The values in the box from (minX, minY) to (maxX, maxY), in a new array.
@PanicsAtCaller Public Method Near(x: Float, y: Float, radius: Float): T[] method #

The values no more than radius from (x, y), in a new array.
Public Method ToArray(): T[] method #

Every value, in a new array.
Public Method Clone(): QuadTree<T> method #

A new QuadTree with the same box and values at the same points.
Public Method Iterate(): SpatialIterator<T> method #

Every value. Adding or removing one while going over them panics.

`Octree` class

@DebugElements Public Class Octree<T> Implements Iterable<T>, Cloneable

Values at 3D points, in bounds it splits in eight where points crowd.

Examples

Local tree = Octree<String>(0, 0, 0, 100, 100, 100)
tree.Add("a", 10, 10, 10)
tree.Add("b", 90, 90, 90)
Expect(tree.Near(0, 0, 0, 20) == ["a"])
Expect(tree.Count == 2)

std/collections/spatial.fb, line 650

@PanicsAtCaller Public New(minX: Float, minY: Float, minZ: Float, maxX: Float, maxY: Float, maxZ: Float) constructor #

An empty Octree for the points in the box from (minX, minY, minZ) to (maxX, maxY, maxZ), which has to be finite. A box whose max is below its min along an axis panics.
Public Property Count: Int property #

How many values it holds.
@PanicsAtCaller Public Method Add(value: T, x: Float, y: Float, z: Float) method #

Adds the value at (x, y, z). A point outside the Octree's box panics.
@PanicsAtCaller Public Method Remove(value: T, x: Float, y: Float, z: Float): Bool method #

Removes the first value equal to value at (x, y, z), and tells whether there was one.
@PanicsAtCaller Public Method Contains(value: T, x: Float, y: Float, z: Float): Bool method #

Whether a value equal to value is at (x, y, z).
@PanicsAtCaller Public Method Move(value: T, x: Float, y: Float, z: Float, toX: Float, toY: Float, toZ: Float): Bool method #

Moves the first value equal to value at (x, y, z) to (toX, toY, toZ), and tells whether there was one. A point outside the Octree's box panics.
Public Method Clear() method #

Takes every value out.
@PanicsAtCaller Public Method Query(minX: Float, minY: Float, minZ: Float, maxX: Float, maxY: Float, maxZ: Float): T[] method #

The values in the box from (minX, minY, minZ) to (maxX, maxY, maxZ), in a new array.
@PanicsAtCaller Public Method Near(x: Float, y: Float, z: Float, radius: Float): T[] method #

The values no more than radius from (x, y, z), in a new array.
Public Method ToArray(): T[] method #

Every value, in a new array.
Public Method Clone(): Octree<T> method #

A new Octree with the same box and values at the same points.
Public Method Iterate(): SpatialIterator<T> method #

Every value. Adding or removing one while going over them panics.

Report an issue with this page or with FutureBlitz on GitHub.

std.collections.spatial

Types

SpatialHash class

Examples

SpatialIterator struct

QuadTree class

Examples

Octree class

Examples

`SpatialHash` class

`SpatialIterator` struct

`QuadTree` class

`Octree` class