diff options
author | hanemile <hanemile@protonmail.com> | 2018-11-16 13:57:21 +0100 |
---|---|---|
committer | hanemile <hanemile@protonmail.com> | 2018-11-16 13:57:21 +0100 |
commit | 537c1cdb8067f7ca23c05b6cd3303e833a7c4135 (patch) | |
tree | e9fa7215e87f7b6c94a3a1830db172cb22980a68 /quadtree.go | |
parent | 917a6d10480981e45625475f3458dcc2dc0fe092 (diff) |
Cleaning up a bit
Diffstat (limited to 'quadtree.go')
-rw-r--r-- | quadtree.go | 177 |
1 files changed, 177 insertions, 0 deletions
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) +} |