path: root/quadtree.go

package quadtree

import (
	"fmt"
	"git.darknebu.la/GalaxySimulator/Source/structs"

	//"git.darknebu.la/GalaxySimulator/Source/structs"
	"github.com/fogleman/gg"
)

type Coord struct {
	X float64
	Y float64
}

// newCoord returns a new coordinate using the given values
func NewCoord(x float64, y float64) Coord {
	return Coord{x, y}
}

// InsideOf returns true if the point the method is used on in inside of the quadtreecell
func (point Coord) InsideOf(quadtreeCell *Quadtree) bool {
	// define the bounds
	var lowerXBound = quadtreeCell.boundary.center.X - quadtreeCell.boundary.halfDimension
	var upperXBound = quadtreeCell.boundary.center.X + quadtreeCell.boundary.halfDimension
	var lowerYBound = quadtreeCell.boundary.center.Y - quadtreeCell.boundary.halfDimension
	var upperYBound = quadtreeCell.boundary.center.Y + quadtreeCell.boundary.halfDimension

	// if the point is in the right x range
	if point.X < upperXBound && point.X > lowerXBound {

		// test if the point is in the right y range
		if point.Y < upperYBound && point.Y > lowerYBound {

			// the star is within the bounds: return true
			return true
		}
	}

	// the star is outside of the bounds: return false
	return false
}

// BoundingBox defines a single cell in the Quadtree
type BoundingBox struct {
	center        Coord
	halfDimension float64
}

// NewBoundingBox returns a new bounding with the given struct elements
func NewBoundingBox(inCenter Coord, inHalfDimension float64) BoundingBox {
	return BoundingBox{
		center:        inCenter,
		halfDimension: inHalfDimension,
	}
}

// Quadtree defining the whole Quadtree and a node in itself (recursively)
type Quadtree struct {
	// general information (node ca/home/hanemile/go/src/git.darknebu.la/emile/quadtreepacity, spacial outreach)
	nodeCapacity int
	boundary     BoundingBox

	// slice storing the star coordinates
	pointsSlice []Coord

	// the Quadtree leaves
	northWest *Quadtree
	northEast *Quadtree
	southWest *Quadtree
	southEast *Quadtree

	depth int
}

// NewQuadtree returns a new Quadtree
func NewQuadtree(boundary BoundingBox, depth int) *Quadtree {
	return &Quadtree{
		nodeCapacity: 0,
		boundary:     boundary,
		pointsSlice:  nil,
		northWest:    nil,
		northEast:    nil,
		southWest:    nil,
		southEast:    nil,
		depth:        depth,
	}
}

