go-point-clustering: github.com/smira/go-point-clustering

package cluster

import "github.com/smira/go-point-clustering"

Package cluster implements DBScan clustering on (lat, lon) using K-D Tree

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
)

func DistanceSpherical¶Uses

func DistanceSpherical(p1, p2 *Point) float64

DistanceSpherical is a spherical (optimized) distance between two points

Result is distance in kilometers

func DistanceSphericalFast¶Uses

func DistanceSphericalFast(p1, p2 *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¶Uses

func FastCos(x float64) float64

FastCos calculates cosinus from sinus

func FastSine¶Uses

func FastSine(x float64) float64

FastSine caclulates sinus approximated to parabola

func Inside¶Uses

func Inside(innerMin, innerMax, outerMin, outerMax *Point) bool

Inside checks if (innerMin, innerMax) rectangle is inside (outerMin, outMax) rectangle

func RegionQuery¶Uses

func RegionQuery(points PointList, P *Point, eps float64) []int

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

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

type Cluster¶Uses

type Cluster struct {
C      int
Points []int
}

Cluster is a result of DBScan work

func DBScan¶Uses

func DBScan(points PointList, eps float64, minPoints int) (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-neighbourhood (density)

func (*Cluster) CentroidAndBounds¶Uses

func (c *Cluster) CentroidAndBounds(points PointList) (center, min, max Point)

CentroidAndBounds calculates center and cluster bounds

type EpsFunction¶Uses

type EpsFunction func(pt Point) float64

EpsFunction is a function that returns eps based on point pt

type KDTree¶Uses

type KDTree struct {
Points 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¶Uses

func NewKDTree(points PointList) *KDTree

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

func (*KDTree) Height¶Uses

func (tree *KDTree) Height() int

Height returns the height of the K-D tree.

func (*KDTree) InRange¶Uses

func (tree *KDTree) InRange(pt 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¶Uses

func (tree *KDTree) Insert(point 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 Point¶Uses

type Point float64

Point is longitue, latittude

func (*Point) GreaterEq¶Uses

func (a *Point) GreaterEq(b *Point) bool

GreaterEq - a >= b

func (*Point) LessEq¶Uses

func (a *Point) LessEq(b *Point) bool

LessEq - a <= b

type PointList¶Uses

type PointList []Point

PointList is a slice of Points

type T¶Uses

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.

Package cluster imports 3 packages (graph) and is imported by 1 packages. Updated 2019-07-06. Refresh now. Tools for package owners.