quadtree

package
v0.0.0-...-516b90f Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 30, 2018 License: MIT Imports: 4 Imported by: 0

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

Examples

Constants

This section is empty.

Variables

View Source 
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")
)

Functions

This section is empty.

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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.