quadtree

Documentation

Overview

Package quadtree A Quadtree is a spatial index structure for efficient range querying

of items bounded by 2D rectangles.

Index

• Constants
• func ComputeQuadLevel(env *envelope.Envelope) int
• func EnsureExtent(itemEnv *envelope.Envelope, minExtent float64) *envelope.Envelope
• func IsZeroWidth(min, max float64) bool
• func SubnodeIndex(env *envelope.Envelope, centrex, centrey float64) int
• type IntervalSize
• type Key
  • func NewKeyEnv(itemEnv *envelope.Envelope) *Key
  • func (k *Key) Centre() matrix.Matrix
  • func (k *Key) ComputeKey(itemEnv *envelope.Envelope)
• type Node
  • func NewNode(env *envelope.Envelope) *Node
  • func NewNodeEnv(env *envelope.Envelope, level int) *Node
  • func NewNodeExpanded(node *Node, addEnv *envelope.Envelope) *Node
  • func (n *Node) Add(item interface{})
  • func (n *Node) CreateSubnode(index int) *Node
  • func (n *Node) Depth() int
  • func (n *Node) Find(searchEnv *envelope.Envelope) *Node
  • func (n *Node) GetNode(searchEnv *envelope.Envelope) *Node
  • func (n *Node) GetSubnode(index int) *Node
  • func (n *Node) HasChildren() bool
  • func (n *Node) HasItems() bool
  • func (n *Node) InsertNode(node *Node)
  • func (n *Node) IsEmpty() bool
  • func (n *Node) IsPrunable() bool
  • func (n *Node) IsSearchMatch(searchEnv *envelope.Envelope) bool
  • func (n *Node) NodeCount() int
  • func (n *Node) Remove(itemEnv *envelope.Envelope, item interface{}) bool
  • func (n *Node) Size() int
  • func (n *Node) Visit(searchEnv *envelope.Envelope, visitor index.ItemVisitor)
  • func (n *Node) VisitItems(searchEnv, nodeEnv *envelope.Envelope, visitor index.ItemVisitor)
• type Quadtree
  • func NewQuadtree() *Quadtree
  • func (q *Quadtree) CollectStats(itemEnv *envelope.Envelope)
  • func (q *Quadtree) Depth() int
  • func (q *Quadtree) Insert(itemEnv *envelope.Envelope, item interface{}) error
  • func (q *Quadtree) IsEmpty() bool
  • func (q *Quadtree) Query(searchEnv *envelope.Envelope) interface{}
  • func (q *Quadtree) QueryVisitor(searchEnv *envelope.Envelope, visitor index.ItemVisitor) error
  • func (q *Quadtree) Remove(itemEnv *envelope.Envelope, item interface{}) bool
  • func (q *Quadtree) Size() int
• type Root
  • func (r *Root) Insert(itemEnv *envelope.Envelope, item interface{})
  • func (r *Root) InsertContained(tree *Node, itemEnv *envelope.Envelope, item interface{})
  • func (r *Root) IsSearchMatch(searchEnv *envelope.Envelope) bool
  • func (r *Root) Remove(itemEnv *envelope.Envelope, item interface{}) bool
  • func (r *Root) Visit(searchEnv *envelope.Envelope, visitor index.ItemVisitor)

Constants

const MinBinaryExponent = -50

MinBinaryExponent ...

Functions

func ComputeQuadLevel

func ComputeQuadLevel(env *envelope.Envelope) int

ComputeQuadLevel ...

func EnsureExtent

func EnsureExtent(itemEnv *envelope.Envelope, minExtent float64) *envelope.Envelope

EnsureExtent Ensure that the envelope for the inserted item has non-zero extents.

Use the current minExtent to pad the envelope, if necessary

func IsZeroWidth

func IsZeroWidth(min, max float64) bool

IsZeroWidth Computes whether the interval [min, max] is effectively zero width.

I.e. the width of the interval is so much less than the
location of the interval that the midpoint of the interval cannot be
represented precisely.

func SubnodeIndex

func SubnodeIndex(env *envelope.Envelope, centrex, centrey float64) int

SubnodeIndex Gets the index of the subquad that wholly contains the given envelope. If none does, returns -1.

Types

type IntervalSize

type IntervalSize struct {
}

IntervalSize Provides a test for whether an interval is

so small it should be considered as zero for the purposes of
inserting it into a binary tree.

type Key

type Key struct {
	Pt    matrix.Matrix
	Level int
	Env   *envelope.Envelope
}

Key A Key is a unique identifier for a node in a quadtree.

It contains a lower-left point and a level number. The level number
is the power of two for the size of the node envelope

func NewKeyEnv

func NewKeyEnv(itemEnv *envelope.Envelope) *Key

NewKeyEnv ...

func (*Key) Centre

func (k *Key) Centre() matrix.Matrix

Centre ...

func (*Key) ComputeKey

func (k *Key) ComputeKey(itemEnv *envelope.Envelope)

ComputeKey return a square envelope containing the argument envelope, whose extent is a power of two and which is based at a power of 2

type Node

type Node struct {
	Items            []interface{}
	Subnode          [4]*Node
	Env              *envelope.Envelope
	Centrex, Centrey float64
	Level            int
}

