ptree

package module
Version: v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 27, 2021 License: MIT Imports: 2 Imported by: 1

README

ptree

GoDoc

This package provides an in-memory data structure for storing points.

Under the hood it stores points in a tree structure where nodes are spatially split evenly over a 16x16 grid and leaf nodes hold up to 256 points each.

Cities

It has an api that works a lot like the tidwall/rtree library, but ptree is limited to only storing point while rtree can store points and rectangles. It's also structurally closer to an quadtree than an rtree.

Here's what the R-tree looks like in comparison

Cities

Performance

The following benchmark inserts 1,000,000 random points, searches for each point, and then deletes each point.

P-tree

insert:  1,000,000 ops in 225ms, 4,449,671/sec, 224 ns/op
search:  1,000,000 ops in 287ms, 3,485,059/sec, 286 ns/op
delete:  1,000,000 ops in 220ms, 4,545,320/sec, 220 ns/op

R-tree

insert:  1,000,000 ops in 645ms, 1,551,015/sec, 644 ns/op
search:  1,000,000 ops in 612ms, 1,634,557/sec, 611 ns/op
delete:  1,000,000 ops in 974ms, 1,026,674/sec, 974 ns/op

MacBook Pro 15" 2.8 GHz Intel Core i7

License

ptree source code is available under the MIT License.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type PTree

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

PTree is a tree for storing points.

func New

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

New returns a new PTree with the provided maximum bounding rectangle.

func (*PTree) Children

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

func (tr *PTree) Delete(point [2]float64, data interface{})

Delete a point for the tree

func (*PTree) InBounds

func (tr *PTree) InBounds(point [2]float64) bool

InBounds return true if the point can be contained in the tree's maximum bounding rectangle.

func (*PTree) Insert

func (tr *PTree) Insert(point [2]float64, data interface{})

Insert a point into the tree.

func (*PTree) Len

func (tr *PTree) Len() int

Len returns the number of points in the tree

func (*PTree) MinBounds

func (tr *PTree) MinBounds() (min, max [2]float64)

MinBounds returns the minumum bounding rectangle of the tree.

func (*PTree) Scan

func (tr *PTree) Scan(iter func(point [2]float64, data interface{}) bool)

Scan all items in tree

func (*PTree) Search

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

Search for points in the tree that are within the provided rectangle.

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL