diff options
| -rw-r--r-- | structs/structs.go | 138 |
1 files changed, 123 insertions, 15 deletions
diff --git a/structs/structs.go b/structs/structs.go index ea99d96..12b208f 100644 --- a/structs/structs.go +++ b/structs/structs.go @@ -1,45 +1,153 @@ package structs // coordinate type storing a position -type coord struct { +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} +func NewCoord(x float64, y float64) Coord { + return Coord{x, y} } -// boundingBox defines a single cell in the quadtree -type boundingBox struct { - center coord - halfDimension float64 -} +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 { -// containsPoint returns true if the given point is inside of the boundingBox the method is called on -func (boundingBox *boundingBox) containsPoint(point coord) bool { - // find out if the point is in or outside of the box - if boundingBox.center.x-boundingBox.halfDimension < point.x && boundingBox.center.x+boundingBox.halfDimension > point.x { - if boundingBox.center.y-boundingBox.halfDimension < point.y && boundingBox.center.y+boundingBox.halfDimension > point.y { + // test if the point is in the right y range + if point.y < upperYBound && point.y > lowerYBound { - // the point is inside of the cell -> return true + // the star is within the bounds: return true return true } } - // the point is outside of the cell -> return false + // 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 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 +} + +// 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) } |
