go-point-clustering: github.com/smira/go-point-clustering Index | Files

package cluster

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

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


Package Files

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

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

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

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 [2]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.