README

rtreego

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

Build Status

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

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

Author

Written by Daniel Connelly (dhconnelly@gmail.com).

License

rtreego is released under a BSD-style license, described in the LICENSE file.

Expand ▾ Collapse ▴

Documentation

Overview

    Package rtreego is a library for efficiently storing and querying spatial data.

    Index

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    Types

    type Comparator

    type Comparator func(obj1, obj2 Spatial) (equal bool)

      Comparator compares two spatials and returns whether they are equal.

      type DimError

      type DimError struct {
      	Expected int
      	Actual   int
      }

        DimError represents a failure due to mismatched dimensions.

        func (DimError) Error

        func (err DimError) Error() string

        type DistError

        type DistError float64

          DistError is an improper distance measurement. It implements the error and is generated when a distance-related assertion fails.

          func (DistError) Error

          func (err DistError) Error() string

          type Filter

          type Filter func(results []Spatial, object Spatial) (refuse, abort bool)

            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

            func LimitFilter(limit int) Filter

              LimitFilter checks if the results have reached the limit size and aborts if so.

              type Point

              type Point []float64

                Point represents a point in n-dimensional Euclidean space.

                func (Point) ToRect

                func (p Point) ToRect(tol float64) *Rect

                  ToRect constructs a rectangle containing p with side lengths 2*tol.

                  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

                    func NewRect(p Point, lengths []float64) (r *Rect, err error)

                      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 (*Rect) Equal

                      func (r *Rect) Equal(other *Rect) bool

                        Equal returns true if the two rectangles are equal

                        func (*Rect) LengthsCoord

                        func (r *Rect) LengthsCoord(i int) float64

                          LengthsCoord returns the coordinate of the lengths of the rectangle at i

                          func (*Rect) PointCoord

                          func (r *Rect) PointCoord(i int) float64

                            PointCoord returns the coordinate of the point of the rectangle at i

                            func (*Rect) String

                            func (r *Rect) String() string

                            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

                              func NewTree(dim, min, max int, objs ...Spatial) *Rtree

                                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

                                func (tree *Rtree) Delete(obj Spatial) bool

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

                                    func (tree *Rtree) Depth() int

                                      Depth returns the maximum depth of tree.

                                      func (*Rtree) GetAllBoundingBoxes

                                      func (tree *Rtree) GetAllBoundingBoxes() []*Rect

                                        GetAllBoundingBoxes returning slice of bounding boxes by traversing tree. Slice includes bounding boxes from all non-leaf nodes.

                                        func (*Rtree) Insert

                                        func (tree *Rtree) Insert(obj Spatial)

                                          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

                                          func (tree *Rtree) NearestNeighbor(p Point) Spatial

                                            NearestNeighbor returns the closest object to the specified point. Implemented per "Nearest Neighbor Queries" by Roussopoulos et al

                                            func (*Rtree) NearestNeighbors

                                            func (tree *Rtree) NearestNeighbors(k int, p Point, filters ...Filter) []Spatial

                                              NearestNeighbors gets the closest Spatials to the Point.

                                              func (*Rtree) SearchIntersect

                                              func (tree *Rtree) SearchIntersect(bb *Rect, filters ...Filter) []Spatial

                                                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

                                                func (tree *Rtree) SearchIntersectWithLimit(k int, bb *Rect) []Spatial

                                                  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.

                                                  func (*Rtree) Size

                                                  func (tree *Rtree) Size() int

                                                    Size returns the number of objects currently stored in tree.

                                                    func (*Rtree) String

                                                    func (tree *Rtree) String() string

                                                    type Spatial

                                                    type Spatial interface {
                                                    	Bounds() *Rect
                                                    }

                                                      Spatial is an interface for objects that can be stored in an Rtree and queried.