rtreego

To store custom objects in an R-tree, your type must implement the Spatial interface by providing a Bounds() method that returns a *Rect.

type Spatial interface {
  Bounds() *Rect
}

type Thing struct {
  where *Rect
  name string
}

func (t *Thing) Bounds() *Rect {
  return t.where
}

To install rtreego, use the Go toolchain to fetch the package from GitHub:

go get github.com/dhconnelly/rtreego

To store custom objects in an Rtree, your type must implement the Spatial interface by providing a Bounds() method that returns a Rect.

type MyObject struct {
    // ... fields
}

func (m *MyObject) Bounds() rtreego.Rect {
    return rtreego.Rect{...
}

You can create a new R-tree by specifying the number of spatial dimensions, the minimum branching factor, and the maximum branching factor. You can also perform a bulk-load by passing existing objects during initialization.

Standard initialization: rt := rtreego.NewTree(dimensions, min, max)

Bulk-load initialization: rt := rtreego.NewTree(dimensions, min, max, objects...)

// Create a 2D tree with min branching 25 and max 50
rt := rtreego.NewTree(2, 25, 50)

// Or bulk-load with objects
rt := rtreego.NewTree(2, 25, 50, objects...)

Bounding-box queries

Use rt.SearchIntersect(searchRect) to find all objects that have a non-zero intersection volume with the provided *Rect.

K-Nearest-Neighbors (KNN) queries

Use rt.NearestNeighbors(k, queryPoint) to find the k objects in the tree closest to the specified rtreego.Point.

// Bounding-box search
bb, _ := rtreego.NewRect(rtreego.Point{1.7, -3.4}, []float64{3.2, 1.9})
results := rt.SearchIntersect(bb)

// K-Nearest-Neighbors search
q := rtreego.Point{6.5, -2.47}
k := 5
results = rt.NearestNeighbors(k, q)

You can refine search results by providing a Filter function to the search methods. A filter can decide to refuse a specific object or abort the entire search.

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

Example of using the built-in LimitFilter to restrict the number of returned results:

// Returns a maximum of three results
results := tree.SearchIntersect(bb, rtreego.LimitFilter(3))

Use SearchIntersect(bb Rect, filters ...Filter) to find all objects whose bounding boxes intersect the provided Rect. You can optionally pass Filter functions to refine the results (e.g., to limit the number of results returned).

searchArea := rtreego.Rect{...}
results := tree.SearchIntersect(searchArea)

You can remove objects using two methods:

1. Delete(obj Spatial): Uses the default equality comparator to find and remove the object.
2. DeleteWithComparator(obj Spatial, cmp Comparator): Allows you to provide a custom Comparator function. This is useful if you want to remove an object based on its properties without having the exact original pointer/instance.

// Using default comparator
success := tree.Delete(myObj)

// Using custom comparator
success := tree.DeleteWithComparator(myObj, func(obj1, obj2 rtreego.Spatial) bool {
    return obj1.(*MyType).ID == obj2.(*MyType).ID
})

Use the Insert(obj Spatial) method to add a new object to the tree. The tree automatically handles rebalancing and node splitting if a leaf node overflows.

tree.Insert(mySpatialObject)

Once you have a Rect, you can inspect its dimensions and size:

• PointCoord(i int) float64: Returns the coordinate of the minimum corner p at dimension i.
• LengthsCoord(i int) float64: Returns the length of the rectangle in dimension i (q[i] - p[i]).
• Size() float64: Returns the total measure (volume/area) of the rectangle (the product of all side lengths).

rect, _ := rtreego.NewRect(rtreego.Point{0, 0}, []float64{10, 5})

fmt.Println(rect.PointCoord(0))    // 0
fmt.Println(rect.LengthsCoord(1)) // 5
fmt.Println(rect.Size())          // 50

Use Size() to get the total number of objects currently in the tree and Depth() to get the maximum depth of the tree.

count := tree.Size()
depth := tree.Depth()