rtree

README

rtree

rtree is a high-performance go library for spatial indexing of 2D points and rectangles. It allows queries like "all items within this bounding box" very efficiently.

The library is optimized for 2D geometry using float32.

R-Trees

R-Trees are a spatial data structure in the same category as QuadTrees, k-d Trees and BSP-Trees.
However, instead of splitting the available space along an axis, R-trees put elements into hierarchical bounding boxes. While doing so, the split strategy tries to keep the area of those boxes as small as possible.
This has two implications. First, the bounding boxes are allowed to overlap. Secondly, R-trees might leave empty areas uncovered.

R-trees are dynamic data structures that guarantee a balanced search tree and are therefore ideal for dynamic geometry. In contrast to k-d and BSP-trees, which can only hold points, R-trees are designed to store rectangles and polygons without requiring additional logic.

Visualization

Inserting items

Searching and deleting items

Used Algorithms

• single insertion: non-recursive R-tree insertion with overlap minimizing split routine from R*-tree
• single deletion: non-recursive R-tree deletion using depth-first tree traversal with free-at-empty strategy (entries in underflowed nodes are not reinserted, instead underflowed nodes are kept in the tree and deleted only when empty, which is a good compromise of query vs removal performance)
• bulk loading: OMT algorithm (Overlap Minimizing Top-down Bulk Loading) for tree creation, STLT algorithm (Small-Tree-Large-Tree) for tree merging
• search: standard non-recursive R-tree search
• nearest neighbour: recursive R-tree search with sub-tree pruning using minmax-distances

Acknowledgements

Parts of this library are based on the JavaScript implementation rbush.
Certain key aspects have been changed to produce better performance in the go language and additional functionality has been added.

Documentation

Index

• type EqualsFunc
• type FilterFunc
• type Item
• type RTree
  • func New() *RTree
  • func NewConf(maxEntries int) *RTree
  • func (r *RTree) All() []Item
  • func (r *RTree) Bounds() vmath.Rectf
  • func (r *RTree) BulkLoad(items []Item) *RTree
  • func (r *RTree) Clear() *RTree
  • func (r *RTree) Height() int
  • func (r *RTree) Insert(item Item) *RTree
  • func (r *RTree) Intersects(area vmath.Rectf) bool
  • func (r *RTree) IterateInternalNodes(fn func(bounds vmath.Rectf, height int, leaf bool) bool)
  • func (r *RTree) IterateItems(fn func(item Item) bool)
  • func (r *RTree) NearestNeighbor(pos vmath.Vec2f) Item
  • func (r *RTree) NearestNeighborWithin(pos vmath.Vec2f, maxDistance float32) Item
  • func (r *RTree) Remove(item Item, equalsFn EqualsFunc) *RTree
  • func (r *RTree) Search(area vmath.Rectf, mustCover bool) []Item
  • func (r *RTree) SearchFiltered(area vmath.Rectf, mustCover bool, filter FilterFunc) []Item
  • func (r *RTree) SearchN(area vmath.Rectf, mustCover bool, maxResults int) []Item
  • func (r *RTree) SearchPos(pos vmath.Vec2f) []Item
  • func (r *RTree) SearchPosN(pos vmath.Vec2f, maxResults int) []Item
  • func (r *RTree) Size() int

Types

type EqualsFunc

type EqualsFunc func(a, b Item) bool

EqualsFunc checks if the two items are identical.

type FilterFunc

type FilterFunc func(item Item) bool

FilterFunc filters items by arbitrary properties

type Item

type Item interface {
	// Bounds returns the normalized bounding box of the item.
	Bounds() vmath.Rectf
}

type RTree

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

func New

func New() *RTree

New creates a new RTree.

func NewConf

func NewConf(maxEntries int) *RTree

NewConf creates a new RTree with the given maximum for children-per-node. Higher values mean faster insertion and slower search, and vice versa. The minimum value is 4.

func (*RTree) All

func (r *RTree) All() []Item

