1 files changed, 177 insertions, 0 deletions
diff --git a/quadtree.go b/quadtree.go
new file mode 100644
index 0000000..c799df7
--- /dev/null
+++ b/quadtree.go
@@ -0,0 +1,177 @@
+package quadtree
+
+import "fmt"
+
+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 the maxDepth is not reached...
+	if quadtree.depth < 4 {
+		// ... test if the given point is inside the one of the cells
+		// and add Insert it to that specific cell
+
+		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))
+}
+
+// Print() is a method that can be used on a quadtree.
+// It prints all the root nodes of the quadtree recursively
+// The tree is printed from the bottom up in the following order: NW, NE, SW, SE
+func (quadtree *Quadtree) Print() {
+	// Define an end condition: if the quadtree-leaf is nil, the root does not continue
+	if quadtree.northWest != nil {
+		quadtree.northWest.Print()
+	}
+	if quadtree.northEast != nil {
+		quadtree.northEast.Print()
+	}
+	if quadtree.southWest != nil {
+		quadtree.southWest.Print()
+	}
+	if quadtree.southEast != nil {
+		quadtree.southEast.Print()
+	}
+	fmt.Println(quadtree)
+}