rtree Go Package

To use the rtree package in your Go project, install it using go get:

$ go get -u github.com/tidwall/rtree

The standard rtree.RTree uses any for the data payload. You can insert points (where min and max are identical) or rectangles, and search using a callback function. Note that when using the basic RTree, you must type-assert the data parameter in your search callback.

// create a 2D RTree
var tr rtree.RTree

// insert a point
tr.Insert([2]float64{-112.0078, 33.4373}, [2]float64{-112.0078, 33.4373}, "PHX")

// insert a rect
tr.Insert([2]float64{10, 10}, [2]float64{20, 20}, "rect")

// search 
tr.Search([2]float64{-112.1, 33.4}, [2]float64{-112.0, 33.5}, 
	func(min, max [2]float64, data any) bool {
		println(data.(string)) // prints "PHX"
	},
)

// delete 
tr.Delete([2]float64{-112.0078, 33.4373}, [2]float64{-112.0078, 33.4373}, "PHX")

For maximum flexibility, rtree.RTreeGN[N, T] allows you to specify both the numeric type for coordinates (e.g., float32, int) and the type for the data payload. This is useful when working with different precision requirements or memory constraints.

// create a 2D RTree with float32 coordinates and string data
var tr rtree.RTreeGN[float32, string]

// insert a point
tr.Insert([2]float32{-112.0078, 33.4373}, [2]float32{-112.0078, 33.4373}, "PHX")

// insert a rect
tr.Insert([2]float32{10, 10}, [2]float32{20, 20}, "rect")

// search 
tr.Search([2]float32{-112.1, 33.4}, [2]float32{-112.0, 33.5}, 
	func(min, max [2]float32, data string) bool {
		println(data) // prints "PHX"
	},
)

// delete 
tr.Delete([2]float32{-112.0078, 33.4373}, [2]float32{-112.0078, 33.4373}, "PHX")

If you are using Go 1.18+, you can use rtree.RTreeG[T] to provide a type-safe data payload. This avoids the need for type assertions within your search callback function.

// create a 2D RTree with string data
var tr rtree.RTreeG[string]

// insert a point
tr.Insert([2]float64{-112.0078, 33.4373}, [2]float64{-112.0078, 33.4373}, "PHX")

// insert a rect
tr.Insert([2]float64{10, 10}, [2]float64{20, 20}, "rect")

// search 
tr.Search([2]float64{-112.1, 33.4}, [2]float64{-112.0, 33.5}, 
	func(min, max [2]float64, data string) bool {
		println(data) // prints "PHX"
	},
)

// delete 
tr.Delete([2]float64{-112.0078, 33.4373}, [2]float64{-112.0078, 33.4373}, "PHX")

You can retrieve the total number of items in the tree using Len() and the minimum bounding rectangle of all items in the tree using Bounds().

count := tree.Len()
min, max := tree.Bounds()

The RTreeG[T] type is a convenience wrapper around RTreeGN[float64, T]. Use this if you are working with standard float64 coordinates and want a simpler API without specifying the numeric type explicitly.

// Create an R-Tree for float64 coordinates and string data
tree := rtree.RTreeG[string]{}

tree.Insert([2]float64{0, 0}, [2]float64{1, 1}, "example")

The RTreeGN[N, T] type is the core generic R-Tree implementation. It allows you to create a spatial index using any numeric type N (such as int, float32, float64) for coordinates and any type T for the data being indexed. This is the most flexible way to use the library when you want to control the precision of your coordinates and the type of your data.

// Example of creating an R-Tree with float64 coordinates and string data
tree := rtree.RTreeGN[float64, string]{}

// Insert an item
tree.Insert([2]float64{0, 0}, [2]float64{1, 1}, "my-data")

The Nearby method performs a k-Nearest Neighbor type operation. It requires two functions:

1. A dist function that calculates the distance from a target to a rectangle or an item.
2. An iter function that processes results from smallest to largest distance.

For simple box-distance calculations, use the BoxDist helper.

// Example: Find items closest to a point (10, 20)
tree.Nearby(
	rtree.BoxDist([2]float64{10, 20}, [2]float64{10, 20}, nil),
	func(min, max [2]float64, data int, dist float64) bool {
		fmt.Printf("Data: %v, Distance: %v\n", data, dist)
		return true
	},
)

The RTree type is a convenience wrapper around RTreeG[any]. It is best used when the data being indexed is of an unknown or varying type (any). Note that this is a legacy/simplified wrapper.

tree := rtree.RTree{}

tree.Insert([2]float64{0, 0}, [2]float64{1, 1}, "some data")

The Scan(iter func(min, max [2]N, data T) bool) method iterates through every item in the tree in no specified order. Use this for full tree traversals.

tree.Scan(func(min, max [2]float64, data any) bool {
	fmt.Println(data)
	return true
})

The Copy() method performs a very fast, shadowed copy of the tree using a copy-on-write mechanism. This allows you to create a snapshot of the tree that can be used independently while the original tree continues to be modified.

newTree := tree.Copy()

To remove an item, use Delete(min, max [2]N, data T). If you need custom equality logic for the data type T (e.g., comparing complex structs), use DeleteEqual(min, max [2]N, keydata T, eq func(T, T) bool).

// Standard delete
tree.Delete(min, max, data)

// Delete with custom equality
tree.DeleteEqual(min, max, keydata, func(a, b T) bool {
	return a.ID == b.ID
})