README
rtreego
A library for efficiently storing and querying spatial data in the Go programming language.
About
The Rtree is a popular data structure for efficiently storing and querying spatial objects; one common use is implementing geospatial indexes in database management systems. Both boundingbox queries and knearestneighbor queries are supported.
Rtrees are balanced, so maximum tree height is guaranteed to be logarithmic in the number of entries; however, good worstcase performance is not guaranteed. Instead, a number of rebalancing heuristics are applied that perform well in practice. For more details please refer to the references.
This implementation handles the general Ndimensional case; for a more efficient implementation for the 3dimensional case, see Patrick Higgins' fork.
Getting Started
Get the source code from GitHub or,
with Go 1 installed, run go get github.com/dhconnelly/rtreego
.
Make sure you import github.com/dhconnelly/rtreego
in your Go source files.
Documentation
Storing, updating, and deleting objects
To create a new tree, specify the number of spatial dimensions and the minimum and maximum branching factor:
rt := rtreego.NewTree(2, 25, 50)
You can also bulkload the tree when creating it by passing the objects as a parameter.
rt := rtreego.NewTree(2, 25, 50, objects...)
Any type that implements the Spatial
interface can be stored in the tree:
type Spatial interface {
Bounds() *Rect
}
Rect
s are data structures for representing spatial objects, while Point
s
represent spatial locations. Creating Point
s is easythey're just slices
of float64
s:
p1 := rtreego.Point{0.4, 0.5}
p2 := rtreego.Point{6.2, 3.4}
To create a Rect
, specify a location and the lengths of the sides:
r1, _ := rtreego.NewRect(p1, []float64{1, 2})
r2, _ := rtreego.NewRect(p2, []float64{1.7, 2.7})
To demonstrate, let's create and store some test data.
type Thing struct {
where *Rect
name string
}
func (t *Thing) Bounds() *Rect {
return t.where
}
rt.Insert(&Thing{r1, "foo"})
rt.Insert(&Thing{r2, "bar"})
size := rt.Size() // returns 2
We can insert and delete objects from the tree in any order.
rt.Delete(thing2)
// do some stuff...
rt.Insert(anotherThing)
Note that Delete
function does the equality comparison by comparing the
memory addresses of the objects. If you do not have a pointer to the original
object anymore, you can define a custom comparator.
type Comparator func(obj1, obj2 Spatial) (equal bool)
You can use a custom comparator with DeleteWithComparator
function.
cmp := func(obj1, obj2 Spatial) bool {
sp1 := obj1.(*IDRect)
sp2 := obj2.(*IDRect)
return sp1.ID == sp2.ID
}
rt.DeleteWithComparator(obj, cmp)
If you want to store points instead of rectangles, you can easily convert a
point into a rectangle using the ToRect
method:
var tol = 0.01
type Somewhere struct {
location rtreego.Point
name string
wormhole chan int
}
func (s *Somewhere) Bounds() *Rect {
// define the bounds of s to be a rectangle centered at s.location
// with side lengths 2 * tol:
return s.location.ToRect(tol)
}
rt.Insert(&Somewhere{rtreego.Point{0, 0}, "Someplace", nil})
If you want to update the location of an object, you must delete it, update it,
and reinsert. Just modifying the object so that the *Rect
returned by
Location()
changes, without deleting and reinserting the object, will
corrupt the tree.
Queries
Boundingbox and knearestneighbors queries are supported.
Boundingbox queries require a search *Rect
. It returns all objects that
touch the search rectangle.
bb, _ := rtreego.NewRect(rtreego.Point{1.7, 3.4}, []float64{3.2, 1.9})
// Get a slice of the objects in rt that intersect bb:
results := rt.SearchIntersect(bb)
Filters
You can filter out values during searches by implementing Filter functions.
type Filter func(results []Spatial, object Spatial) (refuse, abort bool)
A filter for limiting results by result count is included in the package for backwards compatibility.
// maximum of three results will be returned
tree.SearchIntersect(bb, LimitFilter(3))
Nearestneighbor queries find the objects in a tree closest to a specified query point.
q := rtreego.Point{6.5, 2.47}
k := 5
// Get a slice of the k objects in rt closest to q:
results = rt.NearestNeighbors(k, q)
More information
See GoDoc for full API documentation.
References

A. Guttman. Rtrees: A Dynamic Index Structure for Spatial Searching. Proceedings of ACM SIGMOD, pages 4757, 1984. http://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Guttman84.pdf

N. Beckmann, H .P. Kriegel, R. Schneider and B. Seeger. The R*tree: An Efficient and Robust Access Method for Points and Rectangles. Proceedings of ACM SIGMOD, pages 323331, May 1990. http://infolab.usc.edu/csci587/Fall2011/papers/p322beckmann.pdf

