quadtree

README

orb/quadtree

Package quadtree implements a quadtree using rectangular partitions. Each point exists in a unique node. This implementation is based off of the d3 implementation.

API

func New(bound orb.Bound) *Quadtree
func (q *Quadtree) Bound() orb.Bound

func (q *Quadtree) Add(p orb.Pointer) error
func (q *Quadtree) Remove(p orb.Pointer, eq FilterFunc) bool

func (q *Quadtree) Find(p orb.Point) orb.Pointer
func (q *Quadtree) Matching(p orb.Point, f FilterFunc) orb.Pointer

func (q *Quadtree) KNearest(buf []orb.Pointer, p orb.Point, k int, maxDistance ...float64) []orb.Pointer
func (q *Quadtree) KNearestMatching(buf []orb.Pointer, p orb.Point, k int, f FilterFunc, maxDistance ...float64) []orb.Pointer

func (q *Quadtree) InBound(buf []orb.Pointer, b orb.Bound) []orb.Pointer
func (q *Quadtree) InBoundMatching(buf []orb.Pointer, b orb.Bound, f FilterFunc) []orb.Pointer

Examples

func ExampleQuadtree_Find() {
	r := rand.New(rand.NewSource(42)) // to make things reproducible

	qt := quadtree.New(orb.Bound{Min: orb.Point{0, 0}, Max: orb.Point{1, 1}})

	// add 1000 random points
	for i := 0; i < 1000; i++ {
		qt.Add(orb.Point{r.Float64(), r.Float64()})
	}

	nearest := qt.Find(orb.Point{0.5, 0.5})

	fmt.Printf("nearest: %+v\n", nearest)
	// Output:
	// nearest: [0.4930591659434973 0.5196585530161364]
}

Documentation

Overview

Package quadtree implements a quadtree using rectangular partitions. Each point exists in a unique node in the tree or as leaf nodes. This implementation is based off of the d3 implementation: https://github.com/mbostock/d3/wiki/Quadtree-Geom

Index

• Variables
• type FilterFunc
• type Quadtree
  • func New(bound orb.Bound) *Quadtree
  • func (q *Quadtree) Add(p orb.Pointer) error
  • func (q *Quadtree) Bound() orb.Bound
  • func (q *Quadtree) Find(p orb.Point) orb.Pointer
  • func (q *Quadtree) InBound(buf []orb.Pointer, b orb.Bound) []orb.Pointer
  • func (q *Quadtree) InBoundMatching(buf []orb.Pointer, b orb.Bound, f FilterFunc) []orb.Pointer
  • func (q *Quadtree) KNearest(buf []orb.Pointer, p orb.Point, k int, maxDistance ...float64) []orb.Pointer
  • func (q *Quadtree) KNearestMatching(buf []orb.Pointer, p orb.Point, k int, f FilterFunc, maxDistance ...float64) []orb.Pointer
  • func (q *Quadtree) Matching(p orb.Point, f FilterFunc) orb.Pointer
  • func (q *Quadtree) Remove(p orb.Pointer, eq FilterFunc) bool

Examples

• Quadtree.Find
• Quadtree.InBound
• Quadtree.Matching

Variables

var (
	// ErrPointOutsideOfBounds is returned when trying to add a point
	// to a quadtree and the point is outside the bounds used to create the tree.
	ErrPointOutsideOfBounds = errors.New("quadtree: point outside of bounds")
)

Types

type FilterFunc

type FilterFunc func(p orb.Pointer) bool

A FilterFunc is a function that filters the points to search for.

type Quadtree

type Quadtree struct {
	// contains filtered or unexported fields
}

Quadtree implements a two-dimensional recursive spatial subdivision of orb.Pointers. This implementation uses rectangular partitions.

func New

func New(bound orb.Bound) *Quadtree

New creates a new quadtree for the given bound. Added points must be within this bound.

func (*Quadtree) Add

func (q *Quadtree) Add(p orb.Pointer) error

Add puts an object into the quad tree, must be within the quadtree bounds. This function is not thread-safe, ie. multiple goroutines cannot insert into a single quadtree.

func (*Quadtree) Bound

func (q *Quadtree) Bound() orb.Bound

Bound returns the bounds used for the quad tree.

func (*Quadtree) Find

func (q *Quadtree) Find(p orb.Point) orb.Pointer

Find returns the closest Value/Pointer in the quadtree. This function is thread safe. Multiple goroutines can read from a pre-created tree.

Example

package main

import (
	"fmt"
	"math/rand"

	"github.com/paulmach/orb"
	"github.com/paulmach/orb/quadtree"
)

