kdtree

Documentation

Overview

Package kdtree provides a generic kd-tree implementation.

Index

• Variables
• type Clipper
• type Interface
• type Node
  • func (n *Node) Axis() vecutil.Axis
  • func (n *Node) Indices() []int
  • func (n *Node) IsLeaf() bool
  • func (n *Node) Left() *Node
  • func (n *Node) Pivot() float64
  • func (n *Node) Right() *Node
• type Options
• type Tree
  • func New(data Interface, opts Options) *Tree
  • func (tree *Tree) Bound() bound.Bound
  • func (tree *Tree) Depth() int
  • func (tree *Tree) Root() *Node
  • func (tree *Tree) String() string

Variables

var DefaultOptions = Options{
	MaxDepth:       64,
	LeafSize:       2,
	FaultTolerance: 2,
	ClipThreshold:  32,
}

Reasonable build options

Types

type Clipper

type Clipper interface {
	Clip(i int, bound bound.Bound, axis vecutil.Axis, lower bool, oldData interface{}) (clipped bound.Bound, newData interface{})
}

type Interface

type Interface interface {
	Len() int
	Dimension(i int, axis vecutil.Axis) (min, max float64)
}

A type that implements kdtree.Interface can be partitioned.

type Node

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

Node represents nodes in a kd-tree, both interior and leaf.

func (*Node) Axis

func (n *Node) Axis() vecutil.Axis

func (*Node) Indices

func (n *Node) Indices() []int

func (*Node) IsLeaf

func (n *Node) IsLeaf() bool

func (*Node) Left

func (n *Node) Left() *Node

func (*Node) Pivot

func (n *Node) Pivot() float64

func (*Node) Right

func (n *Node) Right() *Node

type Options

type Options struct {
	MaxDepth       int // MaxDepth limits how many levels the tree can have
	LeafSize       int // LeafSize is the desired leaf size.  Some leaves may not obey this size.
	FaultTolerance int // FaultTolerance specifies the number of bad splits before a branch is considered a fault.
	ClipThreshold  int // ClipThreshold specifies the maximum number of values in a node to do primitive clipping.
}

Options allows you to tune the parameters of kd-tree construction.

type Tree

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

Tree is a generic kd-tree.

func New

func New(data Interface, opts Options) *Tree

New creates a new kd-tree by partitioning data.

func (*Tree) Bound

func (tree *Tree) Bound() bound.Bound

Bound returns a bounding box that encloses all objects in the tree.

func (*Tree) Depth

func (tree *Tree) Depth() int

Depth returns the number of levels in the tree (excluding leaves).

func (*Tree) Root

func (tree *Tree) Root() *Node

Root returns the root of the kd-tree.

func (*Tree) String

func (tree *Tree) String() string