Skip to content

smira/go-point-clustering

Repository files navigation

Point Clustering

Build Status codecov GoDoc FOSSA Status

(Lat, lon) points fast clustering using DBScan algorithm in Go.

Given set of geo points, this library can find clusters according to specified params. There are several optimizations applied:

  • distance calculation is using "fast" implementations of sine/cosine, with sqrt being removed
  • to find points within eps distance k-d tree is being used
  • edge case handling of identical points being present in the set

Usage

Build list of points:

    points := cluster.PointList{{30.258387, 59.951557}, {30.434124, 60.029499}, ...}

Pick settings for DBScan algorithm:

  • eps is clustering radius (in kilometers)
  • minPoints is number of points in eps-radius of base point to consider it being part of the cluster

eps and minPoints together define minimum density of the cluster.

Run DBScan:

    clusters, noise := cluster.DBScan(points, 0.8, 10) // eps is 800m, 10 points minimum in eps-neighborhood

DBScan function returns list of clusters (each Cluster being reference to the list of source points) and list of point indexes which don't fit into any cluster (noise).

License

FOSSA Status