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 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ structs.go | 175 ----------------------------------------------------------- 2 files changed, 177 insertions(+), 175 deletions(-) create mode 100644 quadtree.go delete mode 100644 structs.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) +} diff --git a/structs.go b/structs.go deleted file mode 100644 index 76964fa..0000000 --- a/structs.go +++ /dev/null @@ -1,175 +0,0 @@ -package quadtree - -import "fmt" - -// coordinate type storing a position -type Coord struct { - x float64 - y float64 -} - -// BoundingBox defines a single cell in the Quadtree -type BoundingBox struct { - center Coord - halfDimension float64 -} - -// Quadtree defining the whole Quadtree and a node in itself (recursively) -type Quadtree struct { - // general information (node capacity, 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 -} - -// newCoord returns a new coordinate using the given values -func NewCoord(x float64, y float64) Coord { - return Coord{x, y} -} - -// NewBoundingBox returns a new bounding with the given struct elements -func NewBoundingBox(inCenter Coord, inHalfDimension float64) BoundingBox { - return BoundingBox{ - center: inCenter, - halfDimension: inHalfDimension, - } -} - -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 -} - -// 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, - } -} - -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, point) -} - -// 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