1// Copyright ©2019 The Gonum Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package kdtree 6 7import "math" 8 9var ( 10 _ Interface = Points(nil) 11 _ Comparable = Point(nil) 12) 13 14// Point represents a point in a k-d space that satisfies the Comparable interface. 15type Point []float64 16 17// Compare returns the signed distance of p from the plane passing through c and 18// perpendicular to the dimension d. The concrete type of c must be Point. 19func (p Point) Compare(c Comparable, d Dim) float64 { q := c.(Point); return p[d] - q[d] } 20 21// Dims returns the number of dimensions described by the receiver. 22func (p Point) Dims() int { return len(p) } 23 24// Distance returns the squared Euclidean distance between c and the receiver. The 25// concrete type of c must be Point. 26func (p Point) Distance(c Comparable) float64 { 27 q := c.(Point) 28 var sum float64 29 for dim, c := range p { 30 d := c - q[dim] 31 sum += d * d 32 } 33 return sum 34} 35 36// Extend returns a bounding box that has been extended to include the receiver. 37func (p Point) Extend(b *Bounding) *Bounding { 38 if b == nil { 39 b = &Bounding{append(Point(nil), p...), append(Point(nil), p...)} 40 } 41 min := b.Min.(Point) 42 max := b.Max.(Point) 43 for d, v := range p { 44 min[d] = math.Min(min[d], v) 45 max[d] = math.Max(max[d], v) 46 } 47 *b = Bounding{Min: min, Max: max} 48 return b 49} 50 51// Points is a collection of point values that satisfies the Interface. 52type Points []Point 53 54func (p Points) Bounds() *Bounding { 55 if p.Len() == 0 { 56 return nil 57 } 58 min := append(Point(nil), p[0]...) 59 max := append(Point(nil), p[0]...) 60 for _, e := range p[1:] { 61 for d, v := range e { 62 min[d] = math.Min(min[d], v) 63 max[d] = math.Max(max[d], v) 64 } 65 } 66 return &Bounding{Min: min, Max: max} 67} 68func (p Points) Index(i int) Comparable { return p[i] } 69func (p Points) Len() int { return len(p) } 70func (p Points) Pivot(d Dim) int { return Plane{Points: p, Dim: d}.Pivot() } 71func (p Points) Slice(start, end int) Interface { return p[start:end] } 72 73// Plane is a wrapping type that allows a Points type be pivoted on a dimension. 74// The Pivot method of Plane uses MedianOfRandoms sampling at most 100 elements 75// to find a pivot element. 76type Plane struct { 77 Dim 78 Points 79} 80 81// randoms is the maximum number of random values to sample for calculation of 82// median of random elements. 83const randoms = 100 84 85func (p Plane) Less(i, j int) bool { return p.Points[i][p.Dim] < p.Points[j][p.Dim] } 86func (p Plane) Pivot() int { return Partition(p, MedianOfRandoms(p, randoms)) } 87func (p Plane) Slice(start, end int) SortSlicer { p.Points = p.Points[start:end]; return p } 88func (p Plane) Swap(i, j int) { p.Points[i], p.Points[j] = p.Points[j], p.Points[i] } 89