README
¶
rtreego
A library for efficiently storing and querying spatial data in the Go programming language.
About
The R-tree is a popular data structure for efficiently storing and querying spatial objects; one common use is implementing geospatial indexes in database management systems. Both bounding-box queries and k-nearest-neighbor queries are supported.
R-trees are balanced, so maximum tree height is guaranteed to be logarithmic in the number of entries; however, good worst-case 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 N-dimensional case; for a more efficient implementation for the 3-dimensional 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 bulk-load 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
}
Rects are data structures for representing spatial objects, while Points
represent spatial locations. Creating Points is easy--they're just slices
of float64s:
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 re-insert. Just modifying the object so that the *Rect returned by
Location() changes, without deleting and re-inserting the object, will
corrupt the tree.
Queries
Bounding-box and k-nearest-neighbors queries are supported.
Bounding-box queries require a search *Rect. This function will return all
objects which has a non-zero intersection volume with the input 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))
Nearest-neighbor 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. R-trees: A Dynamic Index Structure for Spatial Searching. Proceedings of ACM SIGMOD, pages 47-57, 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 323-331, May 1990. http://infolab.usc.edu/csci587/Fall2011/papers/p322-beckmann.pdf
-
N. Roussopoulos, S. Kelley and F. Vincent. Nearest Neighbor Queries. ACM SIGMOD, pages 71-79, 1995. http://www.postgis.org/support/nearestneighbor.pdf
Author
Written by Daniel Connelly (dhconnelly@gmail.com).
License
rtreego is released under a BSD-style 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 ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 distance-related assertion fails.
type Filter ¶
Filter is an interface for filtering leaves during search. The parameters should be treated as read-only. 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 n-dimensional 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 most-negative point on the rectangle (in every dimension) and every length should be positive.
func NewRectFromPoints ¶ added in v1.1.0
NewRectFromPoints constructs and returns a pointer to a Rect given a corner points.
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 R-tree, 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 Top-down bulk-loading 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 "R-trees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 47-57, 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 non-leaf 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 "R-trees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 47-57, 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 "R-trees: A Dynamic Index Structure for Spatial Searching" by A. Guttman, Proceedings of ACM SIGMOD, p. 47-57, 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.
Source Files