quadtree

Documentation

Index

• Constants
• type Matcher
• type Node
• type QuadTree
  • func (q *QuadTree[T]) All() []Node[T]
  • func (q *QuadTree[T]) Clear()
  • func (q *QuadTree[T]) ContainedByRect(rect geom.Rect[T]) bool
  • func (q *QuadTree[T]) ContainsPoint(pt geom.Point[T]) bool
  • func (q *QuadTree[T]) ContainsRect(rect geom.Rect[T]) bool
  • func (q *QuadTree[T]) FindContainedByRect(rect geom.Rect[T]) []Node[T]
  • func (q *QuadTree[T]) FindContainsPoint(pt geom.Point[T]) []Node[T]
  • func (q *QuadTree[T]) FindContainsRect(rect geom.Rect[T]) []Node[T]
  • func (q *QuadTree[T]) FindIntersects(rect geom.Rect[T]) []Node[T]
  • func (q *QuadTree[T]) FindMatchedContainedByRect(matcher Matcher[T], rect geom.Rect[T]) []Node[T]
  • func (q *QuadTree[T]) FindMatchedContainsPoint(matcher Matcher[T], pt geom.Point[T]) []Node[T]
  • func (q *QuadTree[T]) FindMatchedContainsRect(matcher Matcher[T], rect geom.Rect[T]) []Node[T]
  • func (q *QuadTree[T]) FindMatchedIntersects(matcher Matcher[T], rect geom.Rect[T]) []Node[T]
  • func (q *QuadTree[T]) Insert(n Node[T])
  • func (q *QuadTree[T]) Intersects(rect geom.Rect[T]) bool
  • func (q *QuadTree[T]) MatchedContainedByRect(matcher Matcher[T], rect geom.Rect[T]) bool
  • func (q *QuadTree[T]) MatchedContainsPoint(matcher Matcher[T], pt geom.Point[T]) bool
  • func (q *QuadTree[T]) MatchedContainsRect(matcher Matcher[T], rect geom.Rect[T]) bool
  • func (q *QuadTree[T]) MatchedIntersects(matcher Matcher[T], rect geom.Rect[T]) bool
  • func (q *QuadTree[T]) Remove(n Node[T])
  • func (q *QuadTree[T]) Reorganize()
  • func (q *QuadTree[T]) 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[T xmath.Numeric] interface {
	// Matches returns true if the node matches.
	Matches(n Node[T]) bool
}

Matcher is used to match nodes.

type Node

type Node[T xmath.Numeric] interface {
	// Bounds returns the node's bounding rectangle.
	Bounds() geom.Rect[T]
}

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

type QuadTree

type QuadTree[T xmath.Numeric] struct {
	Threshold int
	// contains filtered or unexported fields
}

QuadTree stores two-dimensional nodes for fast lookup.

func (*QuadTree[T]) All

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

All returns all nodes.

func (*QuadTree[T]) Clear

func (q *QuadTree[T]) Clear()

Clear removes all nodes.

func (*QuadTree[T]) ContainedByRect

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

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

func (*QuadTree[T]) ContainsPoint

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

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

func (*QuadTree[T]) ContainsRect

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

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

func (*QuadTree[T]) FindContainedByRect

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

FindContainedByRect returns the nodes that are contained by the rect.

func (*QuadTree[T]) FindContainsPoint

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

FindContainsPoint returns the nodes that contain the point.

func (*QuadTree[T]) FindContainsRect

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

FindContainsRect returns the nodes that contain the rect.

func (*QuadTree[T]) FindIntersects

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

FindIntersects returns the nodes that intersect the rect.

func (*QuadTree[T]) FindMatchedContainedByRect

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

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

func (*QuadTree[T]) FindMatchedContainsPoint

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

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

func (*QuadTree[T]) FindMatchedContainsRect

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

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

func (*QuadTree[T]) FindMatchedIntersects

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

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

func (*QuadTree[T]) Insert

func (q *QuadTree[T]) Insert(n Node[T])

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[T]) Intersects

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

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

func (*QuadTree[T]) MatchedContainedByRect

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

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

func (*QuadTree[T]) MatchedContainsPoint

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

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

func (*QuadTree[T]) MatchedContainsRect

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

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

func (*QuadTree[T]) MatchedIntersects

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

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

func (*QuadTree[T]) Remove

func (q *QuadTree[T]) Remove(n Node[T])

Remove a node.

func (*QuadTree[T]) Reorganize

func (q *QuadTree[T]) Reorganize()

Reorganize the QuadTree to optimally fit its contents.

func (*QuadTree[T]) Size

func (q *QuadTree[T]) Size() int

Size returns the number of nodes contained within the QuadTree.