Back to godoc.org

Package vptree

v0.7.0
Latest Go to latest
Published: Feb 26, 2020 | License: BSD-3-Clause | Module: gonum.org/v1/gonum

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)

Code:

// Copyright ©2019 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package vptree_test

import (
	"fmt"
	"log"
	"math"

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

func Example_accessiblePublicTransport() {
	// 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))
	}

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

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

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

Package Files

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

Code:

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

Code:

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, 0, nil)
if err != nil {
	log.Fatal(err)
}
q := vptree.Point{3, 5}
t.Do(func(c vptree.Comparable, _ int) (done bool) {

	if q.Distance(c) <= 3 {
		fmt.Println(c)
	}
	return
})
[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.

Documentation was rendered with GOOS=linux and GOARCH=amd64.

Jump to identifier

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to identifier