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) } func (quadtree *Quadtree) Print() { if quadtree.northEast != nil { quadtree.northEast.Print() } if quadtree.northWest != nil { quadtree.northWest.Print() } if quadtree.southEast != nil { quadtree.southEast.Print() } if quadtree.southWest != nil { quadtree.southWest.Print() } fmt.Println(quadtree) }