From 537c1cdb8067f7ca23c05b6cd3303e833a7c4135 Mon Sep 17 00:00:00 2001 From: hanemile Date: Fri, 16 Nov 2018 13:57:21 +0100 Subject: Cleaning up a bit --- quadtree.go | 177 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 177 insertions(+) create mode 100644 quadtree.go (limited to 'quadtree.go') diff --git a/quadtree.go b/quadtree.go new file mode 100644 index 0000000..c799df7 --- /dev/null +++ b/quadtree.go @@ -0,0 +1,177 @@ +package quadtree + +import "fmt" + +type Coord struct { + X float64 + Y float64 +} + +// newCoord returns a new coordinate using the given values +func NewCoord(x float64, y float64) Coord { + return Coord{x, y} +} + +// InsideOf returns true if the point the method is used on in inside of the quadtreecell +func (point Coord) InsideOf(quadtreeCell *Quadtree) bool { + // define the bounds + var lowerXBound = quadtreeCell.boundary.center.X - quadtreeCell.boundary.halfDimension + var upperXBound = quadtreeCell.boundary.center.X + quadtreeCell.boundary.halfDimension + var lowerYBound = quadtreeCell.boundary.center.Y - quadtreeCell.boundary.halfDimension + var upperYBound = quadtreeCell.boundary.center.Y + quadtreeCell.boundary.halfDimension + + // if the point is in the right x range + if point.X < upperXBound && point.X > lowerXBound { + + // test if the point is in the right y range + if point.Y < upperYBound && point.Y > lowerYBound { + + // the star is within the bounds: return true + return true + } + } + + // the star is outside of the bounds: return false + return false +} + +// BoundingBox defines a single cell in the Quadtree +type BoundingBox struct { + center Coord + halfDimension float64 +} + +// NewBoundingBox returns a new bounding with the given struct elements +func NewBoundingBox(inCenter Coord, inHalfDimension float64) BoundingBox { + return BoundingBox{ + center: inCenter, + halfDimension: inHalfDimension, + } +} + +// Quadtree defining the whole Quadtree and a node in itself (recursively) +type Quadtree struct { + // general information (node ca/home/hanemile/go/src/git.darknebu.la/emile/quadtreepacity, spacial outreach) + nodeCapacity int + boundary BoundingBox + + // slice storing the star coordinates + pointsSlice []Coord + + // the Quadtree leaves + northWest *Quadtree + northEast *Quadtree + southWest *Quadtree + southEast *Quadtree + + depth int +} + +// NewQuadtree returns a new Quadtree +func NewQuadtree(boundary BoundingBox, depth int) *Quadtree { + return &Quadtree{ + nodeCapacity: 0, + boundary: boundary, + pointsSlice: nil, + northWest: nil, + northEast: nil, + southWest: nil, + southEast: nil, + depth: depth, + } +} + +// Subdvide the given quadtree into multiple cells +func (quadtree *Quadtree) subdivide() { + + // Create the new NorthWest boundingbox + var newCellBoundingNorthWest = BoundingBox{ + center: Coord{ + X: quadtree.boundary.center.X - quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y + quadtree.boundary.halfDimension/2, + }, + halfDimension: quadtree.boundary.halfDimension / 2, + } + quadtree.northWest = NewQuadtree(newCellBoundingNorthWest, quadtree.depth+1) + + // Create the new NorthWest boundingbox + var newCellBoundingNorthEast = BoundingBox{ + center: Coord{ + X: quadtree.boundary.center.X + quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y + quadtree.boundary.halfDimension/2, + }, + halfDimension: quadtree.boundary.halfDimension / 2, + } + quadtree.northEast = NewQuadtree(newCellBoundingNorthEast, quadtree.depth+1) + + // Create the new NorthWest boundingbox + var newCellBoundingSouthWest = BoundingBox{ + center: Coord{ + X: quadtree.boundary.center.X - quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y - quadtree.boundary.halfDimension/2, + }, + halfDimension: quadtree.boundary.halfDimension / 2, + } + quadtree.southWest = NewQuadtree(newCellBoundingSouthWest, quadtree.depth+1) + + // Create the new NorthWest boundingbox + var newCellBoundingSouthEast = BoundingBox{ + center: Coord{ + X: quadtree.boundary.center.X + quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y - quadtree.boundary.halfDimension/2, + }, + halfDimension: quadtree.boundary.halfDimension / 2, + } + quadtree.southEast = NewQuadtree(newCellBoundingSouthEast, quadtree.depth+1) +} + +// Insert inserts the given point into the Quadtree the method is applied on +// it returns an error incase the point is not in bounds +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 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)) +} + +// 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() { + // Define an end condition: if the quadtree-leaf is nil, the root does not continue + if quadtree.northWest != nil { + quadtree.northWest.Print() + } + if quadtree.northEast != nil { + quadtree.northEast.Print() + } + if quadtree.southWest != nil { + quadtree.southWest.Print() + } + if quadtree.southEast != nil { + quadtree.southEast.Print() + } + fmt.Println(quadtree) +} -- cgit 1.4.1