dbscan

Documentation

Overview

Package dbscan clusters incoming points into clusters with params (eps, minPoints).

Index

• Constants
• func DBScan(points clusters.PointList, eps float64, minPoints int) (clusterArray []clusters.Cluster, noise []int)
• func DistanceSpherical(p1, p2 space.Point) float64
• func DistanceSphericalFast(p1, p2 space.Point) float64
• func FastCos(x float64) float64
• func FastSine(x float64) float64
• func RegionQuery(points clusters.PointList, P space.Point, eps float64) []int
• type EpsFunction
• type KDTree
  • func NewKDTree(points clusters.PointList) *KDTree
  • func (tree *KDTree) Height() int
  • func (tree *KDTree) InRange(pt space.Point, dist float64, nodes []int) []int
  • func (tree *KDTree) Insert(point space.Point)
• type T

Constants

const (
	// DegreeRad is coefficient to translate from degrees to radians
	DegreeRad = math.Pi / 180.0
	// EarthR is earth radius in km
	EarthR = 6371.0
)

const ...

Functions

func DBScan

func DBScan(points clusters.PointList, eps float64, minPoints int) (clusterArray []clusters.Cluster, noise []int)

DBScan clusters incoming points into clusters with params (eps, minPoints)

eps is clustering radius in km minPoints in minimum number of points in eps-neighborhood (density)

func DistanceSpherical

func DistanceSpherical(p1, p2 space.Point) float64

DistanceSpherical is a spherical (optimized) distance between two points

Result is distance in kilometers

func DistanceSphericalFast

func DistanceSphericalFast(p1, p2 space.Point) float64

DistanceSphericalFast calculates spherical distance with fast cosine without sqrt and normalization to Earth radius/radians

To get real distance in km, take sqrt and multiply result by EarthR*DegreeRad

In this library eps (distance) is adjusted so that we don't need to do sqrt and multiplication

func FastCos

func FastCos(x float64) float64

FastCos calculates cosines from sinus

func FastSine

func FastSine(x float64) float64

FastSine calculates sinus approximated to parabola

Taken from: http://forum.devmaster.net/t/fast-and-accurate-sine-cosine/9648

func RegionQuery

func RegionQuery(points clusters.PointList, P space.Point, eps float64) []int

RegionQuery is simple way O(N) to find points in neighborhood

It is roughly equivalent to kdTree.InRange(points[i], eps, nil)

Types

type EpsFunction

type EpsFunction func(pt space.Point) float64

EpsFunction is a function that returns eps based on point pt

type KDTree

type KDTree struct {
	Points clusters.PointList
	Root   *T
}

KDTree is implementation of K-D Tree, with Points separated from nodes.

Nodes (T) hold only indices into Points slice

func NewKDTree

func NewKDTree(points clusters.PointList) *KDTree

NewKDTree returns a new K-D tree built using the given nodes.

func (*KDTree) Height

func (tree *KDTree) Height() int

Height returns the height of the K-D tree.

func (*KDTree) InRange

func (tree *KDTree) InRange(pt space.Point, dist float64, nodes []int) []int

InRange appends all nodes in the K-D tree that are within a given distance from the given point to the given slice, which may be nil. To avoid allocation, the slice can be pre-allocated with a larger capacity and re-used across multiple calls to InRange.

func (*KDTree) Insert

func (tree *KDTree) Insert(point space.Point)

Insert returns a new K-D tree with the given node inserted. Inserting a node that is already a member of a K-D tree invalidates that tree.

type T

type T struct {
	// Point is the K-dimensional point associated with the
	// data of this node.
	PointID  int
	EqualIDs []int
	// contains filtered or unexported fields
}

A T is a the node of a K-D tree. A *T is the root of a K-D tree, and nil is an empty K-D tree.