N. Roussopoulos, S. Kelley and F. Vincent. Nearest Neighbor Queries. ACM SIGMOD, pages 7179, 1995. http://www.postgis.org/support/nearestneighbor.pdf
Author
Written by Daniel Connelly (dhconnelly@gmail.com).
License
rtreego is released under a BSDstyle license, described in the LICENSE
file.
Documentation
Overview ¶
Package rtreego is a library for efficiently storing and querying spatial data.
Index ¶
 type Comparator
 type DimError
 type DistError
 type Filter
 type Point
 type Rect
 type Rtree
 func (tree *Rtree) Delete(obj Spatial) bool
 func (tree *Rtree) DeleteWithComparator(obj Spatial, cmp Comparator) bool
 func (tree *Rtree) Depth() int
 func (tree *Rtree) GetAllBoundingBoxes() []*Rect
 func (tree *Rtree) Insert(obj Spatial)
 func (tree *Rtree) NearestNeighbor(p Point) Spatial
 func (tree *Rtree) NearestNeighbors(k int, p Point, filters ...Filter) []Spatial
 func (tree *Rtree) SearchIntersect(bb *Rect, filters ...Filter) []Spatial
 func (tree *Rtree) SearchIntersectWithLimit(k int, bb *Rect) []Spatial
 func (tree *Rtree) Size() int
 func (tree *Rtree) String() string
 type Spatial
Constants ¶
Variables ¶
Functions ¶
Types ¶
type Comparator ¶
Comparator compares two spatials and returns whether they are equal.
type DistError ¶
type DistError float64
DistError is an improper distance measurement. It implements the error and is generated when a distancerelated assertion fails.
type Filter ¶
Filter is an interface for filtering leaves during search. The parameters should be treated as readonly. If refuse is true, the current entry will not be added to the result set. If abort is true, the search is aborted and the current result set will be returned.
func LimitFilter ¶
LimitFilter checks if the results have reached the limit size and aborts if so.
type Rect ¶
type Rect struct {
// contains filtered or unexported fields
}
Rect represents a subset of ndimensional Euclidean space of the form [a1, b1] x [a2, b2] x ... x [an, bn], where ai < bi for all 1 <= i <= n.
func NewRect ¶
NewRect constructs and returns a pointer to a Rect given a corner point and the lengths of each dimension. The point p should be the mostnegative point on the rectangle (in every dimension) and every length should be positive.
func (*Rect) LengthsCoord ¶
LengthsCoord returns the coordinate of the lengths of the rectangle at i
func (*Rect) PointCoord ¶
PointCoord returns the coordinate of the point of the rectangle at i
type Rtree ¶
type Rtree struct { Dim int MinChildren int MaxChildren int // contains filtered or unexported fields }
Rtree represents an Rtree, a balanced search tree for storing and querying spatial objects. Dim specifies the number of spatial dimensions and MinChildren/MaxChildren specify the minimum/maximum branching factors.
func NewTree ¶
NewTree returns an Rtree. If the number of objects given on initialization is larger than max, the Rtree will be initialized using the Overlap Minimizing Topdown bulkloading algorithm.
func (*Rtree) Delete ¶
Delete removes an object from the tree. If the object is not found, returns false, otherwise returns true. Uses the default comparator when checking equality.
Implemented per Section 3.3 of "Rtrees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 4757, 1984.
func (*Rtree) DeleteWithComparator ¶
func (tree *Rtree) DeleteWithComparator(obj Spatial, cmp Comparator) bool
DeleteWithComparator removes an object from the tree using a custom comparator for evaluating equalness. This is useful when you want to remove an object from a tree but don't have a pointer to the original object anymore.
func (*Rtree) GetAllBoundingBoxes ¶
GetAllBoundingBoxes returning slice of bounding boxes by traversing tree. Slice includes bounding boxes from all nonleaf nodes.
func (*Rtree) Insert ¶
Insert inserts a spatial object into the tree. If insertion causes a leaf node to overflow, the tree is rebalanced automatically.
Implemented per Section 3.2 of "Rtrees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 4757, 1984.
func (*Rtree) NearestNeighbor ¶
NearestNeighbor returns the closest object to the specified point. Implemented per "Nearest Neighbor Queries" by Roussopoulos et al
func (*Rtree) NearestNeighbors ¶
NearestNeighbors gets the closest Spatials to the Point.
func (*Rtree) SearchIntersect ¶
SearchIntersect returns all objects that intersect the specified rectangle. Implemented per Section 3.1 of "Rtrees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 4757, 1984.
func (*Rtree) SearchIntersectWithLimit ¶
SearchIntersectWithLimit is similar to SearchIntersect, but returns immediately when the first k results are found. A negative k behaves exactly like SearchIntersect and returns all the results.
Kept for backwards compatibility, please use SearchIntersect with a LimitFilter.