diff options
| -rw-r--r-- | structs.go | 153 | ||||
| -rw-r--r-- | structs_test.go | 126 |
2 files changed, 279 insertions, 0 deletions
diff --git a/structs.go b/structs.go new file mode 100644 index 0000000..9406a5b --- /dev/null +++ b/structs.go @@ -0,0 +1,153 @@ +package quadtree + +// 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) +} diff --git a/structs_test.go b/structs_test.go new file mode 100644 index 0000000..66598bf --- /dev/null +++ b/structs_test.go @@ -0,0 +1,126 @@ +package quadtree + +import ( + "testing" +) + +// Quadtree Test +func TestQuadtree(t *testing.T) { + testQuadtree := quadtree{ + nodeCapacity: 0, + boundary: boundingBox{}, + pointsSlice: nil, + northWest: nil, + northEast: nil, + southWest: nil, + southEast: nil, + } + + t.Log(testQuadtree) +} + +// NewQuadTree test +func TestNewQuadtree(t *testing.T) { + var boundary = boundingBox{ + center: Coord{0, 0}, + halfDimension: 3, + } + + var newQuadtree = *newQuadtree(boundary, 0) + + t.Log(newQuadtree) +} + +// Coordinate Test +func TestCoord(t *testing.T) { + testCoord := Coord{ + x: 0, + y: 1, + } + + t.Log(testCoord) +} + +// NewCoord test +func TestNewCoord(t *testing.T) { + var newCoordinate = NewCoord(1, 2) + + t.Log(newCoordinate) +} + +func TestBoundingBox(t *testing.T) { + var newBoundingBox = boundingBox{ + center: Coord{ + x: 1, + y: 2, + }, + halfDimension: 3, + } + + t.Log(newBoundingBox) +} + +func TestInsideOf(t *testing.T) { + var testCoordinate = Coord{0, 0} + var testQuadTree = newQuadtree(boundingBox{ + center: Coord{ + x: 0, + y: 0, + }, + halfDimension: 1, + }, 0) + + var isInsideOf = testCoordinate.insideOf(testQuadTree) + t.Log(isInsideOf) +} + +// Test the newBoundingBox function +func TestNewBoundingBox(t *testing.T) { + + // Initialize some values that are needed + var newCenter = Coord{1, 2} + var newHalfDimension float64 = 3 + + // Initialize the bounding box using the values above + var newBoundingBox = newBoundingBox(newCenter, newHalfDimension) + + // Print the newBoundingBox + t.Log(newBoundingBox) +} + +func TestSubdivide(t *testing.T) { + var boundary = boundingBox{ + center: Coord{0, 0}, + halfDimension: 3, + } + + var newQuadtree = *newQuadtree(boundary, 0) + + newQuadtree.subdivide() + + t.Logf("newQuadTree: %v\n", newQuadtree) + t.Logf("NorthWestCell: %v\n", newQuadtree.northWest) + t.Logf("NorthEestCell: %v\n", newQuadtree.northEast) + t.Logf("SouthWestCell: %v\n", newQuadtree.southWest) + t.Logf("SouthEastCell: %v\n", newQuadtree.southEast) + +} + +// test the insert function +func TestInsert(t *testing.T) { + // Define a new quadtree-root-boundary + var boundary = boundingBox{ + center: Coord{0, 0}, + halfDimension: 3, + } + + // create a new quadtree using the boundary + var newQuadtree = *newQuadtree(boundary, 0) + + // Define a star and insert it into the quadtree + singleCoord := Coord{0.5, 0.5} + newQuadtree.insert(singleCoord) + + // Print the stuff generated + t.Logf("Complete Tree: %v\n", newQuadtree.northEast.southWest.southWest.northEast) +} |
