diff options
Diffstat (limited to 'quadtree.go')
| -rw-r--r-- | quadtree.go | 546 |
1 files changed, 435 insertions, 111 deletions
diff --git a/quadtree.go b/quadtree.go index 054d9d3..22cf46c 100644 --- a/quadtree.go +++ b/quadtree.go @@ -1,11 +1,10 @@ package structs import ( - "fmt" "log" ) -// Definition of a quadtree and it's nodes recursively +// 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 @@ -16,12 +15,39 @@ type Quadtree struct { // 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 +} - // Quadrants - //northWest *Quadtree - //northEast *Quadtree - //southWest *Quadtree - //southEast *Quadtree +// 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. @@ -85,143 +111,441 @@ func (q *Quadtree) IsLeaf() { } } -// 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{}, +// 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 } - log.Printf("[+++] New Quadtree: %v", newquadtree) - return newquadtree } -// 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) - } +// 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 } +} - // 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 thee 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") +// 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 + } - // 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 + // 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 + } - // 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") + if q.noStar() == true && q.Leaf == false { + q.insertHasNoStarIsNotLeaf(point) + return + } - // 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!") + 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) + // } + // } + // } - // 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) - } +// 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 { - 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) - } + 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("[ > ] \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() - } else { - q.Quadrants[1].Insert(point) - } + 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 { - 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) - } + q.Quadrants[3].NewInsert(A) } } } - 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) + 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.Printf("[>>>] Current Star [%d]: ", i) + 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) } } - // log.Printf("[ ] Tree after insertion: %v", *q) - // q.print() -} + // retry to insert the point + q.NewInsert(point) -// print recursively prints the given quadtree -func (q *Quadtree) print() { + q.Star = Star2D{} +} - log.Printf("[ ] Beginning of the print function ") +// 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") - // iterate over all four child nodes - for i := 0; i < 4; i++ { + bx := q.Boundary.Center.X + by := q.Boundary.Center.Y + bw := q.Boundary.Width - // if the child node is no an empty tree, print it - if *q.Quadrants[i] != (Quadtree{}) { - fmt.Println(q.Quadrants[i]) + 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) + } + } - // make a recursive call on the child printing all it's quadtrees - q.Quadrants[i].print() + } 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) + } } } - log.Printf("[ ] End of the print function ") +} + +// 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 |
