kdtree

package
v2.1.5+incompatible Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 5, 2019 License: Apache-2.0 Imports: 5 Imported by: 0

Documentation

Overview

Package kdtree implements a k-d tree.

Index

Constants

This section is empty.

Variables

View Source
var Randoms = 100

Randoms is the maximum number of random values to sample for calculation of median of random elements.

Functions

func MedianOfMedians

func MedianOfMedians(list SortSlicer) int

MedianOfMedians returns the index to the median value of the medians of groups of 5 consecutive elements.

func MedianOfRandoms

func MedianOfRandoms(list SortSlicer, n int) int

MedianOfRandoms returns the index to the median value of up to n randomly chosen elements in list.

func Partition

func Partition(list sort.Interface, pivot int) int

Partition partitions list such that all elements less than the value at pivot prior to the call are placed before that element and all elements greater than that value are placed after it. The final location of the element at pivot prior to the call is returned.

func Select

func Select(list SortSlicer, k int) int

Select partitions list such that all elements less than the kth largest element are placed placed before k in the resulting list and all elements greater than it are placed after the position k.

Types

type Bounder

type Bounder interface {
	Bounds() *Bounding
}

An Bounder returns a bounding volume containing the list of points. Bounds may return nil.

type Bounding

type Bounding [2]Comparable

A Bounding represents a volume bounding box.

func (*Bounding) Contains

func (b *Bounding) Contains(c Comparable) bool

Contains returns whether c is within the volume of the Bounding. A nil Bounding returns true.

type Comparable

type Comparable interface {
	// Compare returns the shortest translation of the plane through b with
	// normal vector along dimension d to the parallel plane through a.
	//
	// Given c = a.Compare(b, d):
	//  c = a_d - b_d
	//
	Compare(Comparable, Dim) float64

	// Dims returns the number of dimensions described in the Comparable.
	Dims() int

	// Distance returns the squared Euclidean distance between the receiver and
	// the parameter.
	Distance(Comparable) float64
}

A Comparable is the element interface for values stored in a k-d tree.

type ComparableDist

type ComparableDist struct {
	Comparable Comparable
	Dist       float64
}

ComparableDist holds a Comparable and a distance to a specific query. A nil Comparable is used to mark the end of the heap, so clients should not store nil values except for this purpose.

type Dim

type Dim int

A Dim is an index into a point's coordinates.

type DistKeeper

type DistKeeper struct {
	Heap
}

DistKeeper is a Keeper that retains the ComparableDists within the specified distance of the query that it is called to Keep.

func NewDistKeeper

func NewDistKeeper(d float64) *DistKeeper

NewDistKeeper returns an DistKeeper with the max value of the heap set to d.

func (*DistKeeper) Keep

func (k *DistKeeper) Keep(c ComparableDist)

Keep adds c to the heap if its distance is less than or equal to the max value of the heap.

type Extender

type Extender interface {
	Comparable

	// Extend returns a bounding box that has been extended to include the
	// receiver. Extend may return nil.
	Extend(*Bounding) *Bounding
}

An Extender is a Comparable that can increase a bounding volume to include the point represented by the Comparable.

type Heap

type Heap []ComparableDist

Heap is a max heap sorted on Dist.

func (*Heap) Len

func (h *Heap) Len() int

func (*Heap) Less

func (h *Heap) Less(i, j int) bool

func (*Heap) Max

func (h *Heap) Max() ComparableDist

func (*Heap) Pop

func (h *Heap) Pop() (i interface{})

func (*Heap) Push

func (h *Heap) Push(x interface{})

func (*Heap) Swap

func (h *Heap) Swap(i, j int)

type Interface

type Interface interface {
	// Index returns the ith element of the list of points.
	Index(i int) Comparable

	// Len returns the length of the list.
	Len() int

	// Pivot partitions the list based on the dimension specified.
	Pivot(Dim) int

	// Slice returns a slice of the list.
	Slice(start, end int) Interface
}

type Keeper

type Keeper interface {
	Keep(ComparableDist) // Keep conditionally pushes the provided ComparableDist onto the heap.
	Max() ComparableDist // Max returns the maximum element of the Keeper.
	heap.Interface
}

