diff options
-rw-r--r-- | quadtree.go | 582 |
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 } |