quadtree

README

go.geo/quadtree

Package quadtree implements a quadtree using rectangular partitions. Each point exists in a unique node; if multiple points are in the same position, some points may be stored on internal nodes rather than leaf nodes. This implementation is based heavily off of the d3 implementation.

Examples

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

	qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

	// insert 1000 random points
	for i := 0; i < 1000; i++ {
		qt.Insert(geo.NewPoint(r.Float64(), r.Float64()))
	}

	nearest := qt.Find(geo.NewPoint(0.5, 0.5))
	fmt.Printf("nearest: %+v\n", nearest)

	// Output:
	// nearest: POINT(0.4930591659434973 0.5196585530161364)
}

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

            qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

            // insert 1000 random points
            for i := 0; i < 1000; i++ {
                    qt.Insert(geo.NewPoint(r.Float64(), r.Float64()))
            }

            nearest := qt.FindKNearest(geo.NewPoint(0.5, 0.5), 3)
            for _, point := range nearest {
                    fmt.Printf("nearest: %+v\n", point)
            }

            // Output:
            // nearest: POINT(0.48825246346025986 0.5199222047875753)
            // nearest: POINT(0.5073640535317331 0.478560836766942)
            // nearest: POINT(0.4930591659434973 0.5196585530161364)
    }

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

	type dataPoint struct {
		geo.Pointer
		visible bool
	}

	qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

	// insert 100 random points
	for i := 0; i < 100; i++ {
		qt.Insert(dataPoint{geo.NewPoint(r.Float64(), r.Float64()), false})
	}

	qt.Insert(dataPoint{geo.NewPoint(0, 0), true})

	nearest := qt.FindMatching(
		geo.NewPoint(0.5, 0.5),
		func(p geo.Pointer) bool { return p.(dataPoint).visible },
	)

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

	// Output:
	// nearest: {Pointer:POINT(0 0) visible:true}
}

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

            type dataPoint struct {
                    geo.Pointer
                    visible bool
            }

            qt := quadtree.New(geo.NewBound(0, 1, 0, 1))
            qt.Insert(dataPoint{geo.NewPoint(0.6, 0.6), true})

            // insert 100 random points
            for i := 0; i < 100; i++ {
                    qt.Insert(dataPoint{geo.NewPoint(r.Float64(), r.Float64()), false})
            }

            qt.Insert(dataPoint{geo.NewPoint(0, 0), true})

            nearest := qt.FindKNearestMatching(
                    geo.NewPoint(0.5, 0.5),
                    3,
                    func(p geo.Pointer) bool { return p.(dataPoint).visible },
            )

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

            // Output:
            // nearest: [{Pointer:POINT(0 0) visible:true} {Pointer:POINT(0.6 0.6) visible:true}]
    }

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

	qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

	// insert 1000 random points
	for i := 0; i < 1000; i++ {
		qt.Insert(geo.NewPoint(r.Float64(), r.Float64()))
	}

	bounded := qt.InBound(geo.NewBound(0.5, 0.5, 0.5, 0.5).Pad(0.05))
	fmt.Printf("in bound: %v\n", len(bounded))
	// Output:
	// in bound: 10
}

Documentation

Overview

Package quadtree implements a quadtree using rectangular partitions. Each point exists in a unique node; if multiple points are in the same position, some points may be stored on internal nodes rather than leaf nodes. This implementation is based heavily off of the d3 implementation: https://github.com/mbostock/d3/wiki/Quadtree-Geom

Index

• Variables
• type Filter
• type Quadtree
  • func New(bound *geo.Bound, preallocateSize ...int) *Quadtree
  • func NewFromPointSet(set *geo.PointSet) *Quadtree
  • func NewFromPointers(points []geo.Pointer) *Quadtree
  • func (q *Quadtree) Bound() *geo.Bound
  • func (q *Quadtree) Find(p *geo.Point) geo.Pointer
  • func (q *Quadtree) FindKNearest(p *geo.Point, k int, maxDistance ...float64) []geo.Pointer
  • func (q *Quadtree) FindKNearestMatching(p *geo.Point, k int, f Filter, maxDistance ...float64) []geo.Pointer
  • func (q *Quadtree) FindMatching(p *geo.Point, f Filter) geo.Pointer
  • func (q *Quadtree) InBound(b *geo.Bound, buf ...[]geo.Pointer) []geo.Pointer
  • func (q *Quadtree) InBoundMatching(b *geo.Bound, f Filter, buf ...[]geo.Pointer) []geo.Pointer
  • func (q *Quadtree) Insert(p geo.Pointer) error

Examples

• Quadtree.Find
• Quadtree.FindKNearest
• Quadtree.FindKNearestMatching
• Quadtree.FindMatching
• Quadtree.InBound

Variables

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

Types

type Filter

type Filter func(p geo.Pointer) bool

A Filter is a function that returns a boolean value for a given geo.Pointer.

type Quadtree

