qtree

README

QTree

This package provides an in-memory quadtree implementation for Go.

Usage

Installing

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

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

Basic operations

// create a QTree
var tr qtree.QTree

// 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")

Performance

Pretty, pretty, pretty good.

License

qtree source code is available under the MIT License.

Documentation

Index

• type QTree
  • func New(min, max [2]float64) *QTree
  • func (tr *QTree) Bounds() (min, max [2]float64)
  • func (tr *QTree) Children(parent interface{}, reuse []child.Child) (children []child.Child)
  • func (tr *QTree) Delete(min, max [2]float64, data interface{})
  • func (tr *QTree) Insert(min [2]float64, max [2]float64, data interface{})
  • func (tr *QTree) Len() int
  • func (tr *QTree) Replace(oldMin, oldMax [2]float64, oldData interface{}, newMin, newMax [2]float64, ...)
  • func (tr *QTree) Scan(iter func(min, max [2]float64, data interface{}) bool)
  • func (tr *QTree) Search(min, max [2]float64, iter func(min, max [2]float64, data interface{}) bool)

Types

type QTree

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

QTree ...

func New

func New(min, max [2]float64) *QTree

New creates a new QuadTree

func (*QTree) Bounds

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

Bounds returns the minimum bounding box

func (*QTree) Children

func (tr *QTree) 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 (*QTree) Delete

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

Delete an item from the structure

func (*QTree) Insert

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

Insert an item into the structure

func (*QTree) Len

func (tr *QTree) Len() int

Len returns the number of items in tree

func (*QTree) Replace

func (tr *QTree) 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 (*QTree) Scan

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

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

func (*QTree) Search

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

Search the structure for items that intersects the rect param