// Subdvide the given quadtree into multiple cells
func (quadtree *Quadtree) subdivide() {

	// Create the new NorthWest boundingbox
	var newCellBoundingNorthWest = BoundingBox{
		center: Coord{
			X: quadtree.boundary.center.X - quadtree.boundary.halfDimension/2,
			Y: quadtree.boundary.center.Y + quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.northWest = NewQuadtree(newCellBoundingNorthWest, quadtree.depth+1)

	// Create the new NorthWest boundingbox
	var newCellBoundingNorthEast = BoundingBox{
		center: Coord{
			X: quadtree.boundary.center.X + quadtree.boundary.halfDimension/2,
			Y: quadtree.boundary.center.Y + quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.northEast = NewQuadtree(newCellBoundingNorthEast, quadtree.depth+1)

	// Create the new NorthWest boundingbox
	var newCellBoundingSouthWest = BoundingBox{
		center: Coord{
			X: quadtree.boundary.center.X - quadtree.boundary.halfDimension/2,
			Y: quadtree.boundary.center.Y - quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.southWest = NewQuadtree(newCellBoundingSouthWest, quadtree.depth+1)

	// Create the new NorthWest boundingbox
	var newCellBoundingSouthEast = BoundingBox{
		center: Coord{
			X: quadtree.boundary.center.X + quadtree.boundary.halfDimension/2,
			Y: quadtree.boundary.center.Y - quadtree.boundary.halfDimension/2,
		},
		halfDimension: quadtree.boundary.halfDimension / 2,
	}
	quadtree.southEast = NewQuadtree(newCellBoundingSouthEast, quadtree.depth+1)
}

// Insert inserts the given point into the Quadtree the method is applied on
// it returns an error incase the point is not in bounds
func (quadtree *Quadtree) Insert(point Coord) {

	// subdivide the Quadtree into four new cells
	quadtree.subdivide()

	if point.InsideOf(quadtree.northWest) {
		quadtree.northWest.Insert(point)
	}
	if point.InsideOf(quadtree.northEast) {
		quadtree.northEast.Insert(point)
	}
	if point.InsideOf(quadtree.southWest) {
		quadtree.southWest.Insert(point)
	}
	if point.InsideOf(quadtree.southEast) {
		quadtree.southEast.Insert(point)
	}

	// if the maximal depth of the tree has been reached:
	// Insert the point into the slice
	quadtree.pointsSlice = append(quadtree.pointsSlice, NewCoord(point.X, point.Y))
	fmt.Printf("Inserted (%f, %f) in layer %d\n", point.X, point.Y, quadtree.depth)
}

func Print(quadtree *Quadtree) {
	// Define an end condition: if the quadtree-leaf is nil, the root does not continue
	if quadtree.northWest != nil {
		Print(quadtree.northWest)
	}
	if quadtree.northEast != nil {
		Print(quadtree.northEast)
	}
	if quadtree.southWest != nil {
		Print(quadtree.southWest)
	}
	if quadtree.southEast != nil {
		Print(quadtree.southEast)
	}
	fmt.Printf("%d\t", quadtree.depth)
	fmt.Printf("%v\t", quadtree.boundary)
	fmt.Printf("%d\n", len(quadtree.pointsSlice))
}

func CreateWithSlice(slice []structs.Star2D) Quadtree {
	// Create a new bounding box at the center of the Galaxy containing the whole galaxy
	var newCenter structs.Vec2 = structs.Vec2{0, 0}
	var newHalfDimension float64 = 5e5

	// Create a Quadtree containing the whole galaxy
	var boundary BoundingBox = NewBoundingBox(Coord(newCenter), newHalfDimension)
	var depth int = 0
	var newQuadtree *Quadtree = NewQuadtree(boundary, depth)

	fmt.Printf("Inserting %d Elements into the Quadtree\n", len(slice))

	// Insert all the stars from the slice into the quadtree step for step
	for i := 0; i < len(slice); i++ {
		newQuadtree.Insert(Coord(slice[i].C))
	}

	return *newQuadtree
}

func InitializeCanvas() *gg.Context {
	const imageWidth = 8192
	const imageHeight = 8192

	// Initialize the new Context
	dc := gg.NewContext(imageWidth, imageHeight)

	// Set the Background to black
	dc.SetRGB(0, 0, 0)
	dc.Clear()

	// Invert the Y axis
	dc.InvertY()

	// Translate the Coordinate System to the middle of the image
	dc.TransformPoint(imageWidth/4, imageHeight/4)

	return dc
}

// recursively iterate over a quadtree and draw all the nodes
func drawQuadTree(dc *gg.Context, quadtree Quadtree) {

	// find filled quadtrees
	if quadtree.northWest != nil {
		drawQuadTree(dc, *quadtree.northWest)
	}
	if quadtree.northEast != nil {
		drawQuadTree(dc, *quadtree.northEast)
	}
	if quadtree.southWest != nil {
		drawQuadTree(dc, *quadtree.southWest)
	}
	if quadtree.southEast != nil {
		drawQuadTree(dc, *quadtree.southEast)
	}

	// don't draw the root node
	if quadtree.depth != 0 {

		// calculate the position of the new rectangle
		origx := quadtree.boundary.center.X
		origy := quadtree.boundary.center.X
		x := (origx - quadtree.boundary.halfDimension) / 1000
		y := (origy - quadtree.boundary.halfDimension) / 1000
		w := quadtree.boundary.halfDimension
		h := quadtree.boundary.halfDimension
		//fmt.Printf("(%f, %f), (%f, %f, %f, %f)\n", origx, origy, x, y, w, h)

		// draw the rectangle
		dc.DrawRectangle(x, y, w, h)
		dc.Stroke()
	}
}

// save the given gg.Context to the given path
func saveImage(dc *gg.Context, path string) {
	err := dc.SavePNG(path)
	if err != nil {
		panic(err)
	}
}

func DrawQuadtree(quadtree Quadtree) {
	dc := InitializeCanvas()

	dc.SetRGB(1, 1, 1)
	drawQuadTree(dc, quadtree)
	saveImage(dc, "quadtree.png")
}