geoindex

package module
v0.0.0-...-64631bf Latest Latest
Warning

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

Go to latest
Published: Jan 27, 2016 License: MIT Imports: 12 Imported by: 38

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

Constants

This section is empty.

Variables

This section is empty.

Functions

func BearingTo

func BearingTo(p1, p2 Point) float64

BearingTo returns the bearing from p1 to p2

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) Add

func (index *ClusteringIndex) Add(point Point)

Add adds a point.

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) Add

func (countIndex *CountIndex) Add(point Point)

Add adds a point.

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.

func (*CountIndex) Range

func (countIndex *CountIndex) Range(topLeft Point, bottomRight Point) []Point

Range returns the counters within some lat, lng range.

func (*CountIndex) Remove

func (countIndex *CountIndex) Remove(id string)

Remove removes a point.

type CountPoint

type CountPoint struct {
	*GeoPoint
	Count interface{}
}

func (*CountPoint) String

func (p *CountPoint) String() string

type Direction

type Direction int
const (
	NorthEast Direction = iota
	East
	SouthEast
	South
	SouthWest
	West
	NorthWest
	North
)

func DirectionTo

func DirectionTo(p1, p2 Point) Direction

DirectionTo returns the direction from p1 to p2

type GeoPoint

type GeoPoint struct {
	Pid  string  `json:"Id"`
	Plat float64 `json:"Lat"`
	Plon float64 `json:"Lon"`
}

Point implementation.

func NewGeoPoint

func NewGeoPoint(id string, lat, lon float64) *GeoPoint

func (*GeoPoint) Id

func (p *GeoPoint) Id() string

func (*GeoPoint) Lat

func (p *GeoPoint) Lat() float64

func (*GeoPoint) Lon

func (p *GeoPoint) Lon() float64

func (*GeoPoint) String

func (p *GeoPoint) String() string

type Index

type Index interface {
	Add(point Point)
	Range(topLeft Point, bottomRight Point) []Point
	KNearest(point Point, k int, maxDistance Meters, accept func(p Point) bool) []Point
}

type Meters

type Meters float64

func Distance

func Distance(p1, p2 Point) Meters

func Km

func Km(km float64) Meters

func Meter

func Meter(meters float64) Meters

type Minutes

type Minutes int

type Point

type Point interface {
	Id() string
	Lat() float64
	Lon() float64
}

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.

Directories

Path Synopsis
demo

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL