quadtree

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.

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.

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.

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
}