gonum: gonum.org/v1/gonum/spatial/vptree Index | Examples | Files

package vptree

import "gonum.org/v1/gonum/spatial/vptree"

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.

Code:

package main

import (
    "fmt"
    "log"
    "math"

    "gonum.org/v1/gonum/spatial/vptree"
)

func main() {
    // Construct a vp tree of train station locations
    // to identify accessible public transport for the
    // elderly.
    t, err := vptree.New(stations, 5, nil)
    if err != nil {
        log.Fatal(err)
    }

    // Residence.
    q := place{lat: 51.501476, lon: -0.140634}

    var keep vptree.Keeper

    // Find all stations within 0.75 of the residence.
    keep = vptree.NewDistKeeper(0.75)
    t.NearestSet(keep, q)

    fmt.Println(`Stations within 750 m of 51.501476N 0.140634W.`)
    for _, c := range keep.(*vptree.DistKeeper).Heap {
        p := c.Comparable.(place)
        fmt.Printf("%s: %0.3f km\n", p.name, p.Distance(q))
    }
    fmt.Println()

    // Find the five closest stations to the residence.
    keep = vptree.NewNKeeper(5)
    t.NearestSet(keep, q)

    fmt.Println(`5 closest stations to 51.501476N 0.140634W.`)
    for _, c := range keep.(*vptree.NKeeper).Heap {
        p := c.Comparable.(place)
        fmt.Printf("%s: %0.3f km\n", p.name, p.Distance(q))
    }

}

// stations is a list of railways stations.
var stations = []vptree.Comparable{
    place{name: "Bond Street", lat: 51.5142, lon: -0.1494},
    place{name: "Charing Cross", lat: 51.508, lon: -0.1247},
    place{name: "Covent Garden", lat: 51.5129, lon: -0.1243},
    place{name: "Embankment", lat: 51.5074, lon: -0.1223},
    place{name: "Green Park", lat: 51.5067, lon: -0.1428},
    place{name: "Hyde Park Corner", lat: 51.5027, lon: -0.1527},
    place{name: "Leicester Square", lat: 51.5113, lon: -0.1281},
    place{name: "Marble Arch", lat: 51.5136, lon: -0.1586},
    place{name: "Oxford Circus", lat: 51.515, lon: -0.1415},
    place{name: "Picadilly Circus", lat: 51.5098, lon: -0.1342},
    place{name: "Pimlico", lat: 51.4893, lon: -0.1334},
    place{name: "Sloane Square", lat: 51.4924, lon: -0.1565},
    place{name: "South Kensington", lat: 51.4941, lon: -0.1738},
    place{name: "St. James's Park", lat: 51.4994, lon: -0.1335},
    place{name: "Temple", lat: 51.5111, lon: -0.1141},
    place{name: "Tottenham Court Road", lat: 51.5165, lon: -0.131},
    place{name: "Vauxhall", lat: 51.4861, lon: -0.1253},
    place{name: "Victoria", lat: 51.4965, lon: -0.1447},
    place{name: "Waterloo", lat: 51.5036, lon: -0.1143},
    place{name: "Westminster", lat: 51.501, lon: -0.1254},
}

// place is a vptree.Comparable implementations.
type place struct {
    name     string
    lat, lon float64
}

// Distance returns the distance between the receiver and c.
func (p place) Distance(c vptree.Comparable) float64 {
    q := c.(place)
    return haversine(p.lat, p.lon, q.lat, q.lon)
}

// haversine returns the distance between two geographic coordinates.
func haversine(lat1, lon1, lat2, lon2 float64) float64 {
    const r = 6371 // km
    sdLat := math.Sin(radians(lat2-lat1) / 2)
    sdLon := math.Sin(radians(lon2-lon1) / 2)
    a := sdLat*sdLat + math.Cos(radians(lat1))*math.Cos(radians(lat2))*sdLon*sdLon
    d := 2 * r * math.Asin(math.Sqrt(a))
    return d // km
}

func radians(d float64) float64 {
    return d * math.Pi / 180
}

Index

Examples

Package Files

doc.go vptree.go

type Comparable Uses

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 Uses

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 Uses

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 Uses

func NewDistKeeper(d float64) *DistKeeper

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

func (*DistKeeper) Keep Uses

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 Uses

type Heap []ComparableDist

Heap is a max heap sorted on Dist.

func (*Heap) Len Uses

func (h *Heap) Len() int

func (*Heap) Less Uses

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

func (*Heap) Max Uses

func (h *Heap) Max() ComparableDist

func (*Heap) Pop Uses

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

func (*Heap) Push Uses

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

func (*Heap) Swap Uses

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

type Keeper Uses

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 Uses

type NKeeper struct {
    Heap
}

NKeeper is a Keeper that retains the n best ComparableDists that have been passed to Keep.

func NewNKeeper Uses

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 Uses

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 Uses

type Node struct {
    Point   Comparable
    Radius  float64
    Closer  *Node
    Further *Node
}

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

type Operation Uses

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 Uses

type Point []float64

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

func (Point) Distance Uses

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 Uses

type Tree struct {
    Root  *Node
    Count int
}

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

Code:

// Example data from https://en.wikipedia.org/wiki/K-d_tree
points := []vptree.Comparable{
    vptree.Point{2, 3},
    vptree.Point{5, 4},
    vptree.Point{9, 6},
    vptree.Point{4, 7},
    vptree.Point{8, 1},
    vptree.Point{7, 2},
}

t, err := vptree.New(points, 3, nil)
if err != nil {
    log.Fatal(err)
}
q := vptree.Point{8, 7}
p, d := t.Nearest(q)
fmt.Printf("%v is closest point to %v, d=%f\n", p, q, d)

Output:

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

func New Uses

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 Uses

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.

Code:

// Example data from https://en.wikipedia.org/wiki/K-d_tree
points := []vptree.Comparable{
    vptree.Point{2, 3},
    vptree.Point{5, 4},
    vptree.Point{9, 6},
    vptree.Point{4, 7},
    vptree.Point{8, 1},
    vptree.Point{7, 2},
}

// Print all points in the data set within 3 of (3, 5).
t, err := vptree.New(points, 0, nil)
if err != nil {
    log.Fatal(err)
}
q := vptree.Point{3, 5}
t.Do(func(c vptree.Comparable, _ int) (done bool) {
    // Compare each distance and output points
    // with a Euclidean distance less than or
    // equal to 3. Distance returns the
    // Euclidean distance between points.
    if q.Distance(c) <= 3 {
        fmt.Println(c)
    }
    return
})
// Unordered output:
// [2 3]
// [4 7]
// [5 4]

Output:

[2 3]
[4 7]
[5 4]

func (*Tree) Len Uses

func (t *Tree) Len() int

Len returns the number of elements in the tree.

func (*Tree) Nearest Uses

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

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

func (*Tree) NearestSet Uses

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.

Package vptree imports 6 packages (graph) and is imported by 1 packages. Updated 2019-06-29. Refresh now. Tools for package owners.