rtree

Documentation

Overview

Package rtree implements an in-memory r-tree data structure. This data structure can be used as a spatial index, allowing fast spatial searches based on a bounding box.

The implementation is heavily based on "R-Trees. A Dynamic Index Structure For Spatial Searching" by Antonin Guttman (which can be found at http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf).

Index

• Variables
• type Box
• type BulkItem
• type RTree
  • func BulkLoad(items []BulkItem) *RTree
  • func (t *RTree) Count() int
  • func (t *RTree) Delete(box Box, recordID int) bool
  • func (t *RTree) Extent() (Box, bool)
  • func (t *RTree) Insert(box Box, recordID int)
  • func (t *RTree) Nearest(box Box) (recordID int, found bool)
  • func (t *RTree) PrioritySearch(box Box, callback func(recordID int) error) error
  • func (t *RTree) RangeSearch(box Box, callback func(recordID int) error) error

Variables

var Stop = errors.New("stop")

Stop is a special sentinal error that can be used to stop a search operation without any error.

Types

type Box

type Box struct {
	MinX, MinY, MaxX, MaxY float64
}

Box is an axis-aligned bounding box.

type BulkItem

type BulkItem struct {
	Box      Box
	RecordID int
}

BulkItem is an item that can be inserted for bulk loading.

type RTree

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

RTree is an in-memory R-Tree data structure. It holds record ID and bounding box pairs (the actual records aren't stored in the tree; the user is responsible for storing their own records). Its zero value is an empty R-Tree.

func BulkLoad

func BulkLoad(items []BulkItem) *RTree

BulkLoad bulk loads multiple items into a new R-Tree. The bulk load operation is optimised for creating R-Trees with minimal node overlap. This allows for fast searching.

func (*RTree) Count

func (t *RTree) Count() int

Count gives the number of entries in the RTree.

func (*RTree) Delete

func (t *RTree) Delete(box Box, recordID int) bool

Delete removes a single record with a matching recordID from the RTree. The box specifies where to search in the RTree for the record (the search box must intersect with the box of the record for it to be found and deleted). The returned bool indicates whether or not the record could be found and thus removed from the RTree (true indicates success).

func (*RTree) Extent

func (t *RTree) Extent() (Box, bool)

Extent gives the Box that most closely bounds the RTree. If the RTree is empty, then false is returned.

func (*RTree) Insert

func (t *RTree) Insert(box Box, recordID int)

Insert adds a new record to the RTree.

func (*RTree) Nearest

func (t *RTree) Nearest(box Box) (recordID int, found bool)

Nearest finds the record in the RTree that is the closest to the input box as measured by the Euclidean metric. Note that there may be multiple records that are equidistant from the input box, in which case one is chosen arbitrarily. If the RTree is empty, then false is returned.

func (*RTree) PrioritySearch

func (t *RTree) PrioritySearch(box Box, callback func(recordID int) error) error

PrioritySearch iterates over the records in the RTree in priority order of distance from the input box (shortest distanace first using the Euclidean metric). The callback is called for every element iterated over. If an error is returned from the callback, then iteration stops immediately. Any error returned from the callback is returned by PrioritySearch, except for the case where the special Stop sentinal error is returned (in which case nil will be returned from PrioritySearch).

func (*RTree) RangeSearch

func (t *RTree) RangeSearch(box Box, callback func(recordID int) error) error

RangeSearch looks for any items in the tree that overlap with the given bounding box. The callback is called with the record ID for each found item. If an error is returned from the callback then the search is terminated early. Any error returned from the callback is returned by RangeSearch, except for the case where the special Stop sentinal error is returned (in which case nil will be returned from RangeSearch).