nqueens.go

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))
}