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) ¶
package main
import (
"fmt"
"log"
"math"
"github.com/ArkaGPL/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
}
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) Max ¶
func (h *Heap) Max() ComparableDist
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 ¶
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 ¶
Tree implements a vantage point tree creation and nearest neighbor search.
Example ¶
package main
import (
"fmt"
"log"
"github.com/ArkaGPL/gonum/spatial/vptree"
)
func main() {
// 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 ¶
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 ¶
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 ¶
package main
import (
"fmt"
"log"
"github.com/ArkaGPL/gonum/spatial/vptree"
)
func main() {
// 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
})
}
Output: [2 3] [4 7] [5 4]
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