Keeper implements a conditional max heap sorted on the Dist field of the ComparableDist type. kd search is guided by the distance stored in the max value of the heap.

type NKeeper

type NKeeper struct {
	Heap
}

NKeeper is a Keeper that retains the n best ComparableDists that it is called to Keep.

func NewNKeeper

func NewNKeeper(n int) *NKeeper

NewNKeeper returns an NKeeper with the max value of the heap set to infinite distance. The returned NKeeper is able to retain at most n values.

func (*NKeeper) Keep

func (k *NKeeper) Keep(c ComparableDist)

Keep add c to the heap if its distance is less than the maximum value of the heap. If adding c would increase the size of the heap beyond the initial maximum length, the maximum value of the heap is dropped.

type Node

type Node struct {
	Point       Comparable
	Plane       Dim
	Left, Right *Node
	*Bounding
}

A Node holds a single point value in a k-d tree.

func (*Node) String

func (n *Node) String() string

type Operation

type Operation func(Comparable, *Bounding, int) (done bool)

An Operation is a function that operates on a Comparable. The bounding volume and tree depth of the point is also provided. If done is returned true, the Operation is indicating that no further work needs to be done and so the Do function should traverse no further.

type Plane

type Plane struct {
	Dim
	Points
}

A Plane is a wrapping type that allows a Points type be pivoted on a dimension.

func (Plane) Less

func (p Plane) Less(i, j int) bool

func (Plane) Pivot

func (p Plane) Pivot() int

func (Plane) Slice

func (p Plane) Slice(start, end int) SortSlicer

func (Plane) Swap

func (p Plane) Swap(i, j int)

type Point

type Point []float64

A Point represents a point in a k-d space that satisfies the Comparable interface.

func (Point) Compare

func (p Point) Compare(c Comparable, d Dim) float64

func (Point) Dims

func (p Point) Dims() int

func (Point) Distance

func (p Point) Distance(c Comparable) float64

func (Point) Extend

func (p Point) Extend(b *Bounding) *Bounding

type Points

type Points []Point

A Points is a collection of point values that satisfies the Interface.

func (Points) Bounds

func (p Points) Bounds() *Bounding

func (Points) Index

func (p Points) Index(i int) Comparable

func (Points) Len

func (p Points) Len() int

func (Points) Pivot

func (p Points) Pivot(d Dim) int

func (Points) Slice

func (p Points) Slice(start, end int) Interface

type SortSlicer

type SortSlicer interface {
	sort.Interface
	Slice(start, end int) SortSlicer
}

A SortSlicer satisfies the sort.Interface and is able to slice itself.

type Tree

type Tree struct {
	Root  *Node
	Count int
}

A Tree implements a k-d tree creation and nearest neighbour search.

func New

func New(p Interface, bounding bool) *Tree

New returns a k-d tree constructed from the values in p. If p is a Bounder and bounding is true, bounds are determined for each node.

func (*Tree) Contains

func (t *Tree) Contains(c Comparable) bool

Contains returns whether a Comparable is in the bounds of the tree. If no bounding has been constructed Contains returns true.

func (*Tree) Do

func (t *Tree) Do(fn Operation) bool

Do performs fn on all values stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

func (*Tree) DoBounded

func (t *Tree) DoBounded(fn Operation, b *Bounding) bool

DoBounded performs fn on all values stored in the tree that are within the specified bound. If b is nil, the result is the same as a Do. A boolean is returned indicating whether the DoBounded traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships future tree operation behaviors are undefined.

func (*Tree) Insert

func (t *Tree) Insert(c Comparable, bounding bool)

Insert adds a point to the tree, updating the bounding volumes if bounding is true, and the tree is empty or the tree already has bounding volumes stored, and c is an Extender. No rebalancing of the tree is performed.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of elements in the tree.

func (*Tree) Nearest

func (t *Tree) Nearest(q Comparable) (Comparable, float64)

Nearest returns the nearest value to the query and the distance between them.

func (*Tree) NearestSet

func (t *Tree) NearestSet(k Keeper, q Comparable)

NearestSet finds the nearest values to the query accepted by the provided Keeper, k. k must be able to return a ComparableDist specifying the maximum acceptable distance when Max() is called, and retains the results of the search in min sorted order after the call to NearestSet returns.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL