README
¶
Geo Index
Geo Index library
Overview
Splits the earth surface in a grid. At each cell we can store data, such as list of points, count of points, etc. It can do KNearest and Range queries. For more detailed description check https://sudo.hailoapp.com/services/2015/02/18/geoindex/ .
Demo
http://go-geoindex.appspot.com/static/nearest.html - Click to select the nearest points.
http://go-geoindex.appspot.com/static/cluster.html - A map with 100K points around the world. Zoom in and out to cluster.
API
type Driver struct {
lat float64
lon float64
id string
canAcceptJobs bool
}
// Implement Point interface
func (d *Driver) Lat() float64 { return d.lat }
func (d *Driver) Lon() float64 { return d.lon }
func (d *Driver) Id() string { return d.id }
// create points index with resolution (cell size) 0.5 km
index := NewPointsIndex(Km(0.5))
// Adds a point in the index, if a point with the same id exists it's removed and the new one is added
index.Add(&Driver{"id1", lat, lng, true})
index.Add(&Driver{"id2", lat, lng, false})
// Removes a point from the index by id
index.Remove("id1")
// get the k-nearest points to a point, within some distance
points := index.KNearest(&GeoPoint{id, lat, lng}, 5, Km(5), func(p Point) bool {
return p.(* Driver).canAcceptJobs
})
// get the points within a range on the map
points := index.Range(topLeftPoint, bottomRightPoint)
Index types
There are several index types
NewPointsIndex(Km(0.5)) // Creates index that maintains points
NewExpiringPointsIndex(Km(0.5), Minutes(5)) // Creates index that expires the points after some interval
NewCountIndex(Km(0.5)) // Creates index that maintains counts of the points in each cell
NewExpiringCountIndex(Km(0.5), Minutes(15)) // Creates index that maintains expiring count
NewClusteringIndex() // index that clusters the points at different zoom levels, so we can create maps
NewExpiringClusteringIndex(Minutes(15)) // index that clusters and expires the points at different zoom levels
// so we can create real time maps of customer request, etc in the driver app
Performance Benchmarks
BenchmarkClusterIndexAdd 500000 5395 ns/op
BenchmarkClusterIndexStreetRange 100000 22207 ns/op
BenchmarkClusterIndexCityRange 100000 16389 ns/op
BenchmarkClusterIndexEuropeRange 50000 36559 ns/op
BenchmarkExpiringClusterIndexAdd 300000 7124 ns/op
BenchmarkExpiringClusterIndexStreetRange 50000 27030 ns/op
BenchmarkExpiringClusterIndexCityRange 100000 22185 ns/op
BenchmarkExpiringClusterIndexEuropeRange 30000 52080 ns/op
BenchmarkCountIndexAdd 1000000 1670 ns/op
BenchmarkCountIndexCityRange 100000 20325 ns/op
BenchmarkExpiringCountIndexAdd 500000 2808 ns/op
BenchmarkExpiringCountIndexRange 50000 35791 ns/op
BenchmarkPointIndexRange 100000 15945 ns/op
BenchmarkPointIndexAdd 1000000 2416 ns/op
BenchmarkPointIndexKNearest 100000 13788 ns/op
BenchmarkExpiringPointIndexAdd 500000 4324 ns/op
BenchmarkExpiringPointIndexKNearest 100000 15638 ns/op
BenchmarkExpiringPointIndexRange 100000 20386 ns/op
Documentation
¶
Overview ¶
Package geoindex provides in memory geoindex implementation. It works by splitting the earth surface into grid with fixed size cells and storing data in each cell. The data can be points, count of points, and expiring points/counts. Has Range and K-Nearest queries.
Index ¶
- func BearingTo(p1, p2 Point) float64
- type ClusteringIndex
- func (index *ClusteringIndex) Add(point Point)
- func (index *ClusteringIndex) Clone() *ClusteringIndex
- func (index *ClusteringIndex) KNearest(point Point, k int, maxDistance Meters, accept func(p Point) bool) []Point
- func (index *ClusteringIndex) Range(topLeft Point, bottomRight Point) []Point
- func (index *ClusteringIndex) Remove(id string)
- type CountIndex
- func (countIndex *CountIndex) Add(point Point)
- func (index *CountIndex) Clone() *CountIndex
- func (index *CountIndex) KNearest(point Point, k int, maxDistance Meters, accept func(p Point) bool) []Point
- func (countIndex *CountIndex) Range(topLeft Point, bottomRight Point) []Point
- func (countIndex *CountIndex) Remove(id string)
- type CountPoint
- type Direction
- type GeoPoint
- type Index
- type Meters
- type Minutes
- type Point
- type PointsIndex
- func (points *PointsIndex) Add(point Point)
- func (pi *PointsIndex) Clone() *PointsIndex
- func (points *PointsIndex) Get(id string) Point
- func (points *PointsIndex) GetAll() map[string]Point
- func (points *PointsIndex) KNearest(point Point, k int, maxDistance Meters, accept func(p Point) bool) []Point
- func (points *PointsIndex) PointsWithin(point Point, distance Meters, accept func(p Point) bool) []Point
- func (points *PointsIndex) Range(topLeft Point, bottomRight Point) []Point
- func (points *PointsIndex) Remove(id string)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type ClusteringIndex ¶
type ClusteringIndex struct {
// contains filtered or unexported fields
}
func NewClusteringIndex ¶
func NewClusteringIndex() *ClusteringIndex
NewClusteringIndex creates index that clusters the points at three levels with cell size 0.5, 5 and 500km. Useful for creating maps.
func NewExpiringClusteringIndex ¶
func NewExpiringClusteringIndex(expiration Minutes) *ClusteringIndex
NewExpiringClusteringIndex creates index that clusters the points at three levels with cell size 0.5, 5 and 500km and expires them after expiration minutes.
func (*ClusteringIndex) Clone ¶
func (index *ClusteringIndex) Clone() *ClusteringIndex
func (*ClusteringIndex) KNearest ¶
func (index *ClusteringIndex) KNearest(point Point, k int, maxDistance Meters, accept func(p Point) bool) []Point
KNearest returns the K-Nearest points near point within maxDistance, that match the accept function.
func (*ClusteringIndex) Range ¶
func (index *ClusteringIndex) Range(topLeft Point, bottomRight Point) []Point
Range returns points or count points depending on the size of the topLeft and bottomRight range.
func (*ClusteringIndex) Remove ¶
func (index *ClusteringIndex) Remove(id string)
Remove removes a point.
type CountIndex ¶
type CountIndex struct {
// contains filtered or unexported fields
}
func NewCountIndex ¶
func NewCountIndex(resolution Meters) *CountIndex
NewCountIndex creates an index which counts the points in each cell.
func NewExpiringCountIndex ¶
func NewExpiringCountIndex(resolution Meters, expiration Minutes) *CountIndex
NewExpiringCountIndex creates an index, which maintains an expiring counter for each cell.
func (*CountIndex) Clone ¶
func (index *CountIndex) Clone() *CountIndex
func (*CountIndex) KNearest ¶
func (index *CountIndex) KNearest(point Point, k int, maxDistance Meters, accept func(p Point) bool) []Point
KNearest just to satisfy an interface. Doesn't make much sense for count index.
type CountPoint ¶
type CountPoint struct {
*GeoPoint
Count interface{}
}
func (*CountPoint) String ¶
func (p *CountPoint) String() string
type Direction ¶
type Direction int
func DirectionTo ¶
DirectionTo returns the direction from p1 to p2
type PointsIndex ¶
type PointsIndex struct {
// contains filtered or unexported fields
}
A geoindex that stores points.
func NewExpiringPointsIndex ¶
func NewExpiringPointsIndex(resolution Meters, expiration Minutes) *PointsIndex
NewExpiringPointsIndex creates new PointIndex that expires the points in each cell after expiration minutes.
func NewPointsIndex ¶
func NewPointsIndex(resolution Meters) *PointsIndex
NewPointsIndex creates new PointsIndex that maintains the points in each cell.
func (*PointsIndex) Add ¶
func (points *PointsIndex) Add(point Point)
Add adds a point to the index. If a point with the same Id already exists it gets replaced.
func (*PointsIndex) Clone ¶
func (pi *PointsIndex) Clone() *PointsIndex
func (*PointsIndex) Get ¶
func (points *PointsIndex) Get(id string) Point
Get gets a point from the index given an id.
func (*PointsIndex) GetAll ¶
func (points *PointsIndex) GetAll() map[string]Point
GetAll get all Points from the index as a map from id to point
func (*PointsIndex) KNearest ¶
func (points *PointsIndex) KNearest(point Point, k int, maxDistance Meters, accept func(p Point) bool) []Point
KNearest returns the k nearest points near point within maxDistance that match the accept criteria.
func (*PointsIndex) PointsWithin ¶
func (points *PointsIndex) PointsWithin(point Point, distance Meters, accept func(p Point) bool) []Point
PointsWithin returns all points with distance of point that match the accept criteria.
func (*PointsIndex) Range ¶
func (points *PointsIndex) Range(topLeft Point, bottomRight Point) []Point
Range returns the points within the range defined by top left and bottom right.
func (*PointsIndex) Remove ¶
func (points *PointsIndex) Remove(id string)
Remove removes a point from the index.
Source Files
Directories