Documentation ¶
Overview ¶
Package cluster a very fast Golang library for geospatial point clustering.
cluster 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 ¶
- Constants
- func MercatorProjection(coordinates GeoCoordinates) (float64, float64)
- type Cluster
- func (c *Cluster) AllClusters(zoom int) []Point
- func (c *Cluster) GetClusterExpansionZoom(clusterID int) int
- func (c *Cluster) GetClusters(northWest, southEast GeoPoint, zoom int) []Point
- func (c *Cluster) GetClustersPointsInRadius(clusterID int) []*Point
- func (c *Cluster) GetTile(x, y, z int) []Point
- func (c *Cluster) GetTileWithLatLng(x, y, z int) []Point
- type GeoCoordinates
- type GeoPoint
- type Option
- type Point
Examples ¶
Constants ¶
const (
// InfinityZoomLevel indicate impossible large zoom level (Cluster's max is 21)
InfinityZoomLevel = 100
)
Variables ¶
This section is empty.
Functions ¶
func MercatorProjection ¶
func MercatorProjection(coordinates GeoCoordinates) (float64, float64)
MercatorProjection will convert lat,lng into spherical mercator range which is 0 to 1
Types ¶
type Cluster ¶
type Cluster struct { // MinZoom minimum zoom level to generate clusters MinZoom int // MaxZoom maximum zoom level to generate clusters MaxZoom int // PointSize pixel size of marker, affects clustering radius PointSize int // TileSize size of tile in pixels, affects clustering radius TileSize int // NodeSize is size of the KD-tree node, 64 by default. Higher means faster indexing but slower search, and vise versa. NodeSize int // Indexes keeps all KDBush trees Indexes []*kdbush.KDBush // Points keeps original slice of given points Points []GeoPoint // contains filtered or unexported fields }
Cluster struct get a list or stream of geo objects and produce all levels of clusters Zoom range is limited by 0 to 21, and MinZoom could not be larger, then MaxZoom
func New ¶
New create new Cluster instance with default params. Will use 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) AllClusters ¶
AllClusters returns all cluster points, array of Point, for zoom on the map. X coordinate of returned object is Longitude and. Y coordinate of returned object is Latitude.
func (*Cluster) GetClusterExpansionZoom ¶
GetClusterExpansionZoom will return how much you need to zoom to get to a next cluster
func (*Cluster) GetClusters ¶
GetClusters returns the array of clusters for zoom level. The northWest and southEast points are boundary points of square, that should be returned. northWest 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, _ := New(geoPoints) northWest := simplePoint{-71.01562500000001, 83.7539108491127} southEast := simplePoint{71.36718750000001, -83.79204408779539} result := c.GetClusters(northWest, southEast, 2) fmt.Printf("%+v", result[:3])
Output: [{X:-14.473194953510028 Y:26.157965399212813 zoom:1 ID:107 NumPoints:1} {X:-12.408741828510014 Y:58.16339752811905 zoom:1 ID:159 NumPoints:1} {X:-9.269962828651519 Y:42.928736057812586 zoom:1 ID:127 NumPoints:1}]
func (*Cluster) GetClustersPointsInRadius ¶
GetClustersPointsInRadius will return child points for specific cluster this is done with kdbush.Within method allowing fast search
func (*Cluster) GetTile ¶
GetTile return points for Tile with coordinates x and y and for zoom z return objects with pixel coordinates
Example ¶
points := importData("./testdata/places.json") geoPoints := make([]GeoPoint, len(points)) for i := range points { geoPoints[i] = points[i] } c, _ := New(geoPoints, WithinZoom(0, 3), WithPointSize(60), WithTileSize(256), WithNodeSize(64)) 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) GetTileWithLatLng ¶
GetTileWithLatLng return points for Tile with coordinates x and y and for zoom z return objects with LatLng coordinates
type GeoCoordinates ¶
GeoCoordinates represent position in the Earth
func ReverseMercatorProjection ¶
func ReverseMercatorProjection(x, y float64) GeoCoordinates
ReverseMercatorProjection converts spherical mercator range to lat,lng
type GeoPoint ¶
type GeoPoint interface {
GetCoordinates() GeoCoordinates
}
GeoPoint interface returning lat/lng coordinates. All object, that you want to cluster should implement this protocol
type Option ¶
Option allows to modify cluster properties or cluster itself
func WithTileSize ¶
WithTileSize will set tile size. TileSize = 512 (GMaps and OSM default)
type Point ¶
type Point struct {
X, Y float64
ID int //Index for pint, Id for cluster
NumPoints int
// contains filtered or unexported fields
}
Point struct that implements clustered points could have only one point or set of points
func (*Point) Coordinates ¶
Coordinates to be compatible with interface
Source Files ¶
Directories ¶
Path | Synopsis |
---|---|
examples
|
|
googlemaps/spherand
Package spherand generates random points uniformly on a sphere.
|
Package spherand generates random points uniformly on a sphere. |