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 --- structs.go | 175 ------------------------------------------------------------- 1 file changed, 175 deletions(-) delete mode 100644 structs.go (limited to 'structs.go') 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