diff options
| -rw-r--r-- | quadtree.go (renamed from structs.go) | 98 |
1 files changed, 50 insertions, 48 deletions
diff --git a/structs.go b/quadtree.go index 76964fa..c799df7 100644 --- a/structs.go +++ b/quadtree.go @@ -2,10 +2,37 @@ package quadtree import "fmt" -// coordinate type storing a position type Coord struct { - x float64 - y float64 + 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 @@ -14,9 +41,17 @@ type BoundingBox struct { 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) + // general information (node ca/home/hanemile/go/src/git.darknebu.la/emile/quadtreepacity, spacial outreach) nodeCapacity int boundary BoundingBox @@ -32,41 +67,6 @@ type Quadtree struct { 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{ @@ -81,13 +81,14 @@ func NewQuadtree(boundary BoundingBox, depth int) *Quadtree { } } +// 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, + X: quadtree.boundary.center.X - quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y + quadtree.boundary.halfDimension/2, }, halfDimension: quadtree.boundary.halfDimension / 2, } @@ -96,8 +97,8 @@ func (quadtree *Quadtree) subdivide() { // 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, + X: quadtree.boundary.center.X + quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y + quadtree.boundary.halfDimension/2, }, halfDimension: quadtree.boundary.halfDimension / 2, } @@ -106,8 +107,8 @@ func (quadtree *Quadtree) subdivide() { // 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, + X: quadtree.boundary.center.X - quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y - quadtree.boundary.halfDimension/2, }, halfDimension: quadtree.boundary.halfDimension / 2, } @@ -116,8 +117,8 @@ func (quadtree *Quadtree) subdivide() { // 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, + X: quadtree.boundary.center.X + quadtree.boundary.halfDimension/2, + Y: quadtree.boundary.center.Y - quadtree.boundary.halfDimension/2, }, halfDimension: quadtree.boundary.halfDimension / 2, } @@ -135,6 +136,7 @@ func (quadtree *Quadtree) Insert(point Coord) { 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) } @@ -151,7 +153,7 @@ func (quadtree *Quadtree) Insert(point Coord) { // if the maximal depth of the tree has been reached: // Insert the point into the slice - quadtree.pointsSlice = append(quadtree.pointsSlice, point) + quadtree.pointsSlice = append(quadtree.pointsSlice, NewCoord(point.X, point.Y)) } // Print() is a method that can be used on a quadtree. |
