quadtree

Documentation

Index

• Constants
• type Matcher
• type Node
• type QuadTree
  • func (q *QuadTree) All() []Node
  • func (q *QuadTree) Clear()
  • func (q *QuadTree) ContainedByRect(rect geom.Rect) bool
  • func (q *QuadTree) ContainsPoint(pt geom.Point) bool
  • func (q *QuadTree) ContainsRect(rect geom.Rect) bool
  • func (q *QuadTree) FindContainedByRect(rect geom.Rect) []Node
  • func (q *QuadTree) FindContainsPoint(pt geom.Point) []Node
  • func (q *QuadTree) FindContainsRect(rect geom.Rect) []Node
  • func (q *QuadTree) FindIntersects(rect geom.Rect) []Node
  • func (q *QuadTree) FindMatchedContainedByRect(matcher Matcher, rect geom.Rect) []Node
  • func (q *QuadTree) FindMatchedContainsPoint(matcher Matcher, pt geom.Point) []Node
  • func (q *QuadTree) FindMatchedContainsRect(matcher Matcher, rect geom.Rect) []Node
  • func (q *QuadTree) FindMatchedIntersects(matcher Matcher, rect geom.Rect) []Node
  • func (q *QuadTree) Insert(n Node)
  • func (q *QuadTree) Intersects(rect geom.Rect) bool
  • func (q *QuadTree) MatchedContainedByRect(matcher Matcher, rect geom.Rect) bool
  • func (q *QuadTree) MatchedContainsPoint(matcher Matcher, pt geom.Point) bool
  • func (q *QuadTree) MatchedContainsRect(matcher Matcher, rect geom.Rect) bool
  • func (q *QuadTree) MatchedIntersects(matcher Matcher, rect geom.Rect) bool
  • func (q *QuadTree) Remove(n Node)
  • func (q *QuadTree) Reorganize()
  • func (q *QuadTree) Size() int

Constants

const (
	// DefaultQuadTreeThreshold is the default threshold that will be used if
	// none is specified.
	DefaultQuadTreeThreshold = 64
	// MinQuadTreeThreshold is the minimum allowed threshold.
	MinQuadTreeThreshold = 4
)

Types

type Matcher

type Matcher interface {
	// Matches returns true if the node matches.
	Matches(n Node) bool
}

Matcher is used to match nodes.

type Node

type Node interface {
	// Bounds returns the node's bounding rectangle.
	Bounds() geom.Rect
}

Node defines the methods an object that can be stored within the QuadTree must implement.

type QuadTree

type QuadTree struct {
	Threshold int
	// contains filtered or unexported fields
}

QuadTree stores two-dimensional nodes for fast lookup.

func (*QuadTree) All

func (q *QuadTree) All() []Node

All returns all nodes.

func (*QuadTree) Clear

func (q *QuadTree) Clear()

Clear removes all nodes.

func (*QuadTree) ContainedByRect

func (q *QuadTree) ContainedByRect(rect geom.Rect) bool

ContainedByRect returns true if at least one node is contained by the rect.

func (*QuadTree) ContainsPoint

func (q *QuadTree) ContainsPoint(pt geom.Point) bool

ContainsPoint returns true if at least one node contains the point.

func (*QuadTree) ContainsRect

func (q *QuadTree) ContainsRect(rect geom.Rect) bool

ContainsRect returns true if at least one node contains the rect.

func (*QuadTree) FindContainedByRect

func (q *QuadTree) FindContainedByRect(rect geom.Rect) []Node

FindContainedByRect returns the nodes that are contained by the rect.

func (*QuadTree) FindContainsPoint

func (q *QuadTree) FindContainsPoint(pt geom.Point) []Node

FindContainsPoint returns the nodes that contain the point.

func (*QuadTree) FindContainsRect

func (q *QuadTree) FindContainsRect(rect geom.Rect) []Node

FindContainsRect returns the nodes that contain the rect.

func (*QuadTree) FindIntersects

func (q *QuadTree) FindIntersects(rect geom.Rect) []Node

FindIntersects returns the nodes that intersect the rect.

func (*QuadTree) FindMatchedContainedByRect

func (q *QuadTree) FindMatchedContainedByRect(matcher Matcher, rect geom.Rect) []Node

FindMatchedContainedByRect returns the nodes that the matcher returns true for which are contained by the rect.

func (*QuadTree) FindMatchedContainsPoint

func (q *QuadTree) FindMatchedContainsPoint(matcher Matcher, pt geom.Point) []Node

FindMatchedContainsPoint returns the nodes that the matcher returns true for which contain the point.

func (*QuadTree) FindMatchedContainsRect

func (q *QuadTree) FindMatchedContainsRect(matcher Matcher, rect geom.Rect) []Node

FindMatchedContainsRect returns the nodes that the matcher returns true for which contains the rect.

func (*QuadTree) FindMatchedIntersects

func (q *QuadTree) FindMatchedIntersects(matcher Matcher, rect geom.Rect) []Node

FindMatchedIntersects returns the nodes that the matcher returns true for which intersect the rect.

func (*QuadTree) Insert

func (q *QuadTree) Insert(n Node)

Insert a node. NOTE: Once a node is inserted, the value it returns from a call to Bounds() MUST REMAIN THE SAME until the node is removed.

func (*QuadTree) Intersects

func (q *QuadTree) Intersects(rect geom.Rect) bool

Intersects returns true if at least one node intersects the rect.

func (*QuadTree) MatchedContainedByRect

func (q *QuadTree) MatchedContainedByRect(matcher Matcher, rect geom.Rect) bool

MatchedContainedByRect returns true if at least one node that the matcher returns true for is contained by the rect.

func (*QuadTree) MatchedContainsPoint

func (q *QuadTree) MatchedContainsPoint(matcher Matcher, pt geom.Point) bool

MatchedContainsPoint returns true if at least one node that the matcher returns true for contains the point.

func (*QuadTree) MatchedContainsRect

func (q *QuadTree) MatchedContainsRect(matcher Matcher, rect geom.Rect) bool

MatchedContainsRect returns true if at least one node that the matcher returns true for contains the rect.

func (*QuadTree) MatchedIntersects

func (q *QuadTree) MatchedIntersects(matcher Matcher, rect geom.Rect) bool

MatchedIntersects returns true if at least one node that the matcher returns true for intersects the rect.

func (*QuadTree) Remove

func (q *QuadTree) Remove(n Node)

Remove a node.

func (*QuadTree) Reorganize

func (q *QuadTree) Reorganize()

Reorganize the QuadTree to optimally fit its contents.

func (*QuadTree) Size

func (q *QuadTree) Size() int

Size returns the number of nodes contained within the QuadTree.