data

Documentation

Index

• func Canberra(a, b []float64) float64
• func Chebyshev(a, b []float64) float64
• func Euclidean(a, b []float64) float64
• func EuclideanSq(a, b []float64) float64
• func Manhattan(a, b []float64) float64
• type DistanceMetric
• type Interface
• type KDTree
  • func NewKDTree(dimensions int) *KDTree
  • func (t *KDTree) Build(items []Interface)
  • func (t *KDTree) Dimensions() int
  • func (t *KDTree) Items() []Interface
  • func (t *KDTree) Len() int
  • func (t *KDTree) NearestNeighbor(dist DistanceMetric, point ...float64) Interface
  • func (t *KDTree) NearestNeighbors(dist DistanceMetric, k int, point ...float64) []Interface
  • func (t *KDTree) QueryPoint(item Interface) bool
  • func (t *KDTree) QueryRange(ranges [][2]float64) []Interface
• type SpacialTree

Functions

func Canberra

func Canberra(a, b []float64) float64

Canberra is a DistanceMetric func which computes the canberra distance: Sum( |b-a| / |b|+|a| )

func Chebyshev

func Chebyshev(a, b []float64) float64

Chebyshev is a DistanceMetric func which computes the chebyshev distance, where the distance is the single most significant of the components.

func Euclidean

func Euclidean(a, b []float64) float64

Euclidean is the same as EuclideanSq() but takes the square root.

func EuclideanSq

func EuclideanSq(a, b []float64) float64

EuclideanSq is a DistanceMetric func which computes the euclidean/cartesian/geometric distance. It actually returns the sum of squares, without taking the square root.

func Manhattan

func Manhattan(a, b []float64) float64

Manhattan is a DistanceMetric func which computes the manhattan/taxi cab/snake distance.

Types

type DistanceMetric

type DistanceMetric func([]float64, []float64) float64

DistanceMetric is a type of function that calculates the distance between 2 n-dimensional points. Both arguments to the function should be equal length.

type Interface

type Interface interface {
	// get the n-dimensional location of an item
	Location() []float64
}

Interface defines methods required for type wishing to use SpacialTree.

type KDTree

type KDTree struct {
	// contains filtered or unexported fields
}

KDTree implements SpacialTree using the kd-tree data structure.

func NewKDTree

func NewKDTree(dimensions int) *KDTree

NewKDTree creates an empty tree with the capacity to hold the number of dimensions specified.

func (*KDTree) Build

func (t *KDTree) Build(items []Interface)

Build will build (or rebuild) the tree with the given items.

func (*KDTree) Dimensions

func (t *KDTree) Dimensions() int

Dimensions returns the number of dimensions the tree uses.

func (*KDTree) Items

func (t *KDTree) Items() []Interface

Items returns a slice of the items held in the tree.

func (*KDTree) Len

func (t *KDTree) Len() int

Len returns the number of items in the tree.

func (*KDTree) NearestNeighbor

func (t *KDTree) NearestNeighbor(dist DistanceMetric, point ...float64) Interface

NearestNeighbor finds the nearest neighbor to searchPt using the given distance metric. Returns nil if none found or if the tree's root is nil.

func (*KDTree) NearestNeighbors

func (t *KDTree) NearestNeighbors(dist DistanceMetric, k int, point ...float64) []Interface

NearestNeighbors returns the nearest [0,k] neighbors to the search point. If fewer than k are found, the returned slice will be as long as the number found. Distance is determined by the given DistanceMetric.

func (*KDTree) QueryPoint

func (t *KDTree) QueryPoint(item Interface) bool

QueryPoint returns true if the item is found in the tree.

func (*KDTree) QueryRange

func (t *KDTree) QueryRange(ranges [][2]float64) []Interface

QueryRange returns all items within the n-dimensional range specified. Each entry to 'ranges' is a [2]float64 where [0] = MIN and [1] = MAX of range.

type SpacialTree

type SpacialTree interface {
	// get the number of dimensions used in the tree
	Dimensions() int
	// get the total number of items in the tree
	Len() int
	// get a list of items in the tree
	Items() []Interface
	// build tree from item(s)
	Build(items []Interface)
	// check if item is in the tree, based on its location
	QueryPoint(item Interface) bool
	// get all items within the region defined by the list of mins/maxs
	QueryRange(ranges [][2]float64) []Interface
	// get the 1 nearest neighbor
	NearestNeighbor(dist DistanceMetric, point ...float64) Interface
	// get the k nearest neighbors. may return fewer than k
	NearestNeighbors(dist DistanceMetric, k int, point ...float64) []Interface
}

SpacialTree defines the interface for use in n-dimension space partitoning trees, such as k-d trees and quad/oct-trees.