type Quadtree struct {
	// Threshold indicates the limit of how deep the quadtree can go.
	// Points closer than this will essentially be put in the same leaf node and stop recursion.
	// The correct value depends on the use case. The default is computed
	// off the bounds to keep the tree at most 12 levels deep. So points that
	// are closer than 1/4096 * max(bound.width, bound.height) will essentially be
	// stored in the same leaf node. For optimal tree performance you want this to happen
	// sometimes but not very often.
	Threshold float64
	// contains filtered or unexported fields
}

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

func New

func New(bound *geo.Bound, preallocateSize ...int) *Quadtree

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

func NewFromPointSet

func NewFromPointSet(set *geo.PointSet) *Quadtree

NewFromPointSet creates a quadtree from a pointset. Copies the points into the quad tree. Modifying the points later will invalidate the quad tree and lead to unexpected result.

func NewFromPointers

func NewFromPointers(points []geo.Pointer) *Quadtree

NewFromPointers creates a quadtree from a set of pointers.

func (*Quadtree) Bound

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

Bound returns the bounds used for the quad tree.

func (*Quadtree) Find

func (q *Quadtree) Find(p *geo.Point) geo.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

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

qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

// insert 1000 random points
for i := 0; i < 1000; i++ {
	qt.Insert(geo.NewPoint(r.Float64(), r.Float64()))
}

nearest := qt.Find(geo.NewPoint(0.5, 0.5))
fmt.Printf("nearest: %+v\n", nearest)

Output:

nearest: POINT(0.4930591659434973 0.5196585530161364)

func (*Quadtree) FindKNearest

func (q *Quadtree) FindKNearest(p *geo.Point, k int, maxDistance ...float64) []geo.Pointer

FindKNearest returns k closest Value/Pointer in the quadtree. This function is thread safe. Multiple goroutines can read from a pre-created tree. This function allows defining a maximum distance in order to reduce search iterations.

Example

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

qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

// insert 1000 random points
for i := 0; i < 1000; i++ {
	qt.Insert(geo.NewPoint(r.Float64(), r.Float64()))
}

nearest := qt.FindKNearest(geo.NewPoint(0.5, 0.5), 3)
for _, point := range nearest {
	fmt.Printf("nearest: %+v\n", point)
}

Output:

nearest: POINT(0.48825246346025986 0.5199222047875753)
nearest: POINT(0.5073640535317331 0.478560836766942)
nearest: POINT(0.4930591659434973 0.5196585530161364)

func (*Quadtree) FindKNearestMatching

func (q *Quadtree) FindKNearestMatching(p *geo.Point, k int, f Filter, maxDistance ...float64) []geo.Pointer

FindKNearestMatching 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. This function allows defining a maximum distance in order to reduce search iterations.

Example

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

type dataPoint struct {
	geo.Pointer
	visible bool
}

qt := quadtree.New(geo.NewBound(0, 1, 0, 1))
qt.Insert(dataPoint{geo.NewPoint(0.6, 0.6), true})

// insert 100 random points
for i := 0; i < 100; i++ {
	qt.Insert(dataPoint{geo.NewPoint(r.Float64(), r.Float64()), false})
}

qt.Insert(dataPoint{geo.NewPoint(0, 0), true})

nearest := qt.FindKNearestMatching(
	geo.NewPoint(0.5, 0.5),
	3,
	func(p geo.Pointer) bool { return p.(dataPoint).visible },
)

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

Output:

nearest: [{Pointer:POINT(0 0) visible:true} {Pointer:POINT(0.6 0.6) visible:true}]

func (*Quadtree) FindMatching

func (q *Quadtree) FindMatching(p *geo.Point, f Filter) geo.Pointer

FindMatching 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

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

type dataPoint struct {
	geo.Pointer
	visible bool
}

qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

// insert 100 random points
for i := 0; i < 100; i++ {
	qt.Insert(dataPoint{geo.NewPoint(r.Float64(), r.Float64()), false})
}

qt.Insert(dataPoint{geo.NewPoint(0, 0), true})

nearest := qt.FindMatching(
	geo.NewPoint(0.5, 0.5),
	func(p geo.Pointer) bool { return p.(dataPoint).visible },
)

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

Output:

nearest: {Pointer:POINT(0 0) visible:true}

func (*Quadtree) InBound

func (q *Quadtree) InBound(b *geo.Bound, buf ...[]geo.Pointer) []geo.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

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

qt := quadtree.New(geo.NewBound(0, 1, 0, 1))

// insert 1000 random points
for i := 0; i < 1000; i++ {
	qt.Insert(geo.NewPoint(r.Float64(), r.Float64()))
}

bounded := qt.InBound(geo.NewBound(0.5, 0.5, 0.5, 0.5).Pad(0.05))
fmt.Printf("in bound: %v\n", len(bounded))

Output:

in bound: 10

func (*Quadtree) InBoundMatching

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

InBoundMatching returns a slice with all the pointers in the quadtree that are within the given bound and for which the given filter function returns true. 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) Insert

func (q *Quadtree) Insert(p geo.Pointer) error

Insert puts an object into the quad tree, must be within the quadtree bounds. If the pointer returns nil, the point will be ignored. This function is not thread-safe, ie. multiple goroutines cannot insert into a single quadtree.