Documentation

Overview

    Package kdtree implements a k-d tree.

    See https://en.wikipedia.org/wiki/K-d_tree for more details of k-d tree functionality.

    Example (AccessiblePublicTransport)
    Output:
    
    
    Stations within 750 m of 51.501476N 0.140634W.
    St. James's Park: 0.545 km
    Green Park: 0.600 km
    Victoria: 0.621 km
    
    5 closest stations to 51.501476N 0.140634W.
    St. James's Park: 0.545 km
    Green Park: 0.600 km
    Victoria: 0.621 km
    Hyde Park Corner: 0.846 km
    Picadilly Circus: 1.027 km
    

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    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 element are 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
            }

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

              type Bounding

              type Bounding struct {
              	Min, Max Comparable
              }

                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 signed distance of a from the plane passing through
                  	// b and perpendicular to the dimension d.
                  	//
                  	// 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
                  }

                    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

                        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 maximum 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
                              }

                                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 using zero-based half
                                  	// open indexing equivalent to built-in slice indexing.
                                  	Slice(start, end int) Interface
                                  }

                                    Interface is the set of methods required for construction of efficiently searchable k-d trees. A k-d tree may be constructed without using the Interface type, but it is likely to have reduced search performance.

                                    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 have been passed 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 adds 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
                                            }

                                              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)

                                                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
                                                }

                                                  Plane is a wrapping type that allows a Points type be pivoted on a dimension. The Pivot method of Plane uses MedianOfRandoms sampling at most 100 elements to find a pivot element.

                                                  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

                                                    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

                                                      Compare returns the signed distance of p from the plane passing through c and perpendicular to the dimension d. The concrete type of c must be Point.

                                                      func (Point) Dims

                                                      func (p Point) Dims() int

                                                        Dims returns the number of dimensions described by the receiver.

                                                        func (Point) Distance

                                                        func (p Point) Distance(c Comparable) float64

                                                          Distance returns the squared Euclidean distance between c and the receiver. The concrete type of c must be Point.

                                                          func (Point) Extend

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

                                                            Extend returns a bounding box that has been extended to include the receiver.

                                                            type Points

                                                            type Points []Point

                                                              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
                                                              }

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

                                                                type Tree

                                                                type Tree struct {
                                                                	Root  *Node
                                                                	Count int
                                                                }

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

                                                                  Example
                                                                  Output:
                                                                  
                                                                  [9 6] is closest point to [8 7], d=1.414214
                                                                  
                                                                  Example (Bounds)
                                                                  Output:
                                                                  
                                                                  Bounding box of points is &{Min:[2 1] Max:[9 7]}
                                                                  

                                                                  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. The ordering of elements in p may be altered after New returns.

                                                                    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.

                                                                        Example
                                                                        Output:
                                                                        
                                                                        [2 3]
                                                                        [4 7]
                                                                        [5 4]
                                                                        

                                                                        func (*Tree) DoBounded

                                                                        func (t *Tree) DoBounded(b *Bounding, fn Operation) 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.

                                                                          Example
                                                                          Output:
                                                                          
                                                                          p=[5 4] bound=&{Min:[2 3] Max:[5 7]} depth=1
                                                                          p=[4 7] bound=&{Min:[4 7] Max:[4 7]} depth=2
                                                                          

                                                                          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. If a sentinel ComparableDist with a nil Comparable is used by the Keeper to mark the maximum distance, NearestSet will remove it before returning.