spatial - v1.0.0

spatial/octree

Octree spatial partitioning data structure.

An octree divides 3D space into 8 octants recursively, enabling efficient spatial queries for nearby objects.

Types

Octree

opaque </>

Octree node for spatial partitioning.

Divides 3D space into 8 octants recursively for efficient queries.

pub opaque type Octree(a)

Values

bounds

</> 
pub fn bounds(tree: Octree(a)) -> collider.Collider

Get the bounds of the octree.

count

</> 
pub fn count(tree: Octree(a)) -> Int

Count total items in the octree.

Time Complexity: O(n) where n is the total number of items.

insert

</> 
pub fn insert(
  tree: Octree(a),
  position: vec3.Vec3(Float),
  item: a,
) -> Octree(a)

Insert an item at a position into the octree.

Time Complexity: O(h + c) where h is the tree height (typically O(log n)) and c is the node capacity when subdivision occurs. Average case O(log n).

new

</> 
pub fn new(bounds: collider.Collider, capacity: Int) -> Octree(a)

Create a new empty octree.

Parameters

  • bounds: The spatial region this octree covers (must be a Box)
  • capacity: Maximum items per node before subdividing (typically 8-16)

Example

let bounds = collider.box(
  min: vec3.Vec3(-100.0, -100.0, -100.0),
  max: vec3.Vec3(100.0, 100.0, 100.0),
)
let tree = octree.new(bounds, capacity: 8)

query

</> 
pub fn query(
  tree: Octree(a),
  query_bounds: collider.Collider,
) -> List(#(vec3.Vec3(Float), a))

Query all items within a collider region.

Time Complexity: O(log n + k) average case where k is the number of results. Worst case O(n) if query region covers entire tree.

query_all

</> 
pub fn query_all(tree: Octree(a)) -> List(#(vec3.Vec3(Float), a))

Query all items in the octree (useful for iteration).

Time Complexity: O(n) where n is the total number of items.

query_radius

</> 
pub fn query_radius(
  tree: Octree(a),
  center: vec3.Vec3(Float),
  radius: Float,
) -> List(#(vec3.Vec3(Float), a))

Query all items within a radius of a point.

Time Complexity: O(log n + k) average case where k is the number of results.

remove

</> 
pub fn remove(
  tree: Octree(a),
  position: vec3.Vec3(Float),
  predicate: fn(a) -> Bool,
) -> Octree(a)

Remove an item from the octree.

Removes the first occurrence of an item at the given position.

Time Complexity: O(n) worst case as it recursively checks all nodes, but typically O(h) where h is the tree height for sparse trees.

✨ Search Document