quadtree

README

This is an implementation of a point quadtree written in Go.

What is a quadtree?

A quadtree is an intimidating sounding name for something that's very simple.

It's used for storing coordinates ("elements") in a 2D space, and then quickly looking up those elements at a later time. Specifically, the lookups are usually things like "find all elements in a particular region" or "find all elements that are near a certain point".

How does it work?

A quadtree organizes elements that are close together into regions. The quadtree has a bucket you add elements into, but this bucket has a size limit. Once the bucket becomes full, the tree divides the region into 4 equal spaces/cells/quadrants, then distributes the elements among the quadrants.

In essence, a quadtree is using a grid to organize its elements. However, a key feature of the quadtree is that the grid doesn't need to be evenly divided up. A quadtree only subdivides a grid cell when it needs to. Some cells may be very large because there are few or no elements inside the cell. Other cells may contain many elements and have been subdivided several times.

When would I use a quadtree?

If you need to perform lookups as mentioned in the first section, then a quadtree is probably a good choice.

A good example would be a 2D RPG game. Suppose there is a spellcaster with an ability that damages enemies in an area. You could create a quadtree containing the positions of all enemies, and then query the tree to find nearby enemies. In a game with only a few enemies on the screen a quadtree would be overkill, but if there are dozens or hundreds of enemies it could be a good option.

Documentation

Index

• Constants
• type QElement
• type QTree
  • func NewQuadTree(bounds image.Rectangle, bucketSize int, maxDepth int) QTree

Constants

const (
	// DefaultBucketSize probably shouldn't be used unless you are working with small datasets.
	// See the comment for NewQuadTree.
	DefaultBucketSize = 4

	// DefaultMaxDepth is a reasonable default to use for smaller datasets. See the comment
	// for NewQuadTree.
	DefaultMaxDepth = 4
)

Types

type QElement

type QElement interface {
	// Point returns the element's coordinates.
	Point() image.Point

	// Value returns the element's value.
	Value() interface{}
}

QElement is an interface for an element in a QTree. Each element has coordinates and a value.

type QTree

type QTree interface {
	// Bounds returns the tree's boundaries.
	Bounds() image.Rectangle

	// InBounds returns whether the point could fit in the quadtree.
	InBounds(p image.Point) bool

	// Insert adds a point and value to the quad tree and returns true if it was successful.
	// A return value of false usually means the point is outside the bounds of the quad tree.
	Insert(p image.Point, val interface{}) bool

	// Select uses the given rect to search for any elements in the provided area. Returns nil
	// if no elements were found.
	Select(rect image.Rectangle) []QElement
}

QTree is an interface for a quad tree.

func NewQuadTree

func NewQuadTree(bounds image.Rectangle, bucketSize int, maxDepth int) QTree

NewQuadTree returns a new quad tree.

The bounds is the size of the quad tree space. The quad tree can only contain elements which exist within the bounds.

The bucketSize is the maximum number of elements a tree can hold before it is subdivided. A larger value for the bucketSize uses less memory but can make fine grained selecting slow. Using a value that's too small will cause the tree to become imbalanced. Suffice to say, the correct value for the bucket size is application dependent, and you will probably need to test different bucket sizes before finding a good middleground.

The maxDepth is the maximum number of times a tree can subdivide itself. This number should reflect the size of your dataset. Once a tree has hit its subdivision limit, it will continue to add elements beyond its bucketSize. If the maxDepth is too small, the elements will be contained in fewer lists, which will cause searching to act more like a linear search rather than a binary search. However, if the maxDepth is too large, it can cause problems if elements are very close together. For example, if you add several elements directly on top of each other, the tree will keep subdividing itself over and over again as it tries to make the bounds small enough. Of course, the tree will stop subdividing once it hits the maxDepth.