node

Documentation

Overview

Package node implements a K-D tree node.

Index

• func Data(n *N) []point.P
• type N
  • func New(data []point.P, depth int) *N
  • func (n *N) Axis() vector.D
  • func (n *N) Child(v vector.V) *N
  • func (n *N) Data() []point.P
  • func (n *N) Insert(p point.P)
  • func (n *N) L() *N
  • func (n *N) Leaf() bool
  • func (n *N) P() vector.V
  • func (n *N) R() *N
  • func (n *N) Remove(v vector.V, f func(p point.P) bool) bool

Functions

func Data

func Data(n *N) []point.P

Data returns the data in the node and descendents.

Types

type N

type N struct {
	// contains filtered or unexported fields
}

N represents a K-D tree node. Child nodes are sorted along the same axis, with coordinates in the left node preceeding right node coordinates (along the given axis).

func New

func New(data []point.P, depth int) *N

New returns a new K-D tree node instance.

func (*N) Axis

func (n *N) Axis() vector.D

Axis is the discriminant dimension for this tree node -- if the node is split on the X-axis, then all points with X-coordinates less than the node value will be in the left child (and vice versa for the right).

func (*N) Child

func (n *N) Child(v vector.V) *N

Child is the appropriately expanded child node given the input coordinates -- that is, this function wraps the normal branching pattern for e.g. search operations.

func (*N) Data

func (n *N) Data() []point.P

Data returns a list of data points stored in this specific node.

func (*N) Insert

func (n *N) Insert(p point.P)

Insert adds a data point into the node. The point may be stored in a descendent.

func (*N) L

func (n *N) L() *N

L is the meaningful left child node of the current node.

This function returns nil if the left subtree does not encapsulate data.

func (*N) Leaf

func (n *N) Leaf() bool

func (*N) P

func (n *N) P() vector.V

P is the point in the K-dimensional ambient space to which this node is embedded. All data in this node are located at the same spacial coordinate, within a small margin of error.

func (*N) R

func (n *N) R() *N

R is the meaningful right child node of the current node.

This function returns nil if the right subtree does not encapsulate data.

func (*N) Remove

func (n *N) Remove(v vector.V, f func(p point.P) bool) bool

Remove deletes a data point from the node or child nodes. A returned value of false indicates the given point was not found.

N.B.: Remove does not actually delete the underlying K-D tree node. Manually removing and shifting the nodes is a non-trivial task. We generally expect these trees to be relatively stable once created, and that insert and remove operations are kept at a minimum.