diff options
| -rw-r--r-- | quadtree.go | 177 |
1 files changed, 169 insertions, 8 deletions
diff --git a/quadtree.go b/quadtree.go index e120904..9a7d658 100644 --- a/quadtree.go +++ b/quadtree.go @@ -1,5 +1,9 @@ package structs +import ( + "log" +) + // Definition of a quadtree and it's nodes recursively type Quadtree struct { Boundary BoundingBox `json:"boundary"` // Spatial outreach of the quadtree @@ -7,9 +11,10 @@ type Quadtree struct { 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 // NW, NE, SW, SE - Quadrants []*Quadtree `json:"Quadrants"` // List of quadtrees representing individual Quadrants + Quadrants [4]*Quadtree `json:"Quadrants"` // List of quadtrees representing individual Quadrants // Quadrants //northWest *Quadtree @@ -32,8 +37,9 @@ func (q *Quadtree) CalcCenterOfMass() (Vec2, float64) { var x float64 = 0 var y float64 = 0 + q.IsLeaf() // If the Node is a leaf - if q.IsLeaf() == true { + if q.Leaf == true { // update the values needed to calculate the Center of mass totalMass += q.Star.M @@ -63,16 +69,171 @@ func (q *Quadtree) CalcCenterOfMass() (Vec2, float64) { // 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() bool { +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 element == nil { - return true + + // if one of the quadrants is not nil , the node is not a leaf + if element != nil { + q.Leaf = false } } - return false } // NewQuadtree generates a new root node. -func NewQuadtree(boundary BoundingBox) Quadtree { - return Quadtree{Boundary: boundary} +func NewQuadtree(boundary BoundingBox) *Quadtree { + //newquadtree := &Quadtree{ + // Boundary: boundary, + //} + + newquadtree := &Quadtree{ + Boundary: BoundingBox{ + Center: Vec2{ + X: boundary.Center.X, + Y: boundary.Center.Y, + }, + Width: boundary.Width, + }, + CenterOfMass: Vec2{ + X: 0, + Y: 0, + }, + TotalMass: 0, + Depth: 0, + Star: Star2D{ + C: Vec2{ + X: 0, + Y: 0, + }, + V: Vec2{ + X: 0, + Y: 0, + }, + M: 0, + }, + Leaf: false, + Quadrants: [4]*Quadtree{}, + } + 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) + 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) + + var empty bool = true // is the tree empty? + for _, element := range q.Quadrants { + + // if one element is not empty + if element != nil { + empty = false + } + } + + empty = true + + if empty == true { + log.Println("[ ] Subdividing the current tree") + q.subdivide() + log.Println("[+] Done Subdividing!") + + log.Printf("[~] \t point: %v\n", point) + log.Printf("[~] \t quadrant: %v\n", q.Quadrants[0]) + + if point.C.X < bx && point.C.X > bx-bw { + // Left + log.Println("[~] \t\t The point is left of the y-axis!") + if point.C.Y > by && point.C.Y < by+bw { + // Top Left + log.Println("[~] \t\t The point is above of the x-axis!") + log.Println("[ ] \t Inserting the point into the top left (NW) quadtree") + q.Quadrants[0].Star = point + log.Println("[+] \t DONE!") + } else { + // Bottom Left + log.Println("[~] \t\t The point is below of the x-axis!") + log.Println("[ ] \t Inserting the point into the bottom left (SW) quadtree") + q.Quadrants[2].Star = point + log.Println("[+] \t DONE!") + } + } else { + // Right + log.Println("[~] \t\t The point is right of the y-axis!") + if point.C.Y > by && point.C.Y < by+bw { + // Top Right + log.Println("[~] \t\t The point is above of the x-axis!") + log.Println("[ ] \t Inserting the point into the top right (NE) quadtree") + q.Quadrants[1].Star = point + log.Println("[+] \t DONE!") + } else { + // Bottom Right + log.Println("[~] \t\t The point is below of the x-axis!") + log.Println("[ ] \t Inserting the point into the bottom right (SE) quadtree") + q.Quadrants[3].Star = point + log.Println("[+] \t DONE!") + } + } + } +} + +// subdivide subdivides the quadtree it is called on +func (q *Quadtree) subdivide() { + log.Println("[ ] Getting the current boundary") + oldCenterX := q.Boundary.Center.X + oldCenterY := q.Boundary.Center.Y + oldWidth := q.Boundary.Width + log.Printf("[~] \t oldCenterX: %f\n", oldCenterX) + log.Printf("[~] \t oldCenterY: %f\n", oldCenterY) + log.Printf("[~] \t oldWidth: %f\n", oldWidth) + log.Println("[+] Done getting the current boundary!") + + log.Println("[ ] Defining the new centerpoints") + newCenterNW := Vec2{oldCenterX - (oldWidth / 2), oldCenterY + (oldWidth / 2)} + newCenterNE := Vec2{oldCenterX + (oldWidth / 2), oldCenterY + (oldWidth / 2)} + newCenterSW := Vec2{oldCenterX - (oldWidth / 2), oldCenterY - (oldWidth / 2)} + newCenterSE := Vec2{oldCenterX + (oldWidth / 2), oldCenterY - (oldWidth / 2)} + log.Printf("[~] \t newCenterNW: %v\n", newCenterNW) + log.Printf("[~] \t newCenterNE: %v\n", newCenterNE) + log.Printf("[~] \t newCenterSW: %v\n", newCenterSW) + log.Printf("[~] \t newCenterSE: %v\n", newCenterSE) + log.Println("[+] Done defining the new centerpoints!") + + log.Println("[ ] Calculating th new width") + log.Printf("[~] \t Old width: %f", oldWidth) + newWidth := oldWidth / 2 + log.Printf("[~] \t New width: %f", newWidth) + log.Println("[+] Done calculating the new width!") + + log.Println("[ ] Generating the new bounding boxes") + NWboundingBox := NewBoundingBox(newCenterNW, newWidth) + NEboundingBox := NewBoundingBox(newCenterNE, newWidth) + SWboundingBox := NewBoundingBox(newCenterSW, newWidth) + SEboundingBox := NewBoundingBox(newCenterSE, newWidth) + log.Printf("[~] \t NW: %v", NWboundingBox) + log.Printf("[~] \t NE: %v", NEboundingBox) + log.Printf("[~] \t SW: %v", SWboundingBox) + log.Printf("[~] \t SE: %v", SEboundingBox) + log.Println("[+] Done generating the new bounding boxes!") + + log.Println("[ ] assigning the bounding boxes to the individual quadrants") + log.Printf("[~] \t root quadtree: %v\n", q) + log.Printf("[~] \t NW quadtree: %v\n", NewQuadtree(NWboundingBox)) + log.Printf("[~] \t NE quadtree: %v\n", NewQuadtree(NEboundingBox)) + log.Printf("[~] \t SW quadtree: %v\n", NewQuadtree(SWboundingBox)) + log.Printf("[~] \t SE quadtree: %v\n", NewQuadtree(SEboundingBox)) + q.Quadrants[0] = NewQuadtree(NWboundingBox) + q.Quadrants[1] = NewQuadtree(NEboundingBox) + q.Quadrants[2] = NewQuadtree(SWboundingBox) + q.Quadrants[3] = NewQuadtree(SEboundingBox) + log.Println("[+] Done assigning the bounding boxes to the individual quadrants!") } |
