Defined a Node

1 files changed, 7 insertions, 575 deletions

diff --git a/quadtree.go b/quadtree.go
index 22cf46c..ffb871e 100644
--- a/quadtree.go
+++ b/quadtree.go
@@ -1,581 +1,13 @@
 package structs
 
-import (
-	"log"
-)
+type Node struct {
+	Bounadry     BoundingBox // Spatial outreach of the quadtree
+	CenterOfMass Vec2        // Center of mass of the cell
+	TotalMass    float64     // Total mass of all the stars in the cell
+	Depth        int         // Depth of the cell in the tree
 
-// Quadtree defines a quadtree and it's nodes recursively
-type Quadtree struct {
-	Boundary     BoundingBox `json:"boundary"`     // Spatial outreach of the quadtree
-	CenterOfMass Vec2        `json:"CenterOfMass"` // Center of mass of the cell
-	TotalMass    float64     `json:"totalMass"`    // Total mass of the cell
-	Depth        int         `json:"depth"`        // Depth of the cell in the quadtree
-	Star         Star2D      `json:"star"`         // Star inside the cell
-	Leaf         bool        `json:"Leaf"`         // Quadtree is a leaf or not
+	Star Star2D // The actual star
 
 	// NW, NE, SW, SE
-	Quadrants [4]*Quadtree `json:"Quadrants"` // List of quadtrees representing individual Quadrants
-}
-
-type object struct {
-	position Vec2
-	mass     float64
-	size     float64
-	velocity Vec2
-}
-
-type node struct {
-	father node
-	Nodes  []*object
-}
-
-// NewQuadtree generates a new root node.
-func NewQuadtree(boundary BoundingBox) *Quadtree {
-	newquadtree := &Quadtree{
-		Boundary: BoundingBox{
-			Center: Vec2{
-				X: boundary.Center.X,
-				Y: boundary.Center.Y,
-			},
-			Width: boundary.Width,
-		},
-		CenterOfMass: Vec2{},
-		TotalMass:    0,
-		Depth:        0,
-		Star:         Star2D{},
-		Leaf:         true,
-		Quadrants:    [4]*Quadtree{},
-	}
-	log.Printf("[+++] New Quadtree: %v", newquadtree)
-	return newquadtree
-}
-
-// SetCenterOfMass is a setter method for quadtrees.
-// It sets the CenterOfMass of the quadtree to the given value
-func (q *Quadtree) SetCenterOfMass(centerOfMass Vec2) {
-	q.CenterOfMass = centerOfMass
-}
-
-// CalcCenterOfMass is a calculator method for quadtrees.
-// It recursively walks through the quadtree and calculates it's Center of mass.
-// The calculated Center of mass is then inserted into the CenterOfMass variable.
-func (q *Quadtree) CalcCenterOfMass() (Vec2, float64) {
-	var totalMass float64 = 0
-	var x float64 = 0
-	var y float64 = 0
-
-	q.IsLeaf()
-	// If the Node is a leaf
-	if q.Leaf == true {
-
-		// update the values needed to calculate the Center of mass
-		totalMass += q.Star.M
-		x += q.Star.C.X * q.Star.M
-		y += q.Star.C.X * q.Star.M
-
-		return Vec2{x, y}, totalMass
-
-	} else {
-
-		// Iterate over all the Quadrants
-		for _, element := range q.Quadrants {
-
-			// Calculate the Center of mass for each quadrant
-			centerOfMass, totalMass := element.CalcCenterOfMass()
-
-			// Update the overall CenterOfMass for the individual quadtree
-			q.CenterOfMass.X += centerOfMass.X
-			q.CenterOfMass.Y += centerOfMass.Y
-			q.TotalMass += totalMass
-		}
-	}
-
-	// Return the original CenterOfMass and totalMass
-	return q.CenterOfMass, q.TotalMass
-}
-
-// IsLeaf is a method for quadtrees returning true if the node is a leaf (has no children)
-// or returning false if the node is nor a leaf (has children).
-func (q *Quadtree) IsLeaf() {
-
-	// assume that the node is a leaf
-	q.Leaf = true
-
-	// iterate over all the elements in the quadtree (all the quadrants)
-	for _, element := range q.Quadrants {
-
-		// if one of the quadrants is not nil , the node is not a leaf
-		if element != nil {
-			q.Leaf = false
-		}
-	}
-}
-
-// Insert inserts the given point into the quadtree the method is called on
-// func (q *Quadtree) Insert(point Star2D) {
-// 	log.Printf("[   ] Inserting point %v into the tree %v", point, q)
-//
-// 	// prints the stars inside of the leaves of the current node
-// 	log.Printf("[>>>] - Current Star [node]: %v", q.Star)
-// 	for i := 0; i < 4; i++ {
-// 		if q.Quadrants[i] != nil {
-// 			log.Printf("[>>>] - Current Star [%d]: %v", i, q.Quadrants[i].Star)
-// 		} else {
-// 			log.Printf("[>>>] - Current Star [%d]: ", i)
-// 		}
-// 	}
-//
-// 	// create shortcuts for the various bounding box variables
-// 	bx := q.Boundary.Center.X
-// 	by := q.Boundary.Center.Y
-// 	bw := q.Boundary.Width
-// 	log.Printf("[ ~ ] \t Bounding Box X: %f", bx)
-// 	log.Printf("[ ~ ] \t Bounding Box Y: %f", by)
-// 	log.Printf("[ ~ ] \t Bounding Box Width: %f", bw)
-//
-// 	// Insert the given star into the tree
-// 	// Case 1: There is no star inside of the node
-// 	if q.Star == (Star2D{Vec2{}, Vec2{}, 0}) {
-// 		log.Printf("[   ] There was no star inside of the node -> inserting directly")
-// 		q.Star = point
-//
-// 		// if the star is not a leaf, try to insert the star into the correct leaf
-// 		// if there all ready is a star inside of the leaf, subdivide that leaf and insert the two nodes recursively
-// 		// into that leaf
-// 		// TODO: implement the comment above
-//
-// 	// Case 2: There is all ready a star inside of the node
-// 	} else {
-// 		log.Printf("[ ! ] There is allready a star inside of the node -> subdividing")
-//
-// 		// Test if the star is left or right of the center point
-// 		if point.C.X < bx && point.C.X > bx-bw {
-// 			log.Println("[<  ] \t\t The point is left of the center point!")
-//
-// 			// Test if the star is above or below the center point
-// 			if point.C.Y > by && point.C.Y < by+bw {
-// 				log.Println("[ ^ ] \t\t The point is above of the center point!")
-//
-// 				// Subdivide if...
-// 				// ... the quadrant does not contain a node yet or if there is all ready a node in the quadrant
-// 				// ... the quadrant is a leaf
-// 				if (q.Quadrants[0] == nil || q.Quadrants[0].Star != (Star2D{Vec2{}, Vec2{}, 0})) && q.Leaf == true {
-// 					q.subdivide()
-// 				} else {
-// 					q.Quadrants[0].Insert(point)
-// 				}
-//
-// 			} else {
-// 				log.Println("[ v ] \t\t The point is below of the center point!")
-// 				if (q.Quadrants[2] == nil || q.Quadrants[2].Star != (Star2D{Vec2{}, Vec2{}, 0})) && q.Leaf == true {
-// 					q.subdivide()
-// 				} else {
-// 					q.Quadrants[2].Insert(point)
-// 				}
-// 			}
-//
-// 		} else {
-// 			log.Println("[ > ] \t\t The point is right of the center point!")
-//
-// 			// Test if the star is above or below the center point
-// 			if point.C.Y > by && point.C.Y < by+bw {
-// 				log.Println("[ ^ ] \t\t The point is above of the center point!")
-// 				if (q.Quadrants[1] == nil || q.Quadrants[1].Star != (Star2D{Vec2{}, Vec2{}, 0})) && q.Leaf == true {
-// 					q.subdivide()
-// 					q.Quadrants[1].Insert(point)
-// 				} else {
-// 					q.Quadrants[1].Insert(point)
-// 				}
-// 			} else {
-// 				log.Println("[ v ] \t\t The point is below of the center point!")
-// 				if (q.Quadrants[3] == nil || q.Quadrants[3].Star != (Star2D{Vec2{}, Vec2{}, 0})) && q.Leaf == true {
-// 					q.subdivide()
-// 				} else {
-// 					q.Quadrants[3].Insert(point)
-// 				}
-// 			}
-// 		}
-// 	}
-//
-// 	log.Printf("[>>>] Current Star [node]: %v", q.Star)
-// 	for i := 0; i < 4; i++ {
-// 		if q.Quadrants[i] != nil {
-// 			log.Printf("[>>>] Current Star [%d]: %v", i, q.Quadrants[i].Star)
-// 		} else {
-// 			log.Printf("[>>>] Current Star [%d]: ", i)
-// 		}
-// 	}
-//
-// 	// log.Printf("[   ] Tree after insertion: %v", *q)
-// 	// q.print()
-// }
-
-// is Leaf returns true if the given node is a leaf (has no children) and false if it has children
-func (q *Quadtree) isLeaf() bool {
-	if q.Quadrants == ([4]*Quadtree{}) {
-		return true
-	} else {
-		return false
-	}
-}
-
-// noStar returns true if the current node does not contain a star and false if the node contains a star
-func (q *Quadtree) noStar() bool {
-	if q.Star == (Star2D{}) {
-		return true
-	} else {
-		return false
-	}
-}
-
-// NewInsert is a method inserting the given point (star) into the tree it is called on.
-//
-// The Method makes sure that all the points (stars) star are positioned in a leaf or get moved into a leaf
-// so if there all ready is a star (B) in the node the star should be inserted into, (B) gets moved into the
-// Leaf it belongs and the star that should be inserted gets inserted into it's place and is then shifted
-// into the right child. This is repeated, until all the stars are inside of a leaf.
-func (q *Quadtree) NewInsert(point Star2D) {
-	log.Printf("[   ] Inserting the point %v into the tree", point)
-
-	// so, using the example from the writeup, let's build this. we'll start with one of the more
-	// simple cases: we've got an empty tree with an empty node and no children.
-	// Inserting now works the following way:
-	// The star gets inserted directly into the node, it now is a leaf node, because all of it's
-	// children are non existent.
-	//
-	// Is a leaf (one of our goals \o/) and contains no star (our other goal \o/).
-	if q.noStar() == true && q.Leaf == true {
-		log.Println("[ + ] There is no other star in the node -> inserting directly")
-		q.Star = point
-		return
-	}
-
-	// Condition: cannot be inserted and into node that is a leaf because of another blocking star
-	// Solution: insert the star blocking the node into the nodes subtree and then insert the star
-	// into the nodes subtree as well, if the subtree is occupied by an other star, reinsert
-	if q.noStar() == false && q.Leaf == true {
-		q.insertHasStarIsLeaf(point)
-		return
-	}
-
-	if q.noStar() == true && q.Leaf == false {
-		q.insertHasNoStarIsNotLeaf(point)
-		return
-	}
-
-	if q.noStar() == false && q.Leaf == false {
-		q.insertHasNoStarIsNotLeaf(point)
-		return
-	}
-
-	// // Let's continue with the case above: we've now got a tree with a star (A) in the space we want
-	// // to insert the new star (B), so we need to shift (A) down into the tree and then insert (B)
-	// // into the corresponding space so long, until they both are in leaves.
-	// if q.noStar() == false {
-	//
-	// 	// We define A as the star that is all ready inside of the tree and B as the star that should
-	// 	// be inserted
-	// 	A := q.Star
-	// 	B := point
-	//
-	// 	// The if conditions below evaluate in which of the cells A is.
-	// 	// If there is no tree in that quadrant, the tree is subdivided and a 4 new quadrants are generated
-	// 	// In the end, the star is inserted into that quadrant
-	// 	if A.C.Y > by && A.C.Y < by+bw {
-	// 		if A.C.Y > bx && A.C.Y < bx+bw {
-	// 			if q.Quadrants[0] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[0].NewInsert(A)
-	// 		} else {
-	// 			if q.Quadrants[2] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[2].NewInsert(A)
-	// 		}
-	//
-	// 	} else {
-	// 		// Test if b is left or right of the x range
-	// 		if A.C.Y > bx && A.C.Y < bx+bw {
-	// 			if q.Quadrants[1] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[1].NewInsert(A)
-	// 		} else {
-	// 			if q.Quadrants[3] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[3].NewInsert(A)
-	// 		}
-	// 	}
-	//
-	// 	// So after inserting A into the tree, we still need to insert B:
-	// 	if B.C.Y > by && B.C.Y < by+bw {
-	// 		if B.C.Y > bx && B.C.Y < bx+bw {
-	// 			if q.Quadrants[0] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[0].NewInsert(B)
-	// 		} else {
-	// 			if q.Quadrants[2] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[2].NewInsert(B)
-	// 		}
-	//
-	// 	} else {
-	// 		if B.C.Y > bx && B.C.Y < bx+bw {
-	// 			if q.Quadrants[1] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[1].NewInsert(B)
-	// 		} else {
-	// 			if q.Quadrants[3] == nil {
-	// 				q.subdivide()
-	// 			}
-	// 			q.Quadrants[3].NewInsert(B)
-	// 		}
-	// 	}
-	// }
-
-}
-
-// insertHasStarIsLeaf inserts a given point into the quadtree it is called on.
-// The condition is, that the node in which the star should be inserted into already contains a star, so the
-// star that is all ready inside the node must be moved further into the tree before inserting the new star
-func (q *Quadtree) insertHasStarIsLeaf(point Star2D) {
-	q.GeneratePrintTree(0)
-
-	bx := q.Boundary.Center.X
-	by := q.Boundary.Center.Y
-	bw := q.Boundary.Width
-
-	log.Println("[ i ] Star blocking the node, but the node is a leaf")
-
-	log.Println("[   ] Subdividing the node")
-	// subdivide the node
-	q.subdivide()
-
-	log.Println("[   ] Inserting the star blocking the node into the nodes subtree")
-
-	// insert the node blocking the tree into the newly created subtree
-	A := q.Star
-	if A.C.Y > by && A.C.Y < by+bw {
-		log.Println("[<  ] \t\t The point is left of the center point!")
-		if A.C.Y > bx && A.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			if q.Quadrants[0].Star != (Star2D{}) {
-				q.Quadrants[0].insertHasStarIsLeaf(point)
-			} else {
-				q.Quadrants[0].NewInsert(A)
-			}
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			if q.Quadrants[2].Star != (Star2D{}) {
-				q.Quadrants[2].insertHasStarIsLeaf(point)
-			} else {
-				q.Quadrants[2].NewInsert(A)
-			}
-		}
-
-	} else {
-		log.Println("[ > ] \t\t The point is right of the center point!")
-		// Test if b is left or right of the x range
-		if A.C.Y > bx && A.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			if q.Quadrants[1].Star != (Star2D{}) {
-				q.Quadrants[1].insertHasStarIsLeaf(point)
-			} else {
-				q.Quadrants[1].NewInsert(A)
-			}
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			if q.Quadrants[3].Star != (Star2D{}) {
-				q.Quadrants[3].insertHasStarIsLeaf(point)
-			} else {
-				q.Quadrants[3].NewInsert(A)
-			}
-		}
-	}
-
-	log.Println("[   ] Inserting the new star into the new subtree")
-
-	// Insert the point into the newly created subtree
-	B := point
-	if B.C.Y > by && B.C.Y < by+bw {
-		log.Println("[<  ] \t\t The point is left of the center point!")
-		if B.C.Y > bx && B.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			q.Quadrants[0].NewInsert(B)
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			q.Quadrants[2].NewInsert(B)
-		}
-
-	} else {
-		log.Println("[ > ] \t\t The point is right of the center point!")
-		if B.C.Y > bx && B.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			q.Quadrants[1].NewInsert(B)
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			q.Quadrants[3].NewInsert(B)
-		}
-	}
-
-	// retry to insert the point
-	q.NewInsert(point)
-
-	q.Star = Star2D{}
-}
-
-// insertHasNoStarIsNotLeaf inserts a given point into the quadtree it is called on.
-// The condition is, that the node in which the star should be inserted into does not contain a star, but
-// also isn't a leaf.
-func (q *Quadtree) insertHasNoStarIsNotLeaf(point Star2D) {
-	log.Println("[ i ] The node does not contain a star and is not a leaf")
-
-	bx := q.Boundary.Center.X
-	by := q.Boundary.Center.Y
-	bw := q.Boundary.Width
-
-	q.GeneratePrintTree(0)
-
-	// Inserting the star into the subtree
-	// If there is all ready a star in the slot, insert that star into it's subtree and then insert the star into
-	// that subtree recursively
-	A := point
-	if A.C.Y > by && A.C.Y < by+bw {
-		log.Println("[<  ] \t\t The point is left of the center point!")
-		if A.C.Y > bx && A.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			if q.Quadrants[0].Star != (Star2D{}) {
-				q.Quadrants[0].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[0].NewInsert(A)
-			}
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			if q.Quadrants[2].Star != (Star2D{}) {
-				q.Quadrants[2].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[2].NewInsert(A)
-			}
-		}
-
-	} else {
-		log.Println("[ > ] \t\t The point is right of the center point!")
-		// Test if b is left or right of the x range
-		if A.C.Y > bx && A.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			if q.Quadrants[1].Star != (Star2D{}) {
-				q.Quadrants[1].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[1].NewInsert(A)
-			}
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			if q.Quadrants[3].Star != (Star2D{}) {
-				q.Quadrants[3].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[3].NewInsert(A)
-			}
-		}
-	}
-
-}
-
-// insertHasStarIsNotLeaf inserts a given point into the quadtree it is called on.
-// The condition is, that the node in which the star should be inserted into does contain a star, but
-// also isn't a leaf.
-func (q *Quadtree) insertHasStarIsNotLeaf(point Star2D) {
-	log.Println("[ i ] The node contains a star and is not a leaf")
-
-	bx := q.Boundary.Center.X
-	by := q.Boundary.Center.Y
-	bw := q.Boundary.Width
-
-	q.GeneratePrintTree(0)
-
-	// Inserting the star into the subtree
-	// Because of there all ready being a star in the tree, the star in the tree get's inserted into the
-	// subtree first, the point to be inserted is then also inserted into the subtree
-	A := q.Star
-	if A.C.Y > by && A.C.Y < by+bw {
-		log.Println("[<  ] \t\t The point is left of the center point!")
-		if A.C.Y > bx && A.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			if q.Quadrants[0].Star != (Star2D{}) {
-				q.Quadrants[0].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[0].NewInsert(A)
-			}
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			if q.Quadrants[2].Star != (Star2D{}) {
-				q.Quadrants[2].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[2].NewInsert(A)
-			}
-		}
-
-	} else {
-		log.Println("[ > ] \t\t The point is right of the center point!")
-		// Test if b is left or right of the x range
-		if A.C.Y > bx && A.C.Y < bx+bw {
-			log.Println("[ ^ ] \t\t The point is above of the center point!")
-			if q.Quadrants[1].Star != (Star2D{}) {
-				q.Quadrants[1].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[1].NewInsert(A)
-			}
-		} else {
-			log.Println("[ v ] \t\t The point is below of the center point!")
-			if q.Quadrants[3].Star != (Star2D{}) {
-				q.Quadrants[3].NewInsert(q.Star)
-				q.Quadrants[0].NewInsert(point)
-			} else {
-				q.Quadrants[3].NewInsert(A)
-			}
-		}
-	}
-}
-
-// subdivide subdivides the quadtree it is called on
-func (q *Quadtree) subdivide() {
-	// Toggle the leaf state: the node is not a leaf anymore
-	q.Leaf = false
-
-	// Get the "old" bounding box values
-	oldCenterX := q.Boundary.Center.X
-	oldCenterY := q.Boundary.Center.Y
-	oldWidth := q.Boundary.Width
-
-	// Calculate the bounding box values for the new quadrants
-	newCenterNorthWest := Vec2{oldCenterX - (oldWidth / 4), oldCenterY + (oldWidth / 4)}
-	newCenterNorthEast := Vec2{oldCenterX + (oldWidth / 4), oldCenterY + (oldWidth / 4)}
-	newCenterSouthWest := Vec2{oldCenterX - (oldWidth / 4), oldCenterY - (oldWidth / 4)}
-	newCenterSouthEast := Vec2{oldCenterX + (oldWidth / 4), oldCenterY - (oldWidth / 4)}
-
-	// Calculate the new width
-	newWidth := oldWidth / 2
-
-	// Define the new bounding boxes using the values calculated above
-	NorthWestBoundingBox := NewBoundingBox(newCenterNorthWest, newWidth)
-	NorthEastBoundingBox := NewBoundingBox(newCenterNorthEast, newWidth)
-	SouthWestBoundingBox := NewBoundingBox(newCenterSouthWest, newWidth)
-	SouthEastBoundingBox := NewBoundingBox(newCenterSouthEast, newWidth)
-
-	// Generate new quadrants using the new bounding boxes and assign them to the quadtree
-	q.Quadrants[0] = NewQuadtree(NorthWestBoundingBox)
-	q.Quadrants[1] = NewQuadtree(NorthEastBoundingBox)
-	q.Quadrants[2] = NewQuadtree(SouthWestBoundingBox)
-	q.Quadrants[3] = NewQuadtree(SouthEastBoundingBox)
+	Subtrees [4]*Node // The child subtrees
 }