PkgGoDev License Go Version Tag

Go Report Card Maintainability Test Coverage

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, 100, 4)

    // add some points
    tree.Add(10, 10, 5, 5, 1)
    tree.Add(15, 20, 10, 10, 2)
    tree.Add(40, 10, 4, 4, 3)
    tree.Add(90, 90, 5, 8, 4)

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

    log.Println(val) // should print 1

    const (
        searchX = 80.0
        searchY = 80.0
        distance = 20.0
        count = 2
    )

    tree.KNearest(searchX, searchY, 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

pkg: github.com/s0rg/quadtree
cpu: AMD Ryzen 5 5500U with Radeon Graphics
BenchmarkNodeInsert1-12         4119890     302.1 ns/op     139 B/op          0 allocs/op
BenchmarkNodeInsert10-12         314479      3384 ns/op    1237 B/op          0 allocs/op
BenchmarkNodeInsert100-12         33385     33683 ns/op   14128 B/op          0 allocs/op
BenchmarkNodeDel10-12             38428     49986 ns/op       0 B/op          0 allocs/op
BenchmarkNodeDel100-12            10000    647607 ns/op       0 B/op          0 allocs/op
BenchmarkNodeSearch10-12         375060      3071 ns/op       0 B/op          0 allocs/op
BenchmarkNodeSearch100-12         37975     31457 ns/op       0 B/op          0 allocs/op
BenchmarkTreeKNearest10-12       639724      1842 ns/op       0 B/op          0 allocs/op
BenchmarkTreeKNearest100-12       64370     18922 ns/op       0 B/op          0 allocs/op

GitHub

View Github