quad

Documentation

Index

• func HasZonePrefix(zone, prefix Zone) bool
• func ZoneDepth(zone Zone) int
• type Dimension
• type Option
  • func OptCenter(center Point) Option
  • func OptHalfDimensions(halfDimensions Dimension) Option
  • func OptMaxValuesPerQuad(maxValuesPerQuad int) Option
  • func OptPreallocateValueStorage(preallocateValueStorage bool) Option
• type Options
• type Point
• type PointValue
• type Range
  • func RangeFromPoints(topLeft, bottomRight Point) Range
  • func (r *Range) Bounds() (topLeft Point, bottomRight Point)
  • func (r *Range) ContainsPoint(p Point) bool
  • func (r *Range) Intersects(other Range) bool
• type Tree
  • func New[A any](opts ...Option) *Tree[A]
  • func (qt *Tree[A]) Insert(p Point, v A) bool
  • func (qt *Tree[A]) QueryPoint(p Point) []PointValue[A]
  • func (qt *Tree[A]) QueryRange(qr Range) []PointValue[A]
  • func (qt *Tree[A]) QueryZone(zone Zone) []PointValue[A]
  • func (qt *Tree[A]) Values() (output []PointValue[A])
  • func (qt *Tree[A]) ValuesAll() (output []PointValue[A])
  • func (qt *Tree[A]) VisitDepth(fn func(*Tree[A]))
  • func (qt *Tree[A]) ZoneForPoint(p Point) (zone Zone, ok bool)
• type Zone
  • func AppendZone(parent Zone, quadrantIndex ZoneElem) Zone
  • func EncodeZone(values ...ZoneElem) (output Zone)
  • func ShiftZone(zone Zone) Zone
• type ZoneElem
  • func DecodeZone(zone Zone) (output []ZoneElem)
  • func DecodeZoneHigh(zone Zone) (output ZoneElem)

Functions

func HasZonePrefix

func HasZonePrefix(zone, prefix Zone) bool

HasZonePrefix returns if a given child exists within a given parent zone.

It should be used to figure out if a given zone matches an arbitrary prefix.

HasZonePrefix(EncodeZone(2,1,2), EncodeZone(2,1,2,3,1)) => true

func ZoneDepth

func ZoneDepth(zone Zone) int

ZoneDepth returns the depth (or the number of levels of the tree) represented by a given zone.

Types

type Dimension

type Dimension struct {
	Height, Width float64
}

Dimension is a height,width pair.

type Option

type Option func(*Options)

Option is a function that mutates QuadTreeOptions

func OptCenter

func OptCenter(center Point) Option

OptCenter sets the `Center` field on the options.

func OptHalfDimensions

func OptHalfDimensions(halfDimensions Dimension) Option

OptHalfDimensions sets the `HalfDimensions` field on the options.

func OptMaxValuesPerQuad

func OptMaxValuesPerQuad(maxValuesPerQuad int) Option

OptMaxValuesPerQuad sets the `MaxValuesPerQuad` field on the options.

func OptPreallocateValueStorage

func OptPreallocateValueStorage(preallocateValueStorage bool) Option

OptPreallocateValueStorage sets the `PreallocateValueStorage` field on the options.

type Options

type Options struct {
	MaxValuesPerQuad        int
	Center                  Point
	HalfDimensions          Dimension
	PreallocateValueStorage bool
}

Options is options for a quad tree's constructor.

type Point

type Point struct {
	X, Y float64
}

Point is an x,y pair.

type PointValue

type PointValue[A any] struct {
	Point Point
	Zone  Zone
	Value A
}

PointValue is a point with a value.

type Range

type Range struct {
	Center         Point
	HalfDimensions Dimension
}

Range is a boundary box given by a center point and dimensions.

func RangeFromPoints

func RangeFromPoints(topLeft, bottomRight Point) Range

RangeFromPoints returns a new quad range from two given points.

func (*Range) Bounds

func (r *Range) Bounds() (topLeft Point, bottomRight Point)

Bounds returns the top left and bottom right points that bound the quad range box.

func (*Range) ContainsPoint

func (r *Range) ContainsPoint(p Point) bool

ContainsPoint returns if a given bounds contains a given point.

func (*Range) Intersects

func (r *Range) Intersects(other Range) bool

Intersects returns if a given range intersects with another given range.

type Tree

type Tree[A any] struct {
	Range
	// contains filtered or unexported fields
}

Tree creates a quad tree structure to organize values with given points for fast lookups.

func New

func New[A any](opts ...Option) *Tree[A]

New returns a new QuadTree with a given set of options.

Both fields are required,

func (*Tree[A]) Insert

func (qt *Tree[A]) Insert(p Point, v A) bool

Insert adds a new point with a given value.

func (*Tree[A]) QueryPoint

func (qt *Tree[A]) QueryPoint(p Point) []PointValue[A]

QueryPoint gets all the values in the quad tree boundary as found by a single point within the smallest boundary of the tree.

func (*Tree[A]) QueryRange

func (qt *Tree[A]) QueryRange(qr Range) []PointValue[A]

QueryRange queries the tree for all points within a given range as denoted by a given QuadRange.

func (*Tree[A]) QueryZone

func (qt *Tree[A]) QueryZone(zone Zone) []PointValue[A]

QueryRange queries the tree for all points within a given range as denoted by a given QuadRange.

func (*Tree[A]) Values

func (qt *Tree[A]) Values() (output []PointValue[A])

Values yields the values in the current tree node.

func (*Tree[A]) ValuesAll

func (qt *Tree[A]) ValuesAll() (output []PointValue[A])

ValuesAll yields all the values in the tree.

func (*Tree[A]) VisitDepth

func (qt *Tree[A]) VisitDepth(fn func(*Tree[A]))

VisitDepth visits all the nodes of a quad tree in depth first order according to the z-traversal rules.

E.g we visit SW, SE, NW, NE for each node.

func (*Tree[A]) ZoneForPoint

func (qt *Tree[A]) ZoneForPoint(p Point) (zone Zone, ok bool)

ZoneForPoint gets the zone identifier for a given point.

type Zone

type Zone string

Zone is a quadrant zone identifier.

func AppendZone

func AppendZone(parent Zone, quadrantIndex ZoneElem) Zone

AppendZone adds a new index to a given parent.

It works, basically, by prepending the new quadrant on the existing parent, shifting the parent over by two bits.

func EncodeZone

func EncodeZone(values ...ZoneElem) (output Zone)

EncodeZone encodes a zone value from a given list of quadrant choices.

Quadrants are encoded according to a Z order such that - SW => A - SE => B - NW => C - NE => D

func ShiftZone

func ShiftZone(zone Zone) Zone

ShiftZone removes the top order quadrant index returning the lower order quadrant indices.

type ZoneElem

type ZoneElem rune

ZoneElem is an individual element of the zone identifier.

const (
	SW ZoneElem = 'A'
	SE ZoneElem = 'B'
	NW ZoneElem = 'C'
	NE ZoneElem = 'D'
)

func DecodeZone

func DecodeZone(zone Zone) (output []ZoneElem)

Decode zone decodes a zone value fully into a slice of "quad" choices as a query traverses the quad tree fully.

func DecodeZoneHigh

func DecodeZoneHigh(zone Zone) (output ZoneElem)

DecodeZoneHigh decodes _just_ the high order two bits of a given zone id.