rtree

README

rtree

This package provides an in-memory R-Tree implementation for Go. It's designed for Tile38 and is optimized for fast rect inserts and replacements.

Usage

Installing

To start using rtree, install Go and run go get:

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

Basic operations

// 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 interface{}) bool {
		println(data.(string)) // prints "PHX"
	},
)

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

Support for Generics (Go 1.18+)

// create a 2D RTree
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")

Support for generic numeric types, like int, float32, etc.

// create a 2D RTree
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")

Algorithms

This implementation is a variant of the original paper:
R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING

Inserting

Similar to the original algorithm. From the root to the leaf, the rects which will incur the least enlargment are chosen. Ties go to rects with the smallest area.

Added to this implementation: when a rect does not incur any enlargement at all, it's chosen immediately and without further checks on other rects in the same node. This make point insertion faster.

Deleting

Same as the original algorithm. A target rect is deleted directly. When the number of children in a rect falls below it's minumum entries, it is removed from the tree and it's items are re-inserted.

Searching

Same as the original algorithm.

Splitting

This is a custom algorithm. It attempts to minimize intensive operations such as pre-sorting the children and comparing overlaps & area sizes. The desire is to do simple single axis distance calculations each child only once, with a target 50/50 chance that the child might be moved in-memory.

When a rect has reached it's max number of entries it's largest axis is calculated and the rect is split into two smaller rects, named left and right. Each child rects is then evaluated to determine which smaller rect it should be placed into. Two values, min-dist and max-dist, are calcuated for each child.

• min-dist is the distance from the parent's minumum value of it's largest axis to the child's minumum value of the parent largest axis.
• max-dist is the distance from the parent's maximum value of it's largest axis to the child's maximum value of the parent largest axis.

When the min-dist is less than max-dist then the child is placed into the left rect. When the max-dist is less than min-dist then the child is placed into the right rect. When the min-dist is equal to max-dist then the child is placed into an equal bucket until all of the children are evaluated. Each equal rect is then one-by-one placed in either left or right, whichever has less children.

Finally, sort all the rects in the parent node of the split rect by their minimum x value.

License

rtree source code is available under the MIT License.

Documentation

Index

• func BoxDist[N numeric, T any](targetMin, targetMax [2]N, itemDist func(min, max [2]N, data T) N) (dist func(min, max [2]N, data T, item bool) N)
• type Generic
  • func (tr *Generic[T]) Copy() *Generic[T]
• type RTree
  • func (tr *RTree) Bounds() (min, max [2]float64)
  • func (tr *RTree) Children(parent interface{}, reuse []child.Child) (children []child.Child)
  • func (tr *RTree) Clear()
  • func (tr *RTree) Copy() *RTree
  • func (tr *RTree) Delete(min, max [2]float64, data interface{})
  • func (tr *RTree) Insert(min, max [2]float64, data interface{})
  • func (tr *RTree) Len() int
  • func (tr *RTree) Nearby(algo func(min, max [2]float64, data interface{}, item bool) (dist float64), ...)
  • func (tr *RTree) Replace(oldMin, oldMax [2]float64, oldData interface{}, newMin, newMax [2]float64, ...)
  • func (tr *RTree) Scan(iter func(min, max [2]float64, data interface{}) bool)
  • func (tr *RTree) Search(min, max [2]float64, iter func(min, max [2]float64, data interface{}) bool)
• type RTreeG
  • func (tr *RTreeG[T]) Bounds() (min, max [2]float64)
  • func (tr *RTreeG[T]) Clear()
  • func (tr *RTreeG[T]) Copy() *RTreeG[T]
  • func (tr *RTreeG[T]) Delete(min, max [2]float64, data T)
  • func (tr *RTreeG[T]) Insert(min, max [2]float64, data T)
  • func (tr *RTreeG[T]) Len() int
  • func (tr *RTreeG[T]) Nearby(dist func(min, max [2]float64, data T, item bool) float64, ...)
  • func (tr *RTreeG[T]) Replace(oldMin, oldMax [2]float64, oldData T, newMin, newMax [2]float64, newData T)
  • func (tr *RTreeG[T]) Scan(iter func(min, max [2]float64, data T) bool)
  • func (tr *RTreeG[T]) Search(min, max [2]float64, iter func(min, max [2]float64, data T) bool)
