Skip to content
🍀 A Quadtree implemented in Go
Go
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
LICENSE.txt
README.md
godoc.png Add nice godoc shield Sep 10, 2017
quadtree.go
quadtree_test.go

README.md

🍀 Quadtree (Go)

godoc reference

A quadtree implementation in Go, featuring insertion and retrieval of bounding boxes and points.

What is it?

"A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974." - Wikipedia (2016)



Setup

Usage

    qt := &quadtree.Quadtree{
		Bounds: quadtree.Bounds{
			X:      0,
			Y:      0,
			Width:  100,
			Height: 100,
		},
		MaxObjects: 10,
		MaxLevels:  4,
		Level:      0,
		Objects:    make([]quadtree.Bounds, 0),
		Nodes:      make([]quadtree.Quadtree, 0),
	}

    // Insert some boxes
    qt.Insert(Bounds{
		X:      1,
		Y:      1,
		Width:  10,
		Height: 10,
	})
	qt.Insert(Bounds{
		X:      5,
		Y:      5,
		Width:  10,
		Height: 10,
	})
	qt.Insert(Bounds{
		X:      10,
		Y:      10,
		Width:  10,
		Height: 10,
	})
	qt.Insert(Bounds{
		X:      15,
		Y:      15,
		Width:  10,
		Height: 10,
	})

	//Get all the intersections
	intersections := qt.RetrieveIntersections(Bounds{
		X:      5,
		Y:      5,
		Width:  2.5,
		Height: 2.5,
	})

	// Clear the Quadtree
	qt.Clear()

Acknowledgements

This package is based on Timo Hausmann JavaScript Quadtree implementation. This is in turn based on this post.

License

MIT

Original JavaScript code: Copyright © 2012 Timo Hausmann

Go code: Copyright © 2016 James Milner

You can’t perform that action at this time.