diff options
-rw-r--r-- | .idea/encodings.xml | 4 | ||||
-rw-r--r-- | c.out | 28 | ||||
-rw-r--r-- | quadtree.go | 146 | ||||
-rw-r--r-- | quadtree_test.go | 1 |
4 files changed, 151 insertions, 28 deletions
diff --git a/.idea/encodings.xml b/.idea/encodings.xml new file mode 100644 index 0000000..15a15b2 --- /dev/null +++ b/.idea/encodings.xml @@ -0,0 +1,4 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project version="4"> + <component name="Encoding" addBOMForNewFiles="with NO BOM" /> +</project> \ No newline at end of file diff --git a/c.out b/c.out new file mode 100644 index 0000000..8a23115 --- /dev/null +++ b/c.out @@ -0,0 +1,28 @@ +mode: set +git.darknebu.la/emile/quadtree/quadtree.go:11.43,13.2 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:16.58,24.52 5 1 +git.darknebu.la/emile/quadtree/quadtree.go:35.2,35.14 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:24.52,27.53 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:27.53,31.4 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:45.74,50.2 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:71.61,82.2 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:85.39,126.2 8 1 +git.darknebu.la/emile/quadtree/quadtree.go:130.47,136.24 2 1 +git.darknebu.la/emile/quadtree/quadtree.go:156.2,156.81 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:136.24,140.41 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:143.3,143.41 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:146.3,146.41 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:149.3,149.41 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:140.41,142.4 1 0 +git.darknebu.la/emile/quadtree/quadtree.go:143.41,145.4 1 0 +git.darknebu.la/emile/quadtree/quadtree.go:146.41,148.4 1 0 +git.darknebu.la/emile/quadtree/quadtree.go:149.41,151.4 1 0 +git.darknebu.la/emile/quadtree/quadtree.go:162.35,164.31 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:167.2,167.31 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:170.2,170.31 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:173.2,173.31 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:176.2,176.23 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:164.31,166.3 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:167.31,169.3 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:170.31,172.3 1 1 +git.darknebu.la/emile/quadtree/quadtree.go:173.31,175.3 1 1 diff --git a/quadtree.go b/quadtree.go index c799df7..24aedb6 100644 --- a/quadtree.go +++ b/quadtree.go @@ -1,6 +1,12 @@ package quadtree -import "fmt" +import ( + "fmt" + "git.darknebu.la/GalaxySimulator/Source/structs" + + //"git.darknebu.la/GalaxySimulator/Source/structs" + "github.com/fogleman/gg" +) type Coord struct { X float64 @@ -132,46 +138,132 @@ func (quadtree *Quadtree) Insert(point Coord) { // subdivide the Quadtree into four new cells quadtree.subdivide() - // if the maxDepth is not reached... - if quadtree.depth < 4 { - // ... test if the given point is inside the one of the cells - // and add Insert it to that specific cell - - if point.InsideOf(quadtree.northWest) { - quadtree.northWest.Insert(point) - } - if point.InsideOf(quadtree.northEast) { - quadtree.northEast.Insert(point) - } - if point.InsideOf(quadtree.southWest) { - quadtree.southWest.Insert(point) - } - if point.InsideOf(quadtree.southEast) { - quadtree.southEast.Insert(point) - } + if point.InsideOf(quadtree.northWest) { + quadtree.northWest.Insert(point) + } + if point.InsideOf(quadtree.northEast) { + quadtree.northEast.Insert(point) + } + if point.InsideOf(quadtree.southWest) { + quadtree.southWest.Insert(point) + } + if point.InsideOf(quadtree.southEast) { + quadtree.southEast.Insert(point) } // if the maximal depth of the tree has been reached: // Insert the point into the slice quadtree.pointsSlice = append(quadtree.pointsSlice, NewCoord(point.X, point.Y)) + fmt.Printf("Inserted (%f, %f) in layer %d\n", point.X, point.Y, quadtree.depth) } -// Print() is a method that can be used on a quadtree. -// It prints all the root nodes of the quadtree recursively -// The tree is printed from the bottom up in the following order: NW, NE, SW, SE -func (quadtree *Quadtree) Print() { +func Print(quadtree *Quadtree) { // Define an end condition: if the quadtree-leaf is nil, the root does not continue if quadtree.northWest != nil { - quadtree.northWest.Print() + Print(quadtree.northWest) } if quadtree.northEast != nil { - quadtree.northEast.Print() + Print(quadtree.northEast) } if quadtree.southWest != nil { - quadtree.southWest.Print() + Print(quadtree.southWest) } if quadtree.southEast != nil { - quadtree.southEast.Print() + Print(quadtree.southEast) } - fmt.Println(quadtree) + fmt.Printf("%d\t", quadtree.depth) + fmt.Printf("%v\t", quadtree.boundary) + fmt.Printf("%d\n", len(quadtree.pointsSlice)) +} + +func CreateWithSlice(slice []structs.Star2D) Quadtree { + // Create a new bounding box at the center of the Galaxy containing the whole galaxy + var newCenter structs.Vec2 = structs.Vec2{0, 0} + var newHalfDimension float64 = 5e5 + + // Create a Quadtree containing the whole galaxy + var boundary BoundingBox = NewBoundingBox(Coord(newCenter), newHalfDimension) + var depth int = 0 + var newQuadtree *Quadtree = NewQuadtree(boundary, depth) + + fmt.Printf("Inserting %d Elements into the Quadtree\n", len(slice)) + + // Insert all the stars from the slice into the quadtree step for step + for i := 0; i < len(slice); i++ { + newQuadtree.Insert(Coord(slice[i].C)) + } + + return *newQuadtree +} + +func InitializeCanvas() *gg.Context { + const imageWidth = 8192 + const imageHeight = 8192 + + // Initialize the new Context + dc := gg.NewContext(imageWidth, imageHeight) + + // Set the Background to black + dc.SetRGB(0, 0, 0) + dc.Clear() + + // Invert the Y axis + dc.InvertY() + + // Translate the Coordinate System to the middle of the image + dc.TransformPoint(imageWidth/4, imageHeight/4) + + return dc } + +// recursively iterate over a quadtree and draw all the nodes +func drawQuadTree(dc *gg.Context, quadtree Quadtree) { + + // find filled quadtrees + if quadtree.northWest != nil { + drawQuadTree(dc, *quadtree.northWest) + } + if quadtree.northEast != nil { + drawQuadTree(dc, *quadtree.northEast) + } + if quadtree.southWest != nil { + drawQuadTree(dc, *quadtree.southWest) + } + if quadtree.southEast != nil { + drawQuadTree(dc, *quadtree.southEast) + } + + // don't draw the root node + if quadtree.depth != 0 { + + // calculate the position of the new rectangle + origx := quadtree.boundary.center.X + origy := quadtree.boundary.center.X + x := (origx - quadtree.boundary.halfDimension) / 1000 + y := (origy - quadtree.boundary.halfDimension) / 1000 + w := quadtree.boundary.halfDimension + h := quadtree.boundary.halfDimension + //fmt.Printf("(%f, %f), (%f, %f, %f, %f)\n", origx, origy, x, y, w, h) + + // draw the rectangle + dc.DrawRectangle(x, y, w, h) + dc.Stroke() + } +} + +// save the given gg.Context to the given path +func saveImage(dc *gg.Context, path string) { + err := dc.SavePNG(path) + if err != nil { + panic(err) + } +} + +func DrawQuadtree(quadtree Quadtree) { + dc := InitializeCanvas() + + dc.SetRGB(1, 1, 1) + drawQuadTree(dc, quadtree) + saveImage(dc, "quadtree.png") +} + diff --git a/quadtree_test.go b/quadtree_test.go index 590943f..523cb40 100644 --- a/quadtree_test.go +++ b/quadtree_test.go @@ -381,4 +381,3 @@ func TestQuadtree_Print(t *testing.T) { } } -// Testing signed commits |