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

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

- Constants
- func DistanceSpherical(p1, p2 *Point) float64
- func DistanceSphericalFast(p1, p2 *Point) float64
- func FastCos(x float64) float64
- func FastSine(x float64) float64
- func Inside(innerMin, innerMax, outerMin, outerMax *Point) bool
- func RegionQuery(points PointList, P *Point, eps float64) []int
- type Cluster
- func DBScan(points PointList, eps float64, minPoints int) (clusters []Cluster, noise []int)
- func (c *Cluster) CentroidAndBounds(points PointList) (center, min, max Point)
- type EpsFunction
- type KDTree
- func NewKDTree(points PointList) *KDTree
- func (tree *KDTree) Height() int
- func (tree *KDTree) InRange(pt Point, dist float64, nodes []int) []int
- func (tree *KDTree) Insert(point Point)
- type Point
- type PointList
- type T

dbscan.go distance.go kdtree.go point.go

❖

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

DistanceSpherical is a spherical (optimized) distance between two points

Result is distance in kilometers

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

FastCos calculates cosinus from sinus

FastSine caclulates sinus approximated to parabola

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

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

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

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

Cluster is a result of DBScan work

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)

CentroidAndBounds calculates center and cluster bounds

EpsFunction is a function that returns eps based on point pt

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

Nodes (T) hold only indices into Points slice

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

Height returns the height of the K-D tree.

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.

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.

Point is longitue, latittude

GreaterEq - a >= b

LessEq - a <= b

PointList is a slice of Points

❖

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.