Skip to content

Instantly share code, notes, and snippets.

@jamak
Created January 20, 2013 06:54
Show Gist options
  • Save jamak/4577051 to your computer and use it in GitHub Desktop.
Save jamak/4577051 to your computer and use it in GitHub Desktop.
package main
import (
"fmt"
/* "math/rand" */
)
const CAPACITY = 4
// a basic point struct
type Point struct {
X, Y float64
}
//axis-aligned bounding box with half-dimension and center
type AABB struct {
center, halfDimension Point
}
func construct(cen, halfD Point) AABB {
return AABB{center: cen, halfDimension: halfD}
}
func (ab *AABB) containsPoint(p Point) bool {
xRight := ab.center.X + ab.halfDimension.X
xLeft := ab.center.X - ab.halfDimension.X
yUp := ab.center.Y + ab.halfDimension.Y
yDown := ab.center.Y - ab.halfDimension.Y
return (p.X < xRight && p.X > xLeft && p.Y < yUp && p.Y > yDown)
}
func (ab *AABB) intersects(aabb AABB) bool {
xRight := ab.center.X + ab.halfDimension.X
xLeft := ab.center.X - ab.halfDimension.X
yUp := ab.center.Y + ab.halfDimension.Y
yDown := ab.center.Y - ab.halfDimension.Y
pNE := Point{xRight, yUp}
pNW := Point{xLeft, yUp}
pSE := Point{xRight, yDown}
pSW := Point{xLeft, yDown}
return aabb.containsPoint(pNE) || aabb.containsPoint(pNW) ||
aabb.containsPoint(pSE) || aabb.containsPoint(pSW) ||
aabb.containsPoint(ab.center) || ab.containsPoint(aabb.center)
}
type QuadTree struct {
//The capacity of each QT
capacity int
//The boundary of the QT
boundary AABB
//children
northWest, northEast, southWest, southEast *QuadTree
//elements in this QT
points []Point
ancestor *QuadTree
}
func (q *QuadTree) insert(p Point) bool {
if !q.boundary.containsPoint(p) {
return false
}
if len(q.points) < q.capacity && !q.hasChildren() {
q.points = append(q.points, p)
return true
}
if q.northWest == nil {
q.subdivide()
}
if q.northWest.insert(p) {
return true
}
if q.northEast.insert(p) {
return true
}
if q.southWest.insert(p) {
return true
}
if q.southEast.insert(p) {
return true
}
return false
}
//subdivides the current quadtree, redistributing the elements contained within
//q to its new subtrees
func (q *QuadTree) subdivide() {
halfHalfD := Point{X: q.boundary.halfDimension.X * 0.5, Y: q.boundary.halfDimension.Y * 0.5}
cNW := Point{q.boundary.center.X - halfHalfD.X, q.boundary.center.Y + halfHalfD.Y}
cNE := Point{q.boundary.center.X + halfHalfD.X, q.boundary.center.Y + halfHalfD.Y}
cSW := Point{q.boundary.center.X - halfHalfD.X, q.boundary.center.Y - halfHalfD.Y}
cSE := Point{q.boundary.center.X + halfHalfD.X, q.boundary.center.Y - halfHalfD.Y}
q.northWest = &QuadTree{capacity: CAPACITY, boundary: AABB{center: cNW, halfDimension: halfHalfD}}
q.northEast = &QuadTree{capacity: CAPACITY, boundary: AABB{center: cNE, halfDimension: halfHalfD}}
q.southWest = &QuadTree{capacity: CAPACITY, boundary: AABB{center: cSW, halfDimension: halfHalfD}}
q.southEast = &QuadTree{capacity: CAPACITY, boundary: AABB{center: cSE, halfDimension: halfHalfD}}
for _, point := range q.points {
q.insert(point)
}
q.points = make([]Point, len(q.points))
}
func (q QuadTree) hasChildren() bool {
return q.northWest == nil
}
func (q QuadTree) queryRange(view AABB) []Point {
t := *new([]Point)
if !q.boundary.intersects(view) {
return t
}
for _, point := range q.points {
if view.containsPoint(point) {
t = append(t, point)
}
}
if q.northWest == nil {
return t
} else {
t = append(t, q.northWest.queryRange(view)...)
t = append(t, q.northEast.queryRange(view)...)
t = append(t, q.southWest.queryRange(view)...)
t = append(t, q.southEast.queryRange(view)...)
}
return t
}
func main() {
f := *new(Point)
g := Point{X: 10, Y: 10}
view := AABB{center: f, halfDimension: g}
t := QuadTree{capacity: 4, boundary: view}
for i := 0; i < 10; i++ {
t.insert(Point{X: float64(i), Y: float64(i)})
}
d := t.queryRange(view)
fmt.Println(d, len(d))
fmt.Println(t.points, len(t.points))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment