Implemented kind of... ...everything!

1 files changed, 123 insertions, 15 deletions

diff --git a/structs/structs.go b/structs/structs.go
index ea99d96..12b208f 100644
--- a/structs/structs.go
+++ b/structs/structs.go
@@ -1,45 +1,153 @@
 package structs
 
 // coordinate type storing a position
-type coord struct {
+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}
+func NewCoord(x float64, y float64) Coord {
+	return Coord{x, y}
 }
 
-// boundingBox defines a single cell in the quadtree
-type boundingBox struct {
-	center        coord
-	halfDimension float64
-}
+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 {
 
-// containsPoint returns true if the given point is inside of the boundingBox the method is called on
-func (boundingBox *boundingBox) containsPoint(point coord) bool {
-	// find out if the point is in or outside of the box
-	if boundingBox.center.x-boundingBox.halfDimension < point.x && boundingBox.center.x+boundingBox.halfDimension > point.x {
-		if boundingBox.center.y-boundingBox.halfDimension < point.y && boundingBox.center.y+boundingBox.halfDimension > point.y {
+		// test if the point is in the right y range
+		if point.y < upperYBound && point.y > lowerYBound {
 
-			// the point is inside of the cell -> return true
+			// the star is within the bounds: return true
 			return true
 		}
 	}
 
-	// the point is outside of the cell -> return false
+	// 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 capacity, 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,
+	}
+}
+
+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, point)
 }