diff options
| -rw-r--r-- | draw.go | 106 | ||||
| -rw-r--r-- | quadtree.go | 218 |
2 files changed, 211 insertions, 113 deletions
diff --git a/draw.go b/draw.go new file mode 100644 index 0000000..1d7eb4f --- /dev/null +++ b/draw.go @@ -0,0 +1,106 @@ +package structs + +import ( + "log" + + "github.com/fogleman/gg" +) + +func initializePlot(imageWidth int, imageHeight int) *gg.Context { + + // define an new context using the given image width and height + context := gg.NewContext(imageWidth, imageHeight) + + // set the background color to black + context.SetRGB(0, 0, 0) + context.Clear() + context.SetRGB(1, 1, 1) + + // translate the coordinate origin to the midpoint of the image + context.Translate(float64(imageWidth/2), float64(imageHeight/2)) + + return context +} + +// drawQuadtree draws a given quadtree and the stars in it recursively to the given canvas +func drawQuadtree(context *gg.Context, q Quadtree) { + + // find out if the node is a leaf find out if the node is a leaf find out if the node is a leaf find out if the node is a leaf + var draw bool = false + for i := 0; i < 4; i++ { + if q.Quadrants[i] == nil { + draw = true + } + } + + // draw the bounding box and the star if the node is a leaf + if draw == true { + + // Don't draw nonexistent stars + if q.Star != (Star2D{}) { + + // define the current star + x := q.Star.C.X + y := q.Star.C.Y + starsize := 1 + + // set the color of the stars to green + context.SetRGB(0, 1, 1) + context.DrawPoint(x, y, float64(starsize)) + context.Fill() + // context.DrawString(fmt.Sprintf("(%f, %f)", x, y), x, y) + context.Stroke() + log.Printf("[***] Drawing Star (%f, %f)", x, y) + } + + // define the bounding box + boundingx := q.Boundary.Center.X + boundingy := q.Boundary.Center.Y + boundingw := q.Boundary.Width + + // bottom left corner + contextx := boundingx - (boundingw / 2) + contexty := boundingy - (boundingw / 2) + + // draw the rectangle + context.SetRGB(1, 1, 1) + context.DrawRectangle(contextx, contexty, boundingw, boundingw) + context.Stroke() + + log.Printf("[***] Drawing Box ((%f, %f), %f)", contextx, contexty, boundingw) + } + + // draw all the other trees recursively... + for i := 0; i < 4; i++ { + // ... but only if they exist + if q.Quadrants[i] != nil { + drawQuadtree(context, *q.Quadrants[i]) + } + } +} + +// saveImage saves the given context to the given path as a png +func saveImage(context *gg.Context, outpath string) { + savePngError := context.SavePNG(outpath) + if savePngError != nil { + panic(savePngError) + } +} + +// Draw draws the given quadtree to the given output path +func (q Quadtree) Draw(outpath string) { + log.Printf("Drawing the quadtree to %s", outpath) + + // define the image dimensions + imageWidth := 1024 * 8 + imageHeight := 1024 * 8 + + // define a new context to draw on + context := initializePlot(imageWidth, imageHeight) + + // first recursive call of drawQuadtree + drawQuadtree(context, q) + + // save the context to the given output path + saveImage(context, outpath) +} diff --git a/quadtree.go b/quadtree.go index 9a7d658..7adae8b 100644 --- a/quadtree.go +++ b/quadtree.go @@ -86,10 +86,6 @@ func (q *Quadtree) IsLeaf() { // NewQuadtree generates a new root node. func NewQuadtree(boundary BoundingBox) *Quadtree { - //newquadtree := &Quadtree{ - // Boundary: boundary, - //} - newquadtree := &Quadtree{ Boundary: BoundingBox{ Center: Vec2{ @@ -98,142 +94,138 @@ func NewQuadtree(boundary BoundingBox) *Quadtree { }, 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{}, + CenterOfMass: Vec2{}, + TotalMass: 0, + Depth: 0, + Star: Star2D{}, + Leaf: true, + Quadrants: [4]*Quadtree{}, } + 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) - 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) + log.Printf("[ ] Inserting point %v into the tree %v", point, q) - var empty bool = true // is the tree empty? - for _, element := range q.Quadrants { - - // if one element is not empty - if element != nil { - empty = false + // prints the stars in 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) } } - 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]) + // create a shortcut 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 galaxy + // 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 + 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") + // Test if the star is left or right of the center point if point.C.X < bx && point.C.X > bx-bw { - // Left - log.Println("[~] \t\t The point is left of the y-axis!") + 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 { - // 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!") + 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 { - // 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!") + 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 { - // Right - log.Println("[~] \t\t The point is right of the y-axis!") + 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 { - // 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!") + 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) + } } 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!") + 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) } // subdivide subdivides the quadtree it is called on func (q *Quadtree) subdivide() { - log.Println("[ ] Getting the current boundary") + // 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 - 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) + + // 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 - 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!") + + // 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) } |
