README

rtreego

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

Forked from github.com/dhconnelly/rtreego to specialize for 3 dimensions and tune for fewer memory allocations.

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. The variant implemented here, known as the R*-tree, improves performance and increases storage utilization. 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.

Status

Geometric primitives (points, rectangles, and their relevant geometric algorithms) are implemented and tested. The R-tree data structure and algorithms are currently under development.

Install

With Go 1 installed, just run go get github.com/patrick-higgins/rtreego.

Usage

Make sure you import github.com/patrick-higgins/rtreego in your Go source files.

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)

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)

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 argument and come in two flavors: containment search and intersection search. The former returns all objects that fall strictly inside the search rectangle, while the latter 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)

// Get a slice of the objects in rt that are contained inside bb:
results, _ = rt.SearchContained(bb)

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.SearchNearestNeighbors(q, k)
More information

See http://github.com/patrick-higgins/rtreego for full API documentation.

References

Author

rtreego is written and maintained by Daniel Connelly. You can find my stuff at dhconnelly.com or email me at dhconnelly@gmail.com.

This fork is maintained by Patrick Higgins (patrick.allen.higgins@gmail.com).

License

rtreego is released under a BSD-style license; see LICENSE for more details.

Expand ▾ Collapse ▴

Documentation

Overview

    A library for efficiently storing and querying spatial data.

    Index

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    func ToRect

    func ToRect(p geom.Point, tol float64) *geom.Bounds

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

      Types

      type DistError

      type DistError geom.Point

        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 Rtree

        type Rtree struct {
        	MinChildren int
        	MaxChildren int
        	// contains filtered or unexported fields
        }

          Rtree represents an R-tree, a balanced search tree for storing and querying spatial objects. MinChildren/MaxChildren specify the minimum/maximum branching factors.

          func NewTree

          func NewTree(MinChildren, MaxChildren int) *Rtree

            NewTree creates a new R-tree instance.

            func (*Rtree) Delete

            func (tree *Rtree) Delete(obj geom.Geom) bool

              Delete removes an object from the tree. If the object is not found, ok is false; otherwise ok is true.

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

              func (tree *Rtree) Depth() int

                Depth returns the maximum depth of tree.

                func (*Rtree) Insert

                func (tree *Rtree) Insert(obj geom.Geom)

                  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 geom.Point) geom.Geom

                    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 geom.Point) []geom.Geom

                    func (*Rtree) SearchIntersect

                    func (tree *Rtree) SearchIntersect(bb *geom.Bounds) []geom.Geom

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

                      func (tree *Rtree) Size() int

                        Size returns the number of objects currently stored in tree.

                        func (*Rtree) String

                        func (tree *Rtree) String() string

                        Source Files