Node Represents a node of a Quadtree. Nodes contain

items which have a spatial extent corresponding to the node's position in the quadtree.

func NewNode

func NewNode(env *envelope.Envelope) *Node

NewNode ...

func NewNodeEnv

func NewNodeEnv(env *envelope.Envelope, level int) *Node

NewNodeEnv ...

func NewNodeExpanded

func NewNodeExpanded(node *Node, addEnv *envelope.Envelope) *Node

NewNodeExpanded ...

func (*Node) Add

func (n *Node) Add(item interface{})

Add ...

func (*Node) CreateSubnode

func (n *Node) CreateSubnode(index int) *Node

CreateSubnode ...

func (*Node) Depth

func (n *Node) Depth() int

Depth ...

func (*Node) Find

func (n *Node) Find(searchEnv *envelope.Envelope) *Node

Find Returns the smallest existing node containing the envelope.

func (*Node) GetNode

func (n *Node) GetNode(searchEnv *envelope.Envelope) *Node

GetNode Returns the subquad containing the envelope searchEnv. Creates the subquad if it does not already exist.

func (*Node) GetSubnode

func (n *Node) GetSubnode(index int) *Node

GetSubnode get the subquad for the index. If it doesn't exist, create it

func (*Node) HasChildren

func (n *Node) HasChildren() bool

HasChildren ...

func (*Node) HasItems

func (n *Node) HasItems() bool

HasItems ...

func (*Node) InsertNode

func (n *Node) InsertNode(node *Node)

InsertNode ...

func (*Node) IsEmpty

func (n *Node) IsEmpty() bool

IsEmpty ...

func (*Node) IsPrunable

func (n *Node) IsPrunable() bool

IsPrunable ...

func (*Node) IsSearchMatch

func (n *Node) IsSearchMatch(searchEnv *envelope.Envelope) bool

IsSearchMatch ...

func (*Node) NodeCount

func (n *Node) NodeCount() int

NodeCount ...

func (*Node) Remove

func (n *Node) Remove(itemEnv *envelope.Envelope, item interface{}) bool

Remove Removes a single item from this subtree.

func (*Node) Size

func (n *Node) Size() int

Size ...

func (*Node) Visit

func (n *Node) Visit(searchEnv *envelope.Envelope, visitor index.ItemVisitor)

Visit ...

func (*Node) VisitItems

func (n *Node) VisitItems(searchEnv, nodeEnv *envelope.Envelope, visitor index.ItemVisitor)

VisitItems ...

type Quadtree

type Quadtree struct {
	Root      *Root
	MinExtent float64
}

Quadtree A Quadtree is a spatial index structure for efficient range querying

of items bounded by 2D rectangles.
Geometries can be indexed by using their Envelopes.
Any type of Object can also be indexed as
long as it has an extent that can be represented by an  Envelope.

func NewQuadtree

func NewQuadtree() *Quadtree

NewQuadtree Constructs a Quadtree with zero items.

func (*Quadtree) CollectStats

func (q *Quadtree) CollectStats(itemEnv *envelope.Envelope)

CollectStats ...

func (*Quadtree) Depth

func (q *Quadtree) Depth() int

Depth Returns the number of levels in the tree.

func (*Quadtree) Insert

func (q *Quadtree) Insert(itemEnv *envelope.Envelope, item interface{}) error

Insert insert a single item to the tree.

func (*Quadtree) IsEmpty

func (q *Quadtree) IsEmpty() bool

IsEmpty Tests whether the index contains any items.

func (*Quadtree) Query

func (q *Quadtree) Query(searchEnv *envelope.Envelope) interface{}

Query Queries the tree and returns items which may lie in the given search envelope.

func (*Quadtree) QueryVisitor

func (q *Quadtree) QueryVisitor(searchEnv *envelope.Envelope, visitor index.ItemVisitor) error

QueryVisitor Queries the tree and visits items which may lie in the given search envelope.

func (*Quadtree) Remove

func (q *Quadtree) Remove(itemEnv *envelope.Envelope, item interface{}) bool

Remove Removes a single item from the tree.

func (*Quadtree) Size

func (q *Quadtree) Size() int

Size Returns the number of items in the tree.

type Root

type Root struct {
	*Node
	// contains filtered or unexported fields
}

Root QuadRoot is the root of a single Quadtree. It is centred at the origin, and does not have a defined extent.

func (*Root) Insert

func (r *Root) Insert(itemEnv *envelope.Envelope, item interface{})

Insert an item into the quadtree this is the root of.

func (*Root) InsertContained

func (r *Root) InsertContained(tree *Node, itemEnv *envelope.Envelope, item interface{})

InsertContained insert an item which is known to be contained in the tree rooted at

the given QuadNode root.  Lower levels of the tree will be created if necessary to hold the item.

func (*Root) IsSearchMatch

func (r *Root) IsSearchMatch(searchEnv *envelope.Envelope) bool

IsSearchMatch ...

func (*Root) Remove

func (r *Root) Remove(itemEnv *envelope.Envelope, item interface{}) bool

Remove Removes a single item from this subtree.

func (*Root) Visit

func (r *Root) Visit(searchEnv *envelope.Envelope, visitor index.ItemVisitor)

Visit ...