• type RTreeGN
  • func (tr *RTreeGN[N, T]) BottomMost() (min, max [2]N, data T)
  • func (tr *RTreeGN[N, T]) Bounds() (min, max [2]N)
  • func (tr *RTreeGN[N, T]) Clear()
  • func (tr *RTreeGN[N, T]) Copy() *RTreeGN[N, T]
  • func (tr *RTreeGN[N, T]) Delete(min, max [2]N, data T)
  • func (tr *RTreeGN[N, T]) Insert(min, max [2]N, data T)
  • func (tr *RTreeGN[N, T]) LeftMost() (min, max [2]N, data T)
  • func (tr *RTreeGN[N, T]) Len() int
  • func (tr *RTreeGN[N, T]) Nearby(dist func(min, max [2]N, data T, item bool) float64, ...)
  • func (tr *RTreeGN[N, T]) Replace(oldMin, oldMax [2]N, oldData T, newMin, newMax [2]N, newData T)
  • func (tr *RTreeGN[N, T]) RightMost() (min, max [2]N, data T)
  • func (tr *RTreeGN[N, T]) Scan(iter func(min, max [2]N, data T) bool)
  • func (tr *RTreeGN[N, T]) Search(min, max [2]N, iter func(min, max [2]N, data T) bool)
  • func (tr *RTreeGN[N, T]) TopMost() (min, max [2]N, data T)

Functions

func BoxDist

func BoxDist[N numeric, T any](targetMin, targetMax [2]N,
	itemDist func(min, max [2]N, data T) N,
) (dist func(min, max [2]N, data T, item bool) N)

BoxDist performs simple box-distance algorithm on rectangles. This is the default algorithm for Nearby.

Types

type Generic

type Generic[T any] struct {
	RTreeG[T]
}

Generic RTree Deprecated: use RTreeG

func (*Generic[T]) Copy

func (tr *Generic[T]) Copy() *Generic[T]

type RTree

type RTree struct {
	// contains filtered or unexported fields
}

func (*RTree) Bounds

func (tr *RTree) Bounds() (min, max [2]float64)

Bounds returns the minimum bounding box

func (*RTree) Children

func (tr *RTree) Children(parent interface{}, reuse []child.Child) (children []child.Child)

Children returns all children for parent node. If parent node is nil then the root nodes should be returned. The reuse buffer is an empty length slice that can optionally be used to avoid extra allocations.

func (*RTree) Clear

func (tr *RTree) Clear()

Clear will delete all items.

func (*RTree) Copy

func (tr *RTree) Copy() *RTree

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*RTree) Delete

func (tr *RTree) Delete(min, max [2]float64, data interface{})

Delete an item from the structure

func (*RTree) Insert

func (tr *RTree) Insert(min, max [2]float64, data interface{})

Insert an item into the structure

func (*RTree) Len

func (tr *RTree) Len() int

Len returns the number of items in tree

func (*RTree) Nearby

func (tr *RTree) Nearby(
	algo func(min, max [2]float64, data interface{}, item bool) (dist float64),
	iter func(min, max [2]float64, data interface{}, dist float64) bool,
)

Nearby performs a kNN-type operation on the index. It's expected that the caller provides its own the `dist` function, which is used to calculate a distance to rectangles and data. The `iter` function will return all items from the smallest distance to the largest distance.

BoxDist is included with this package for simple box-distance calculations. For example, say you want to return the closest items to Point(10 20):

tr.Nearby(
	rtree.BoxDist([2]float64{10, 20}, [2]float64{10, 20}, nil),
	func(min, max [2]float64, data int, dist float64) bool {
		return true
	},
)

func (*RTree) Replace

func (tr *RTree) Replace(
	oldMin, oldMax [2]float64, oldData interface{},
	newMin, newMax [2]float64, newData interface{},
)

Replace an item in the structure. This is effectively just a Delete followed by an Insert. But for some structures it may be possible to optimize the operation to avoid multiple passes

func (*RTree) Scan

func (tr *RTree) Scan(iter func(min, max [2]float64, data interface{}) bool)

Scan iterates through all data in tree in no specified order.

func (*RTree) Search

func (tr *RTree) Search(
	min, max [2]float64,
	iter func(min, max [2]float64, data interface{}) bool,
)

Search the structure for items that intersects the rect param

type RTreeG

type RTreeG[T any] struct {
	// contains filtered or unexported fields
}

func (*RTreeG[T]) Bounds

func (tr *RTreeG[T]) Bounds() (min, max [2]float64)

Bounds returns the minimum bounding rect

func (*RTreeG[T]) Clear

func (tr *RTreeG[T]) Clear()

Clear will delete all items.

func (*RTreeG[T]) Copy

func (tr *RTreeG[T]) Copy() *RTreeG[T]

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*RTreeG[T]) Delete

func (tr *RTreeG[T]) Delete(min, max [2]float64, data T)

