diff options
| -rw-r--r-- | quadtree_test.go | 341 | ||||
| -rw-r--r-- | structs_test.go | 290 |
2 files changed, 341 insertions, 290 deletions
diff --git a/quadtree_test.go b/quadtree_test.go new file mode 100644 index 0000000..e736515 --- /dev/null +++ b/quadtree_test.go @@ -0,0 +1,341 @@ +package quadtree + +import ( + "reflect" + "testing" +) + +func TestNewCoord(t *testing.T) { + type args struct { + x float64 + y float64 + } + tests := []struct { + name string + args args + want Coord + }{ + {"NewCoord both positive", args{1.0, 1.0}, Coord{1, 1}}, + {"NewCoord both negative", args{-1.0, -1.0}, Coord{-1, -1}}, + {"NewCoord both zero", args{0, 0}, Coord{0, 0}}, + } + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + if got := NewCoord(tt.args.x, tt.args.y); !reflect.DeepEqual(got, tt.want) { + t.Errorf("NewCoord() = %v, want %v", got, tt.want) + } + }) + } +} + +func BenchmarkNewCoord(b *testing.B) { + for i := 0; i < b.N; i++ { + NewCoord(0, 1) + } +} + +func TestNewBoundingBox(t *testing.T) { + type args struct { + inCenter Coord + inHalfDimension float64 + } + tests := []struct { + name string + args args + want BoundingBox + }{ + {"bounding positive", args{Coord{0, 0}, 5.0}, BoundingBox{Coord{0, 0}, 5.0}}, + {"bounding negative", args{Coord{0, 0}, -5.0}, BoundingBox{Coord{0, 0}, -5.0}}, + {"positive", args{Coord{3, 3}, 5.0}, BoundingBox{Coord{3, 3}, 5.0}}, + {"negative", args{Coord{-3, -3}, 5.0}, BoundingBox{Coord{-3, -3}, 5.0}}, + } + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + if got := NewBoundingBox(tt.args.inCenter, tt.args.inHalfDimension); !reflect.DeepEqual(got, tt.want) { + t.Errorf("NewBoundingBox() = %v, want %v", got, tt.want) + } + }) + } +} + +func BenchmarkNewBoundingBox(b *testing.B) { + for i := 0; i < b.N; i++ { + NewBoundingBox(Coord{1, 2}, 4) + } +} + +func TestCoord_InsideOf(t *testing.T) { + type args struct { + quadtreeCell *Quadtree + } + + // define a quadtreeCell that should be used + quadtreeCell := Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 3, + }, + pointsSlice: nil, + northWest: nil, + northEast: nil, + southWest: nil, + southEast: nil, + depth: 0, + } + + // Define a struct storing the tests + tests := []struct { + name string + point *Coord + args args + want bool + }{ + // Define the testcases + {"point inside of the quadtree", &Coord{0, 0}, args{&quadtreeCell}, true}, + {"point outside of the quadtree", &Coord{4, 4}, args{&quadtreeCell}, false}, + } + + // Run the tests + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + if got := tt.point.InsideOf(tt.args.quadtreeCell); got != tt.want { + t.Errorf("Coord.InsideOf() = %v, want %v", got, tt.want) + } + }) + } +} + +func TestNewQuadtree(t *testing.T) { + type args struct { + boundary BoundingBox + depth int + } + tests := []struct { + name string + args args + want *Quadtree + }{ + { + name: "", + args: args{ + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + depth: 0, + }, + want: &Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + pointsSlice: nil, + northWest: nil, + northEast: nil, + southWest: nil, + southEast: nil, + depth: 0, + }, + }, + } + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + if got := NewQuadtree(tt.args.boundary, tt.args.depth); !reflect.DeepEqual(got, tt.want) { + t.Errorf("NewQuadtree() = %v, want %v", got, tt.want) + } + }) + } +} + +func TestQuadtree_subdivide(t *testing.T) { + tests := []struct { + name string + quadtree *Quadtree + }{ + { + name: "Subdivide", + quadtree: &Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + pointsSlice: nil, + northWest: &Quadtree{}, + northEast: &Quadtree{}, + southWest: &Quadtree{}, + southEast: &Quadtree{}, + depth: 0, + }, + }, + } + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + tt.quadtree.subdivide() + }) + } +} + +func TestQuadtree_Insert(t *testing.T) { + type args struct { + point Coord + } + tests := []struct { + name string + quadtree *Quadtree + args args + }{ + { + name: "", + quadtree: &Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + pointsSlice: nil, + northWest: &Quadtree{}, + northEast: &Quadtree{}, + southWest: &Quadtree{}, + southEast: &Quadtree{}, + depth: 0, + }, + args: args{ + point: Coord{ + X: 1, + Y: 1, + }, + }, + }, + { + name: "", + quadtree: &Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + pointsSlice: nil, + northWest: &Quadtree{}, + northEast: &Quadtree{}, + southWest: &Quadtree{}, + southEast: &Quadtree{}, + depth: 0, + }, + args: args{ + point: Coord{ + X: 1, + Y: -1, + }, + }, + }, + { + name: "", + quadtree: &Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + pointsSlice: nil, + northWest: &Quadtree{}, + northEast: &Quadtree{}, + southWest: &Quadtree{}, + southEast: &Quadtree{}, + depth: 0, + }, + args: args{ + point: Coord{ + X: -1, + Y: -1, + }, + }, + }, + { + name: "", + quadtree: &Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + pointsSlice: nil, + northWest: &Quadtree{}, + northEast: &Quadtree{}, + southWest: &Quadtree{}, + southEast: &Quadtree{}, + depth: 0, + }, + args: args{ + point: Coord{ + X: -1, + Y: 1, + }, + }, + }, + } + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + tt.quadtree.Insert(tt.args.point) + + }) + } +} + +func TestQuadtree_Print(t *testing.T) { + tests := []struct { + name string + quadtree *Quadtree + }{ + { + name: "", + quadtree: &Quadtree{ + nodeCapacity: 0, + boundary: BoundingBox{ + center: Coord{ + X: 0, + Y: 0, + }, + halfDimension: 0, + }, + pointsSlice: nil, + northWest: &Quadtree{}, + northEast: &Quadtree{}, + southWest: &Quadtree{}, + southEast: &Quadtree{}, + depth: 0, + }, + }, + } + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + tt.quadtree.Print() + }) + } +} diff --git a/structs_test.go b/structs_test.go deleted file mode 100644 index 30ac7cf..0000000 --- a/structs_test.go +++ /dev/null @@ -1,290 +0,0 @@ -package quadtree - -import ( - "fmt" - "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) -} - -// TestBoundingBox creates a bounding box -func TestBoundingBox(t *testing.T) { - var newBoundingBox = BoundingBox{ - center: Coord{ - x: 1, - y: 2, - }, - halfDimension: 3, - } - - t.Log(newBoundingBox) -} - -// TestInsideOf runs multiple tests testing if a point is inside a bounding box -// All possible scenarios are simulated: -// 1. The Point is outside of the x-range -// 2. The Point is inside of the x-range, but outside of the y-range -// 3. The Point if inside the the x- and y-range -// The case where the point is inside of the y-range, but outsid eof the x-range -// does not need to be considered -func TestInsideOf(t *testing.T) { - - // Define a QuadTree that will be used for all tests - var testQuadTree = NewQuadtree(BoundingBox{ - center: Coord{ - x: 0, - y: 0, - }, - halfDimension: 1, - }, 0) - - // Case 1: The point is outside of the x-range - var testCoordinateInX = Coord{10, 0} - var isInsideOfX = testCoordinateInX.InsideOf(testQuadTree) - t.Logf("%v is inside of %v: %t", testCoordinateInX, testQuadTree.boundary, isInsideOfX) - - // Case 2: The point is inside of the x-range, but outside of the y-range - var testCoordinateInXNotY = Coord{0.5, 10} - var isInsideOfXNotY = testCoordinateInXNotY.InsideOf(testQuadTree) - t.Logf("%v is inside of %v: %t", testCoordinateInXNotY, testQuadTree.boundary, isInsideOfXNotY) - - // Case 3: The point is inside of the x- and y-range - var testCoordinateInside = Coord{0, 0} - var isInsideOfInside = testCoordinateInside.InsideOf(testQuadTree) - t.Logf("%v is inside of %v: %t", testCoordinateInside, testQuadTree.boundary, isInsideOfInside) -} - -// 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 Method -// Case 1: The point is in the North-West Sector -// Case 2: The point is in the North-East Sector -// Case 3: The point is in the South-West Sector -// Case 4: The point is in the South-East Sector -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) - - // Case 1: Add a star to the North-West Boundary - singleCoordNW := Coord{-0.5, 0.5} - newQuadtree.Insert(singleCoordNW) - - // Case 2: Add a star to the North-East Boundary - singleCoordNE := Coord{0.5, 0.5} - newQuadtree.Insert(singleCoordNE) - - // Case 3: Add a star to the South-West Boundary - singleCoordSW := Coord{0.5, -0.5} - newQuadtree.Insert(singleCoordSW) - - // Case 4: Add a star to the South-East Boundary - singleCoordSE := Coord{-0.5, -0.5} - newQuadtree.Insert(singleCoordSE) - -} - -// test printing a quadtree -func TestPrint(t *testing.T) { - - // Define a testQuadTree - - var testQuadTree = Quadtree{ - nodeCapacity: 0, - boundary: BoundingBox{ - center: Coord{ - x: 0, - y: 0, - }, - halfDimension: 4, - }, - pointsSlice: nil, - northWest: &Quadtree{ - nodeCapacity: 0, - boundary: BoundingBox{ - center: Coord{ - x: 2, - y: 2, - }, - halfDimension: 2, - }, - pointsSlice: nil, - northWest: &Quadtree{ - nodeCapacity: 0, - boundary: BoundingBox{ - center: Coord{ - x: 3, - y: 3, - }, - halfDimension: 1, - }, - pointsSlice: nil, - northWest: nil, - northEast: nil, - southWest: nil, - southEast: nil, - depth: 2, - }, - northEast: nil, - southWest: nil, - southEast: nil, - depth: 1, - }, - northEast: &Quadtree{ - nodeCapacity: 0, - boundary: BoundingBox{ - center: Coord{ - x: -2, - y: 2, - }, - halfDimension: 2, - }, - pointsSlice: nil, - northWest: nil, - northEast: nil, - southWest: nil, - southEast: nil, - depth: 1, - }, - southWest: &Quadtree{ - nodeCapacity: 0, - boundary: BoundingBox{ - center: Coord{ - x: 2, - y: -2, - }, - halfDimension: 2, - }, - pointsSlice: nil, - northWest: nil, - northEast: nil, - southWest: nil, - southEast: nil, - depth: 1, - }, - southEast: &Quadtree{ - nodeCapacity: 0, - boundary: BoundingBox{ - center: Coord{ - x: -2, - y: -2, - }, - halfDimension: 2, - }, - pointsSlice: nil, - northWest: nil, - northEast: nil, - southWest: nil, - southEast: nil, - depth: 1, - }, - depth: 0, - } - - // Print the test-QuadTree - testQuadTree.Print() -} - -/*############################################################ - BEYOND THIS POINT: EXAMPLES -############################################################*/ - -// The NewCoord function can be used to create a new Coordinate in the following way: -func ExampleNewCoord() { - fmt.Println(NewCoord(1, 1)) - // Output: {1 1} -} - -// The NewBoundingBox function can combine a coordinate resulting in a BoundingBox: -func ExampleNewBoundingBox() { - fmt.Println(NewBoundingBox(NewCoord(0, 0), 10)) - // Output: {{0 0} 10} -} - -// Using the InsideOf() method, it can be determined if a point is inside of a bounding box -// or not. The Example below can be used as a reference: -func ExampleInsideOf() { - var point = NewCoord(0, 0) - var bounadry = NewBoundingBox(NewCoord(0, 0), 10) - var quadtreeCell = NewQuadtree(bounadry, 0) - - fmt.Println(point.InsideOf(quadtreeCell)) - // Output: true -} |
