Cluster

The origin of this library is in GoCluster

Guys did amazing job

This fork is better implementation with few additional features.

- Method to obtain expansion zoom
- Google maps example
- Better (refactored) implementation

Please look at godocs here.

Cluster is a very fast Golang library for geospatial point clustering.

This image is demo of JS library, this will work faster, because Golang is faster :-)

The cluster use hierarchical greedy clustering approach. The same approach used by Dave Leaver with his fantastic Leaflet.markercluster plugin.

So this approach is extremely fast, the only drawback is that all clustered points are stored in memory

This library is deeply inspired by MapBox's superclaster JS library and blog post: https://www.mapbox.com/blog/supercluster/

Very easy to use:

// 1.Convert slice of your objects to slice of GeoPoint (interface) objects
geoPoints := make([]GeoPoint, len(points))
for i := range points {
  geoPoints[i] = points[i]
}
// 2.Create new cluster (this will build index)
c, _ := cluster.New(geoPoints, cluster.WithinZoom(0, 21))

// 3.Get tour tile with mercator coordinate projections to display directly on the map
result := c.GetTile(0,0,0)
// or get all clusters for zoom 10
results := c.AllClusters(10) 

Library has only one dependency, it's KD-tree geospatial index

All ids of Point that you have as result are the index of initial array of Geopoint, so you could get you point by this index.

Init cluster index

To init index, you need to prepare your data. All your points should implement GeoPoint interface:

type GeoPoint interface {
	GetCoordinates() GeoCoordinates
}

type GeoCoordinates struct {
	Lng float64
	Lat float64
}

You could tweak the Cluster:

parameter	default value	description
MinZoom	0	Minimum zoom level at which clusters are generated
MaxZoom	16	Minimum zoom level at which clusters are generated
PointSize	40	Cluster radius, in pixels
TileSize	512	Tile extent. Radius is calculated relative to this value
NodeSize	64	NodeSize is size of the KD-tree node. Higher means faster indexing but slower search, and vise versa.

Available option functions:

	WithPointSize(size int) Option 
	WithTileSize(size int) Option
	WithinZoom(min, max int) Option
	WithNodeSize(size int) Option

	// creating new cluster
	New(points []GeoPoint, opts ...Option) (*Cluster, error)

Search point in boundary box

To search all points inside the box, that are limited by the box, formed by north-west point and east-south points. You need to provide Z index as well.

northWest := simplePoint{71.36718750000001, -83.79204408779539}
southEast := simplePoint{-71.01562500000001, 83.7539108491127}
zoom := 2
var results := c.GetClusters(northWest, southEast, zoom)

Returns the array of 'ClusterPoint' for zoom level. Each point has following coordinates:

• X coordinate of returned object is Longitude and
• Y coordinate of returned object is Latitude
• if the object is cluster of points (NumPoints > 1), the ID is generated started from ClusterIdxSeed (ID>ClusterIdxSeed)
• if the object represents only one point, it's id is the index of initial GeoPoints array

Search points for tile

OSM and Google maps uses tiles system to optimize map loading. So you could get all points for the tile with tileX, tileY and zoom:

c := NewCluster(geoPoints)
tileX := 0
tileY := 1
zoom := 4
results := c.GetTile(tileX, tileY, zoom)

In this case all coordinates are returned in pixels for that tile. If you want to return objects with Lat, Lng, use GetTileWithLatLng method.

TODO: Benchmarks