package quadtree

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

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

Examples

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

Code:play  

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++ {
		err := qt.Add(orb.Point{r.Float64(), r.Float64()})
		if err != nil {
			panic(err)
		}
	}

	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

Code:play  

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++ {
		err := qt.Add(orb.Point{r.Float64(), r.Float64()})
		if err != nil {
			panic(err)
		}
	}

	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. The points are returned in a sorted order, nearest first. 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. The points are returned in a sorted order, nearest first. 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

Code:play  

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++ {
		err := qt.Add(dataPoint{orb.Point{r.Float64(), r.Float64()}, false})
		if err != nil {
			panic(err)
		}
	}

	err := qt.Add(dataPoint{orb.Point{0, 0}, true})
	if err != nil {
		panic(err)
	}

	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
}

Source Files

maxheap.go quadtree.go

Version
v0.9.0
Published
Feb 19, 2023
Platform
js/wasm
Imports
4 packages
Last checked
3 hours ago –

Tools for package owners.