rbang

README

R!tree

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 R!Tree, install Go and run go get:

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

Basic operations

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

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

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

// delete 
tr.Delete([2]float64{-112.0078, 33.4373}, [2]float64{-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

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

Deleting

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

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 box has reached it's max number of entries it's largest axis is calculated and the box is split into two smaller boxes, named left and right. Each child boxes is then evaluated to determine which smaller box 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 box. When the max-dist is less than min-dist then the child is placed into the right box. 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 box is then one-by-one placed in either left or right, whichever has less children.

Performance

In my testing:

• Insert show similar performance as the quadratic R-tree and ~1.2x - 1.5x faster than R*tree.
• Search and Delete is ~1.5x - 2x faster than quadratic and about the same as R*tree.

I hope to provide more details in the future.

License

rbang source code is available under the MIT License.

Documentation

Index

• type RTree
  • func (tr *RTree) Bounds() (min, max [2]float64)
  • func (tr *RTree) Children(parent interface{}, reuse []child.Child) []child.Child
  • func (tr *RTree) Delete(min, max [2]float64, data interface{})
  • func (tr *RTree) Insert(min, max [2]float64, value interface{})
  • func (tr *RTree) Len() int
  • 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, value interface{}) bool)

Types

type RTree

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

RTree ...

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,
) []child.Child

Children is a utility function that returns all children for parent node. If parent node is nil then the root nodes should be returned. The min, max, data, and items slices all must have the same lengths. And, each element from all slices must be associated. Returns true for `items` when the the item at the leaf level. The reuse buffers are empty length slices that can optionally be used to avoid extra allocations.

func (*RTree) Delete

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

Delete data from tree

func (*RTree) Insert

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

Insert inserts an item into the RTree

func (*RTree) Len

func (tr *RTree) Len() int

Len returns the number of items in tree

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.

func (*RTree) Scan

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

Scan iterates through all data in tree.

func (*RTree) Search

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

Search ...