diff options
| -rw-r--r-- | structs/structs.go | 153 |
1 files changed, 0 insertions, 153 deletions
diff --git a/structs/structs.go b/structs/structs.go deleted file mode 100644 index 12b208f..0000000 --- a/structs/structs.go +++ /dev/null @@ -1,153 +0,0 @@ -package structs - -// coordinate type storing a position -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 (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 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) -} |
