Documentation

Overview

    Package vptree implements a vantage point tree. Vantage point trees provide an efficient search for nearest neighbors in a metric space.

    See http://pnylab.com/papers/vptree/vptree.pdf for details of vp-trees.

    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

    This section is empty.

    Types

    type Comparable

    type Comparable interface {
    	// Distance returns the distance between the receiver and the
    	// parameter. The returned distance must satisfy the properties
    	// of distances in a metric space.
    	//
    	// - a.Distance(a) == 0
    	// - a.Distance(b) >= 0
    	// - a.Distance(b) == b.Distance(a)
    	// - a.Distance(b) <= a.Distance(c)+c.Distance(b)
    	//
    	Distance(Comparable) float64
    }

      Comparable is the element interface for values stored in a vp-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 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 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 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. vantage point 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
                        	Radius  float64
                        	Closer  *Node
                        	Further *Node
                        }

                          Node holds a single point value in a vantage point tree.

                          type Operation

                          type Operation func(Comparable, 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 Point

                            type Point []float64

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

                              func (Point) Distance

                              func (p Point) Distance(c Comparable) float64

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

                                type Tree

                                type Tree struct {
                                	Root  *Node
                                	Count int
                                }

                                  Tree implements a vantage point tree creation and nearest neighbor search.

                                  Example
                                  Output:
                                  
                                  [9 6] is closest point to [8 7], d=1.414214
                                  

                                  func New

                                  func New(p []Comparable, effort int, src rand.Source) (t *Tree, err error)

                                    New returns a vantage point tree constructed from the values in p. The effort parameter specifies how much work should be put into optimizing the choice of vantage point. If effort is one or less, random vantage points are chosen. The order of elements in p will be altered after New returns. The src parameter provides the source of randomness for vantage point selection. If src is nil global rand package functions are used. Points in p must not be infinitely distant.

                                    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) 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.

                                            Source Files