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

package kdtree

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

Package kdtree implements a k-d tree.

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

Code:

package main

import (
    "fmt"
    "math"

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

func main() {
    // Construct a k-d tree of train station locations
    // to identify accessible public transport for the
    // elderly.
    t := kdtree.New(stations, false)

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

    var keep kdtree.Keeper

    // Find all stations within 0.75 of the residence.
    keep = kdtree.NewDistKeeper(0.75 * 0.75) // Distances are squared.
    t.NearestSet(keep, q)

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

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

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

}

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

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

// Compare satisfies the axis comparisons method of the kdtree.Comparable interface.
// The dimensions are:
//  0 = lat
//  1 = lon
func (p place) Compare(c kdtree.Comparable, d kdtree.Dim) float64 {
    q := c.(place)
    switch d {
    case 0:
        return p.lat - q.lat
    case 1:
        return p.lon - q.lon
    default:
        panic("illegal dimension")
    }
}

// Dims returns the number of dimensions to be considered.
func (p place) Dims() int { return 2 }

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

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

// places is a collection of the place type that satisfies kdtree.Interface.
type places []place

func (p places) Index(i int) kdtree.Comparable         { return p[i] }
func (p places) Len() int                              { return len(p) }
func (p places) Pivot(d kdtree.Dim) int                { return plane{places: p, Dim: d}.Pivot() }
func (p places) Slice(start, end int) kdtree.Interface { return p[start:end] }

// plane is required to help places.
type plane struct {
    kdtree.Dim
    places
}

func (p plane) Less(i, j int) bool {
    switch p.Dim {
    case 0:
        return p.places[i].lat < p.places[j].lat
    case 1:
        return p.places[i].lon < p.places[j].lon
    default:
        panic("illegal dimension")
    }
}
func (p plane) Pivot() int { return kdtree.Partition(p, kdtree.MedianOfMedians(p)) }
func (p plane) Slice(start, end int) kdtree.SortSlicer {
    p.places = p.places[start:end]
    return p
}
func (p plane) Swap(i, j int) {
    p.places[i], p.places[j] = p.places[j], p.places[i]
}

Index

Examples

Package Files

doc.go kdtree.go medians.go points.go

func MedianOfMedians Uses

func MedianOfMedians(list SortSlicer) int

MedianOfMedians returns the index to the median value of the medians of groups of 5 consecutive elements.

func MedianOfRandoms Uses

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 Uses

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 Uses

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.

type Bounder Uses

type Bounder interface {
    Bounds() *Bounding
}

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

type Bounding Uses

type Bounding struct {
    Min, Max Comparable
}

Bounding represents a volume bounding box.

func (*Bounding) Contains Uses

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 Uses

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 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 Dim Uses

type Dim int

Dim is an index into a point's coordinates.

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 Extender Uses

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 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 Interface Uses

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 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. kd 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
    Plane       Dim
    Left, Right *Node
    *Bounding
}

Node holds a single point value in a k-d tree.

func (*Node) String Uses

func (n *Node) String() string

type Operation Uses

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 Uses

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 Uses

func (p Plane) Less(i, j int) bool

func (Plane) Pivot Uses

func (p Plane) Pivot() int

func (Plane) Slice Uses

func (p Plane) Slice(start, end int) SortSlicer

func (Plane) Swap Uses

func (p Plane) Swap(i, j int)

type Point Uses

type Point []float64

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

func (Point) Compare Uses

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 Uses

func (p Point) Dims() int

Dims returns the number of dimensions described by the receiver.

func (Point) Distance Uses

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 Uses

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

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

type Points Uses

type Points []Point

Points is a collection of point values that satisfies the Interface.

func (Points) Bounds Uses

func (p Points) Bounds() *Bounding

func (Points) Index Uses

func (p Points) Index(i int) Comparable

func (Points) Len Uses

func (p Points) Len() int

func (Points) Pivot Uses

func (p Points) Pivot(d Dim) int

func (Points) Slice Uses

func (p Points) Slice(start, end int) Interface

type SortSlicer Uses

type SortSlicer interface {
    sort.Interface
    Slice(start, end int) SortSlicer
}

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

type Tree Uses

type Tree struct {
    Root  *Node
    Count int
}

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

Code:

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

t := kdtree.New(points, false)
q := kdtree.Point{8, 7}
p, d := t.Nearest(q)
fmt.Printf("%v is closest point to %v, d=%f\n", p, q, math.Sqrt(d))

Output:

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

Code:

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

t := kdtree.New(points, true)
fmt.Printf("Bounding box of points is %+v\n", t.Root.Bounding)

Output:

Bounding box of points is &{Min:[2 1] Max:[9 7]}

func New Uses

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 Uses

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 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 := kdtree.Points{{2, 3}, {5, 4}, {9, 6}, {4, 7}, {8, 1}, {7, 2}}

// Print all points in the data set within 3 of (3, 5).
t := kdtree.New(points, false)
q := kdtree.Point{3, 5}
t.Do(func(c kdtree.Comparable, _ *kdtree.Bounding, _ int) (done bool) {
    // Compare each distance and output points
    // with a Euclidean distance less than 3.
    // Distance returns the square of the
    // Euclidean distance between points.
    if q.Distance(c) <= 3*3 {
        fmt.Println(c)
    }
    return
})
// Unordered output:
// [2 3]
// [4 7]
// [5 4]

Output:

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

func (*Tree) DoBounded Uses

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.

Code:

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

// Find all points within the bounding box ((3, 3), (6, 8))
// and print them with their bounding boxes and tree depth.
t := kdtree.New(points, true) // Construct tree with bounding boxes.
b := &kdtree.Bounding{
    Min: kdtree.Point{3, 3},
    Max: kdtree.Point{6, 8},
}
t.DoBounded(b, func(c kdtree.Comparable, bound *kdtree.Bounding, depth int) (done bool) {
    fmt.Printf("p=%v bound=%+v depth=%d\n", c, bound, depth)
    return
})

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 Uses

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 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 kdtree imports 5 packages (graph) and is imported by 1 packages. Updated 2019-09-08. Refresh now. Tools for package owners.