func main() {
	r := rand.New(rand.NewSource(42)) // to make things reproducible

	qt := quadtree.New(orb.Bound{Min: orb.Point{0, 0}, Max: orb.Point{1, 1}})

	// add 1000 random points
	for i := 0; i < 1000; i++ {
		qt.Add(orb.Point{r.Float64(), r.Float64()})
	}

	nearest := qt.Find(orb.Point{0.5, 0.5})
	fmt.Printf("nearest: %+v\n", nearest)

}

Output:

nearest: [0.4930591659434973 0.5196585530161364]

func (*Quadtree) InBound

func (q *Quadtree) InBound(buf []orb.Pointer, b orb.Bound) []orb.Pointer

InBound returns a slice with all the pointers in the quadtree that are within the given bound. An optional buffer parameter is provided to allow for the reuse of result slice memory. This function is thread safe. Multiple goroutines can read from a pre-created tree.

Example

package main

import (
	"fmt"
	"math/rand"

	"github.com/paulmach/orb"
	"github.com/paulmach/orb/quadtree"
)

func main() {
	r := rand.New(rand.NewSource(52)) // to make things reproducible

	qt := quadtree.New(orb.Bound{Min: orb.Point{0, 0}, Max: orb.Point{1, 1}})

	// add 1000 random points
	for i := 0; i < 1000; i++ {
		qt.Add(orb.Point{r.Float64(), r.Float64()})
	}

	bounded := qt.InBound(nil, orb.Point{0.5, 0.5}.Bound().Pad(0.05))
	fmt.Printf("in bound: %v\n", len(bounded))

}

Output:

in bound: 10

func (*Quadtree) InBoundMatching

func (q *Quadtree) InBoundMatching(buf []orb.Pointer, b orb.Bound, f FilterFunc) []orb.Pointer

InBoundMatching returns a slice with all the pointers in the quadtree that are within the given bound and matching the give filter function. An optional buffer parameter is provided to allow for the reuse of result slice memory. This function is thread safe. Multiple goroutines can read from a pre-created tree.

func (*Quadtree) KNearest

func (q *Quadtree) KNearest(buf []orb.Pointer, p orb.Point, k int, maxDistance ...float64) []orb.Pointer

KNearest returns k closest Value/Pointer in the quadtree. This function is thread safe. Multiple goroutines can read from a pre-created tree. An optional buffer parameter is provided to allow for the reuse of result slice memory. This function allows defining a maximum distance in order to reduce search iterations.

func (*Quadtree) KNearestMatching

func (q *Quadtree) KNearestMatching(buf []orb.Pointer, p orb.Point, k int, f FilterFunc, maxDistance ...float64) []orb.Pointer

KNearestMatching returns k closest Value/Pointer in the quadtree for which the given filter function returns true. This function is thread safe. Multiple goroutines can read from a pre-created tree. An optional buffer parameter is provided to allow for the reuse of result slice memory. This function allows defining a maximum distance in order to reduce search iterations.

func (*Quadtree) Matching

func (q *Quadtree) Matching(p orb.Point, f FilterFunc) orb.Pointer

Matching returns the closest Value/Pointer in the quadtree for which the given filter function returns true. This function is thread safe. Multiple goroutines can read from a pre-created tree.

Example

package main

import (
	"fmt"
	"math/rand"

	"github.com/paulmach/orb"
	"github.com/paulmach/orb/quadtree"
)

func main() {
	r := rand.New(rand.NewSource(42)) // to make things reproducible

	type dataPoint struct {
		orb.Pointer
		visible bool
	}

	qt := quadtree.New(orb.Bound{Min: orb.Point{0, 0}, Max: orb.Point{1, 1}})

	// add 100 random points
	for i := 0; i < 100; i++ {
		qt.Add(dataPoint{orb.Point{r.Float64(), r.Float64()}, false})
	}

	qt.Add(dataPoint{orb.Point{0, 0}, true})

	nearest := qt.Matching(
		orb.Point{0.5, 0.5},
		func(p orb.Pointer) bool { return p.(dataPoint).visible },
	)

	fmt.Printf("nearest: %+v\n", nearest)

}

Output:

nearest: {Pointer:[0 0] visible:true}

func (*Quadtree) Remove

func (q *Quadtree) Remove(p orb.Pointer, eq FilterFunc) bool

Remove will remove the pointer from the quadtree. By default it'll match using the points, but a FilterFunc can be provided for a more specific test if there are elements with the same point value in the tree. For example:

func(pointer orb.Pointer) {
	return pointer.(*MyType).ID == lookingFor.ID
}