cluster

package module
v0.0.0-...-138b67e Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 4, 2018 License: MIT Imports: 2 Imported by: 0

README

Gocluster

Please look at godocs here.

Gocluster 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 :-)

TODO: implement goserver example

clusters2

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.Create new cluster
c := NewCluster()
//2.Convert slice of your objects to slice of GeoPoint (interface) objects
geoPoints := make([]GeoPoint, len(points))
for i := range points {
  geoPoints[i] = points[i]
}
//3.Build index
c.ClusterPoints(geoPoints)
//3.Get tour tile with mercator coordinate projections to display directly on the map
result := c.GetTile(0,0,0)

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

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

Clusters of points are have autoincrement generated ids, started at ClusterIdxSeed.

ClusterIdxSeed is the next power of length of input array. For example, if input slice of points length is 78, ClusterIdxSeed == 100, if input slice of points length is 991, ClusterIdxSeed == 1000 etc

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 {
	Lon 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 Minimum zoom level at which clusters are generated
MaxZoom 16 NodeSize is size of the KD-tree node. Higher means faster indexing but slower search, and vise versa.

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 result []ClusterPoint = 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()
c.ClusterPoints(geoPoints)
tileX := 0
tileY := 1
zoom := 4
result := 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, Long, use GetTileWithLatLon method.

TODO: Benchmarks TODO: demo server

Documentation

Overview

A very fast Golang library for geospatial point clustering.

gocluster is very fast library for geospatial point clustering server side (or client side)

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.Create new cluster
	c := NewCluster()

	//2.Convert slice of your objects to slice of GeoPoint (interface) objects
 	geoPoints := make([]GeoPoint, len(points))
 	for i := range points {
 		geoPoints[i] = points[i]
	}

	//3.Build index
	c.ClusterPoints(geoPoints)

	//3.Get tour tile with mercator coordinate projections to display directly on the map
	result := c.GetTile(0,0,0)

Library has only one dependency, it's KD-tree geospatial index https://github.com/MadAppGang/kdbush

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

Clusters of points are have autoincrement generated ids, started at ClusterIdxSeed ClusterIdxSeed is the next power of length of input array

For example, if input slice of points length is 78, ClusterIdxSeed == 100, if input slice of points length is 991, ClusterIdxSeed == 1000 etc

TODO: Benchmarks

TODO: demo server

Index

Examples

Constants

View Source 
const InfinityZoomLevel = 100

That Zoom level indicate impossible large zoom level (Cluster's max is 21)

Variables

This section is empty.

Functions

func MercatorProjection 

func MercatorProjection(coordinates GeoCoordinates) (float64, float64)

longitude/latitude to spherical mercator in [0..1] range

Types

type Cluster 

type Cluster struct {
	MinZoom           int
	MaxZoom           int
	PointSize         int
	TileSize          int
	NodeSize          int
	Indexes           []*kdbush.KDBush
	Points            []GeoPoint
	ClusterCustomizer ClusterCustomizer
	ClusterIdxSeed    int
	// contains filtered or unexported fields
}

Cluster struct get a list or stream of geo objects and produce all levels of clusters MinZoom - minimum zoom level to generate clusters MaxZoom - maximum zoom level to generate clusters Zoom range is limited by 0 to 21, and MinZoom could not be larger, then MaxZoom PointSize - pixel size of marker, affects clustering radius TileSize - size of tile in pixels, affects clustering radius

func NewCluster 

func NewCluster() *Cluster

Create new Cluster instance with default parameters: MinZoom = 0 MaxZoom = 16 PointSize = 40 TileSize = 512 (GMaps and OSM default) NodeSize is size of the KD-tree node, 64 by default. Higher means faster indexing but slower search, and vise versa.

func NewClusterFromCustomizer 

func NewClusterFromCustomizer(customizer ClusterCustomizer) *Cluster

Create new Cluster with given customizer and default parameters Same as NewCluster but allows changing the clustering result

func (*Cluster) AllClusters 

func (c *Cluster) AllClusters(zoom int) []ClusterPoint

AllClusters returns all cluster points, array of ClusterPoint, for zoom on the map. X coordinate of returned object is Longitude and. Y coordinate of returned object is Latitude.

func (*Cluster) ClusterPoints 

func (c *Cluster) ClusterPoints(points []GeoPoint, specificZoom int) error

ClusterPoint get points and create multilevel clustered indexes All points should implement GeoPoint interface they are not copied, so you could not worry about memory efficiency And GetCoordinates called only once for each object, so you could calc it on the fly, if you need

func (*Cluster) GetClusters 

func (c *Cluster) GetClusters(northWest, southEast GeoPoint, zoom int) []ClusterPoint

Returns the array of clusters for zoom level. The northWest and southEast points are boundary points of square, that should be returned. nothWest is left topmost point. southEast is right bottom point. return the object for clustered points, X coordinate of returned object is Longitude and Y coordinate of returned object is Latitude

Example 
points := importData("./testdata/places.json")

geoPoints := make([]GeoPoint, len(points))
for i := range points {
	geoPoints[i] = points[i]
}

c := NewCluster()
c.ClusterPoints(geoPoints, -1)

northWest := SimplePoint{71.36718750000001, -83.79204408779539}
southEast := SimplePoint{-71.01562500000001, 83.7539108491127}

var result []ClusterPoint = c.GetClusters(northWest, southEast, 2)
fmt.Printf("%+v", result[:3])

Output:
[{X:-14.473194953510028 Y:26.157965399212813 zoom:2 Id:107 NumPoints:1} {X:-12.408741828510014 Y:58.16339752811905 zoom:2 Id:159 NumPoints:1} {X:-9.269962828651519 Y:42.928736057812586 zoom:2 Id:127 NumPoints:1}]

func (*Cluster) GetTile 

func (c *Cluster) GetTile(x, y, z int) []ClusterPoint

return points for Tile with coordinates x and y and for zoom z return objects with pixel coordinates

Example 
points := importData("./testdata/places.json")

c := NewCluster()
c.PointSize = 60
c.MaxZoom = 3
c.TileSize = 256
c.NodeSize = 64

geoPoints := make([]GeoPoint, len(points))
for i := range points {
	geoPoints[i] = points[i]
}

c.ClusterPoints(geoPoints, -1)
result := c.GetTile(0, 0, 4)
fmt.Printf("%+v", result)

Output:
[{X:-2418 Y:165 zoom:0 Id:62 NumPoints:1} {X:-3350 Y:253 zoom:0 Id:22 NumPoints:1}]

func (*Cluster) GetTileWithLatLon 

func (c *Cluster) GetTileWithLatLon(x, y, z int) []ClusterPoint

return points for Tile with coordinates x and y and for zoom z return objects with LatLon coordinates

type ClusterCustomizer 

type ClusterCustomizer interface {
	GeoPoint2ClusterPoint(point GeoPoint) ClusterPoint
	AggregateClusterPoints(point ClusterPoint, aggregated []ClusterPoint, zoom int) ClusterPoint
}

If you want to customize the algorithm, for example to track the points that clusterized you should provide this type

type ClusterPoint 

type ClusterPoint interface {
	Coordinates() (float64, float64)
	SetCoordinates(X, Y float64) ClusterPoint

	SetZoom(int) ClusterPoint
	Zoom() int

	SetNumberOfPoints(int) ClusterPoint
	NumberOfPoints() int

	SetID(int) ClusterPoint
	ID() int
}

Struct that implements clustered points could have only one point or set of points

type GeoCoordinates 

type GeoCoordinates struct {
	Lon float64
	Lat float64
}

GeoCoordinates represent position in the Earth

func ReverseMercatorProjection 

func ReverseMercatorProjection(x, y float64) GeoCoordinates

type GeoPoint 

type GeoPoint interface {
	GetCoordinates() GeoCoordinates
}

all object, that you want to cluster should implement this protocol

type SimplePoint 

type SimplePoint struct {
	Lon, Lat float64
}

func (SimplePoint) GetCoordinates 

func (sp SimplePoint) GetCoordinates() GeoCoordinates

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.