quadtree

Documentation

Index

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

Matcher is used to match nodes.

type Node

type Node[T xmath.Numeric] interface {
	comparable
	// 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, N Node[T]] struct {
	Threshold int
	// contains filtered or unexported fields
}

QuadTree stores two-dimensional nodes for fast lookup.

func (*QuadTree[T, N]) All

func (q *QuadTree[T, N]) All() []N

All returns all nodes.

func (*QuadTree[T, N]) Clear

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

Clear removes all nodes.

func (*QuadTree[T, N]) ContainedByRect

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

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

func (*QuadTree[T, N]) ContainsPoint

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

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

func (*QuadTree[T, N]) ContainsRect

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

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

func (*QuadTree[T, N]) FindContainedByRect

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

FindContainedByRect returns the nodes that are contained by the rect.

func (*QuadTree[T, N]) FindContainsPoint

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

FindContainsPoint returns the nodes that contain the point.

func (*QuadTree[T, N]) FindContainsRect

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

FindContainsRect returns the nodes that contain the rect.

func (*QuadTree[T, N]) FindIntersects

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

FindIntersects returns the nodes that intersect the rect.

func (*QuadTree[T, N]) FindMatchedContainedByRect

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

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

func (*QuadTree[T, N]) FindMatchedContainsPoint

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

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

func (*QuadTree[T, N]) FindMatchedContainsRect

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

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

func (*QuadTree[T, N]) FindMatchedIntersects

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

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

func (*QuadTree[T, N]) Insert

func (q *QuadTree[T, N]) Insert(n N)

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, N]) Intersects

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

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

func (*QuadTree[T, N]) MatchedContainedByRect

func (q *QuadTree[T, N]) MatchedContainedByRect(matcher Matcher[T, N], 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, N]) MatchedContainsPoint

func (q *QuadTree[T, N]) MatchedContainsPoint(matcher Matcher[T, N], 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, N]) MatchedContainsRect

func (q *QuadTree[T, N]) MatchedContainsRect(matcher Matcher[T, N], 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, N]) MatchedIntersects

func (q *QuadTree[T, N]) MatchedIntersects(matcher Matcher[T, N], 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, N]) Remove

func (q *QuadTree[T, N]) Remove(n N)

Remove a node.

func (*QuadTree[T, N]) Reorganize

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

Reorganize the QuadTree to optimally fit its contents.

func (*QuadTree[T, N]) Size

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

Size returns the number of nodes contained within the QuadTree.