All returns all stored items. Returns nil if the tree is empty.

func (*RTree) Bounds

func (r *RTree) Bounds() vmath.Rectf

Bounds returns the bounding box of all items. Returns an infinitely small bounding box if there are no items.

func (*RTree) BulkLoad

func (r *RTree) BulkLoad(items []Item) *RTree

BulkLoad inserts big data sets at once.

Bulk insertion can be ~5-6 times faster than inserting items one by one. Subsequent search queries are also ~2-3 times faster.

Note that when you do bulk insertion into an existing tree, it bulk-loads the given items into a separate tree and inserts the smaller tree into the larger tree. This means that bulk insertion works very well for clustered data (where items in one update are close to each other), but makes query performance worse if the data is scattered.

func (*RTree) Clear

func (r *RTree) Clear() *RTree

Clear removes all items.

func (*RTree) Height

func (r *RTree) Height() int

Height returns the height of the R-Tree. This function is useful for graphically visualizing the R-Tree internals.

func (*RTree) Insert

func (r *RTree) Insert(item Item) *RTree

Insert adds a single item. The item's bounds must be normalized and must not change until the item is removed from the tree.

func (*RTree) Intersects

func (r *RTree) Intersects(area vmath.Rectf) bool

Intersects returns true if there are any items overlapping with the given area. Touching rectangles where floats are exactly equal are not considered to intersect.

func (*RTree) IterateInternalNodes

func (r *RTree) IterateInternalNodes(fn func(bounds vmath.Rectf, height int, leaf bool) bool)

IterateInternalNodes calls the provided function for every internal tree node until true (=abort) is returned. The order in which nodes are iterated is undefined. This function is useful for graphically visualizing the R-Tree internals.

func (*RTree) IterateItems

func (r *RTree) IterateItems(fn func(item Item) bool)

IterateAllItems calls the provided function for every stored item until true (=abort) is returned. The order in which items are iterated is undefined.

func (*RTree) NearestNeighbor

func (r *RTree) NearestNeighbor(pos vmath.Vec2f) Item

NearestNeighbor returns the item that is closest to the given position. Returns nil if the tree is empty.

func (*RTree) NearestNeighborWithin

func (r *RTree) NearestNeighborWithin(pos vmath.Vec2f, maxDistance float32) Item

NearestNeighbor returns the item that is closest to the given position but within the given max. distance. Returns nil if the tree is empty or if there are no items within the given distance.

func (*RTree) Remove

func (r *RTree) Remove(item Item, equalsFn EqualsFunc) *RTree

Remove the given item from the tree. equalsFn is optional. It is useful if you only have a copy of the originally inserted item.

func (*RTree) Search

func (r *RTree) Search(area vmath.Rectf, mustCover bool) []Item

Search returns all items within the area. If mustCover is true, items are only returned if they are fully within the search area. If false, items are returned if they intersect the search area.

func (*RTree) SearchFiltered

func (r *RTree) SearchFiltered(area vmath.Rectf, mustCover bool, filter FilterFunc) []Item

SearchFiltered returns all items within the area that are filtered. If 'filter' returns false, the item is discarded. If mustCover is true, items are only returned if they are fully within the search area. If false, items are returned if they intersect the search area.

func (*RTree) SearchN

func (r *RTree) SearchN(area vmath.Rectf, mustCover bool, maxResults int) []Item

Search returns all items within the area. Stops searching after 'maxResults' have found. If mustCover is true, items are only returned if they are fully within the search area. If false, items are returned if they intersect the search area.

func (*RTree) SearchPos

func (r *RTree) SearchPos(pos vmath.Vec2f) []Item

SearchPos returns all items at the given position.

func (*RTree) SearchPosN

func (r *RTree) SearchPosN(pos vmath.Vec2f, maxResults int) []Item

SearchPos returns all items at the given position. Stops searching after 'maxResults' have found.

func (*RTree) Size

func (r *RTree) Size() int

Size returns the total number of stored items.