README
¶
KDBsuh
Package kdbush provides a very fast static spatial index for 2D points based on a flat KD-tree. Very fast, but limited:
- Points only, no rectangles
- 2 dimensional
- indexing 16-40 times faster then rtreego(https: github.com/dhconnelly/rtreego) (TODO: benchmark)
- Implements radius search (rtreego and go.geo only have range search)
There are three amazing other options for geospatial indexing:
This implementation is based on:
- JS library: https: github.com/mourner/kdbush
- C++11 port: https: github.com/mourner/kdbush.hpp
##Create Index example All Items should implement Point interface:
type Point interface {
Coordinates() (X, Y float64)
}
Package represents simple struct, that implements that protocol, you could use it:
type SimplePoint struct {
X, Y float64
}
func (sp *SimplePoint)Coordinates()(float64, float64) {
return sp.X, sp.Y
}
To create index, just supply array of points and nodeSize. NodeSize is size of the KD-tree node, 64 by default. Higher means faster indexing but slower search, and vise versa.
points := []Point{
&SimplePoint{X:10,Y:10}, //0
&SimplePoint{X:15,Y:11}, //1
&SimplePoint{X:1,Y:22},
&SimplePoint{X:22,Y:22},
&SimplePoint{X:34,Y:12},
&SimplePoint{X:19,Y:19}, //5
&SimplePoint{X:32,Y:34},
}
bush := NewBush(points, 10)
##Search in range
kdbush implements Range function to find points in bounding box. Returns an array of indices that refer to the items in the original points input slice.
points := []Point{
&SimplePoint{X:10,Y:10}, //0
&SimplePoint{X:15,Y:11}, //1
&SimplePoint{X:1,Y:22},
&SimplePoint{X:22,Y:22},
&SimplePoint{X:34,Y:12},
&SimplePoint{X:19,Y:19}, //5
&SimplePoint{X:32,Y:34},
}
bush := NewBush(points, 10)
result := bush.Range(10, 10, 21, 21)
fmt.Println(result)
// Output: [0 1 5]
Documentation
¶
Overview ¶
Package kdbush provides a very fast static spatial index for 2D points based on a flat KD-tree.
Very fast, but limited. Here are main limitations:
1. Points only, no rectangles
2. 2 dimensional
3. indexing 16-40 times faster then rtreego(https://github.com/dhconnelly/rtreego) (TODO: benchmark)
4. Implements radius search (rtreego and go.geo only have range search)
There are three amazing other options for geospatial indexing:
tile38 - http://tile38.com go.geo - https://github.com/paulmach/go.geo/tree/master/quadtree rtreego - https://github.com/dhconnelly/rtreego
All this modules are dynamic and complex.
This implementation is based on:
JS library: https://github.com/mourner/kdbush
C++11 port: https://github.com/mourner/kdbush.hpp
If you liked the project, start it please: https://github.com/electrious-go/kdbush
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type KDBush ¶
KDBush a very fast static spatial index for 2D points based on a flat KD-tree. Points only, no rectangles static (no add, remove items) 2 dimensional indexing 16-40 times faster then rtreego(https://github.com/dhconnelly/rtreego) (TODO: benchmark)
func NewBush ¶
NewBush create new index from points Structure don't copy points itself, copy only coordinates Returns pointer to new KDBush index object, all data in it already indexed Input: points - slice of objects, that implements Point interface nodeSize - size of the KD-tree node, 64 by default. Higher means faster indexing but slower search, and vise versa.
func (*KDBush) Range ¶
Range finds all items within the given bounding box and returns an array of indices that refer to the items in the original points input slice.
Example ¶
points := []Point{
&SimplePoint{X: 10, Y: 10}, //0
&SimplePoint{X: 15, Y: 11}, //1
&SimplePoint{X: 1, Y: 22},
&SimplePoint{X: 22, Y: 22},
&SimplePoint{X: 34, Y: 12},
&SimplePoint{X: 19, Y: 19}, //5
&SimplePoint{X: 32, Y: 34},
}
bush := NewBush(points, 10)
result := bush.Range(10, 10, 21, 21)
fmt.Println(result)
Output: [0 1 5]
func (*KDBush) Within ¶
Within finds all items within a given radius from the query point and returns an array of indices.
Example ¶
points := []Point{
&SimplePoint{X: 10, Y: 10}, //0
&SimplePoint{X: 15, Y: 11}, //1
&SimplePoint{X: 1, Y: 22}, //3
&SimplePoint{X: 22, Y: 22},
&SimplePoint{X: 34, Y: 12},
&SimplePoint{X: 19, Y: 19}, //5
&SimplePoint{X: 32, Y: 34},
}
bush := NewBush(points, 10)
result := bush.Within(&SimplePoint{15, 15}, 10)
fmt.Println(result)
Output: [0 1 3 5]
type Point ¶
type Point interface {
Coordinates() (X, Y float64)
}
Interface, that should be implemented by indexing structure It's just simply returns points coordinates Called once, only when index created, so you could calc values on the fly for this interface
type SimplePoint ¶
type SimplePoint struct {
X, Y float64
}
SimplePoint minimal struct, that implements Point interface
func (*SimplePoint) Coordinates ¶
func (sp *SimplePoint) Coordinates() (float64, float64)
Coordinates to make SimplePoint's implementation of Point interface satisfied
Source Files