quadtree

README

quadtree

Quadtree for golang.

features

• generic
• heavy optimized
• zero-alloc
• 100% test coverage

example

import (
    "log"

    "github.com/s0rg/quadtree"
)

func main() {
    // width, height and max depth for new tree
    tree := quadtree.New[int](100.0, 100.0, 4)

    // add some points
    tree.Add(10.0, 10.0, 5.0, 5.0, 1)
    tree.Add(15.0, 20.0, 10.0, 10.0, 2)
    tree.Add(40.0, 10.0, 4.0, 4.0, 3)
    tree.Add(90.0, 90.0, 5.0, 8.0, 4)

    val, ok := tree.Get(9.0, 9.0, 11.0, 11.0)
    if !ok {
        log.Fatal("not found")
    }

    log.Println(val) // should print 1

    const (
        distance = 20.0
        count = 2
    )

    tree.KNearest(80.0, 80.0, distance, count, func(x, y, w, h float64, val int) {
        log.Printf("(%f, %f, %f, %f) = %d", x, y, w, h, val)
    })

    // output: (90.000000, 90.000000, 5.000000, 8.000000) = 4
}

benchmark

goos: linux
goarch: amd64
pkg: github.com/s0rg/quadtree
cpu: AMD Ryzen 5 5500U with Radeon Graphics
BenchmarkNode/Insert-12             14974236      71.07 ns/op       249 B/op          0 allocs/op
BenchmarkNode/Del-12                6415672       188.3 ns/op         0 B/op          0 allocs/op
BenchmarkNode/Search-12             21702474      51.83 ns/op         0 B/op          0 allocs/op
BenchmarkTree/Add-12                18840514      67.83 ns/op       241 B/op          0 allocs/op
BenchmarkTree/Get-12                21204722      55.46 ns/op         0 B/op          0 allocs/op
BenchmarkTree/Move-12               8061322       147.5 ns/op         0 B/op          0 allocs/op
BenchmarkTree/ForEach-12            18723290      58.60 ns/op         0 B/op          0 allocs/op
BenchmarkTree/KNearest-12           3595956       324.7 ns/op         0 B/op          0 allocs/op
BenchmarkTree/Del-12                6234123       193.1 ns/op         0 B/op          0 allocs/op
PASS
ok      github.com/s0rg/quadtree    12.666s

Documentation

Overview

Package quadtree is a generic, zero-alloc Quadtree.

Index

• type Iter
• type Tree
  • func New[T any](w, h float64, depth int) (rv *Tree[T])
  • func (t *Tree[T]) Add(x, y, w, h float64, value T) (ok bool)
  • func (t *Tree[T]) Del(x, y float64) (ok bool)
  • func (t *Tree[T]) ForEach(x, y, w, h float64, iter Iter[T])
  • func (t *Tree[T]) Get(x, y, w, h float64) (value T, ok bool)
  • func (t *Tree[T]) KNearest(x, y, distance float64, k int, iter Iter[T])
  • func (t *Tree[T]) Move(x, y, newX, newY float64) (ok bool)
  • func (t *Tree[T]) Size() int

Types

type Iter

type Iter[T any] func(x, y, w, h float64, value T)

Iter is a shorthand for iterator callback type.

type Tree

type Tree[T any] struct {
	// contains filtered or unexported fields
}

Tree is a quad-tree container.

func New

func New[T any](w, h float64, depth int) (rv *Tree[T])

New creates new, empty quad tree instance with given area width and height and maximum depth value.

func (*Tree[T]) Add

func (t *Tree[T]) Add(x, y, w, h float64, value T) (ok bool)

Add adds rectangle, with top-left corner at (x, y) and given width and height.

func (*Tree[T]) Del

func (t *Tree[T]) Del(x, y float64) (ok bool)

Del removes any items located at given coordinates, returns true if succeed.

func (*Tree[T]) ForEach

func (t *Tree[T]) ForEach(x, y, w, h float64, iter Iter[T])

ForEach iterates over items in given region.

func (*Tree[T]) Get

func (t *Tree[T]) Get(x, y, w, h float64) (value T, ok bool)

Get returns item located at given coordinates, if any.

func (*Tree[T]) KNearest

func (t *Tree[T]) KNearest(x, y, distance float64, k int, iter Iter[T])

KNearest iterates over k nearest for given coordinates within given distance.

func (*Tree[T]) Move

func (t *Tree[T]) Move(x, y, newX, newY float64) (ok bool)

Move moves item located at (x, y) to (newX, newY), returns true if succeed.

func (*Tree[T]) Size

func (t *Tree[T]) Size() int

Size returns current elements count.