Delete data from tree

func (*RTreeG[T]) Insert

func (tr *RTreeG[T]) Insert(min, max [2]float64, data T)

Insert data into tree

func (*RTreeG[T]) Len

func (tr *RTreeG[T]) Len() int

Len returns the number of items in tree

func (*RTreeG[T]) Nearby

func (tr *RTreeG[T]) Nearby(
	dist func(min, max [2]float64, data T, item bool) float64,
	iter func(min, max [2]float64, data T, dist float64) bool,
)

Nearby performs a kNN-type operation on the index. It's expected that the caller provides its own the `dist` function, which is used to calculate a distance to rectangles and data. The `iter` function will return all items from the smallest distance to the largest distance.

BoxDist is included with this package for simple box-distance calculations. For example, say you want to return the closest items to Point(10 20):

tr.Nearby(
	rtree.BoxDist([2]float64{10, 20}, [2]float64{10, 20}, nil),
	func(min, max [2]float64, data int, dist float64) bool {
		return true
	},
)

func (*RTreeG[T]) Replace

func (tr *RTreeG[T]) Replace(
	oldMin, oldMax [2]float64, oldData T,
	newMin, newMax [2]float64, newData T,
)

Replace an item. If the old item does not exist then the new item is not inserted.

func (*RTreeG[T]) Scan

func (tr *RTreeG[T]) Scan(iter func(min, max [2]float64, data T) bool)

Scan all items in the tree

func (*RTreeG[T]) Search

func (tr *RTreeG[T]) Search(min, max [2]float64,
	iter func(min, max [2]float64, data T) bool,
)

Search for items in tree that intersect the provided rectangle

type RTreeGN

type RTreeGN[N numeric, T any] struct {
	// contains filtered or unexported fields
}

func (*RTreeGN[N, T]) BottomMost

func (tr *RTreeGN[N, T]) BottomMost() (min, max [2]N, data T)

func (*RTreeGN[N, T]) Bounds

func (tr *RTreeGN[N, T]) Bounds() (min, max [2]N)

Bounds returns the minimum bounding rect

func (*RTreeGN[N, T]) Clear

func (tr *RTreeGN[N, T]) Clear()

Clear will delete all items.

func (*RTreeGN[N, T]) Copy

func (tr *RTreeGN[N, T]) Copy() *RTreeGN[N, T]

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*RTreeGN[N, T]) Delete

func (tr *RTreeGN[N, T]) Delete(min, max [2]N, data T)

Delete data from tree

func (*RTreeGN[N, T]) Insert

func (tr *RTreeGN[N, T]) Insert(min, max [2]N, data T)

Insert data into tree

func (*RTreeGN[N, T]) LeftMost

func (tr *RTreeGN[N, T]) LeftMost() (min, max [2]N, data T)

func (*RTreeGN[N, T]) Len

func (tr *RTreeGN[N, T]) Len() int

Len returns the number of items in tree

func (*RTreeGN[N, T]) Nearby

func (tr *RTreeGN[N, T]) Nearby(
	dist func(min, max [2]N, data T, item bool) float64,
	iter func(min, max [2]N, data T, dist float64) bool,
)

Nearby performs a kNN-type operation on the index. It's expected that the caller provides its own the `dist` function, which is used to calculate a distance to rectangles and data. The `iter` function will return all items from the smallest distance to the largest distance.

BoxDist is included with this package for simple box-distance calculations. For example, say you want to return the closest items to Point(10 20):

tr.Nearby(
	rtree.BoxDist([2]float64{10, 20}, [2]float64{10, 20}, nil),
	func(min, max [2]float64, data int, dist float64) bool {
		return true
	},
)

func (*RTreeGN[N, T]) Replace

func (tr *RTreeGN[N, T]) Replace(
	oldMin, oldMax [2]N, oldData T,
	newMin, newMax [2]N, newData T,
)

Replace an item. If the old item does not exist then the new item is not inserted.

func (*RTreeGN[N, T]) RightMost

func (tr *RTreeGN[N, T]) RightMost() (min, max [2]N, data T)

func (*RTreeGN[N, T]) Scan

func (tr *RTreeGN[N, T]) Scan(iter func(min, max [2]N, data T) bool)

Scane all items in the tree

func (*RTreeGN[N, T]) Search

func (tr *RTreeGN[N, T]) Search(min, max [2]N,
	iter func(min, max [2]N, data T) bool,
)

Search for items in tree that intersect the provided rectangle

func (*RTreeGN[N, T]) TopMost

func (tr *RTreeGN[N, T]) TopMost() (min, max [2]N, data T)