Repository files navigation

A library for efficiently storing and querying spatial datain the Go programming language.

The R-tree is a popular data structure for efficiently storing andquerying spatial objects; one common use is implementing geospatialindexes in database management systems. Both bounding-box queriesand k-nearest-neighbor queries are supported.

R-trees are balanced, so maximum tree height is guaranteed to belogarithmic in the number of entries; however, good worst-caseperformance is not guaranteed. Instead, a number of rebalancingheuristics are applied that perform well in practice. For moredetails please refer to the references.

This implementation handles the general N-dimensional case; for a moreefficient implementation for the 3-dimensional case, seePatrickHiggins' fork.

Get the source code fromGitHub or,with Go 1 installed, rungo get github.com/dhconnelly/rtreego.

Make sure youimport github.com/dhconnelly/rtreego in your Go source files.

To create a new tree, specify the number of spatial dimensions and the minimumand maximum branching factor:

rt:=rtreego.NewTree(2,25,50)

You can also bulk-load the tree when creating it by passing the objects asa parameter.

rt:=rtreego.NewTree(2,25,50,objects...)

Any type that implements theSpatial interface can be stored in the tree:

typeSpatialinterface {Bounds()*Rect    }

Rects are data structures for representing spatial objects, whilePointsrepresent spatial locations. CreatingPoints is easy--they're just slicesoffloat64s:

p1:= rtreego.Point{0.4,0.5}p2:= rtreego.Point{6.2,-3.4}

To create aRect, 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.

typeThingstruct {where*Rectnamestring    }func (t*Thing)Bounds()*Rect {returnt.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 thatDelete function does the equality comparison by comparing thememory addresses of the objects. If you do not have a pointer to the originalobject anymore, you can define a custom comparator.

typeComparatorfunc(obj1,obj2Spatial) (equalbool)

You can use a custom comparator withDeleteWithComparator function.

cmp:=func(obj1,obj2Spatial)bool {sp1:=obj1.(*IDRect)sp2:=obj2.(*IDRect)returnsp1.ID==sp2.ID    }rt.DeleteWithComparator(obj,cmp)

If you want to store points instead of rectangles, you can easily convert apoint into a rectangle using theToRect method:

vartol=0.01typeSomewherestruct {location rtreego.Pointnamestringwormholechanint    }func (s*Somewhere)Bounds()*Rect {// define the bounds of s to be a rectangle centered at s.location// with side lengths 2 * tol:returns.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 byLocation() changes, without deleting and re-inserting the object, willcorrupt the tree.

Bounding-box and k-nearest-neighbors queries are supported.

Bounding-box queries require a search*Rect. This function will return allobjects 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)

You can filter out values during searches by implementing Filter functions.

typeFilterfunc(results []Spatial,objectSpatial) (refuse,abortbool)

A filter for limiting results by result count is included in the package forbackwards compatibility.

// maximum of three results will be returnedtree.SearchIntersect(bb,LimitFilter(3))

Nearest-neighbor queries find the objects in a tree closest to a specifiedquery 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)

SeeGoDoc for full APIdocumentation.

• 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: AnEfficient and Robust Access Method for Points and Rectangles. Proceedingsof 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. ACMSIGMOD, pages 71-79, 1995.http://www.postgis.org/support/nearestneighbor.pdf

Written byDaniel Connelly (dhconnelly@gmail.com).

rtreego is released under a BSD-style license, described in theLICENSEfile.