1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
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)
// 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)
}
/*############################################################
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_Coord() {
var point Coord = NewCoord(0, 0)
var bounadry BoundingBox = NewBoundingBox(NewCoord(0, 0), 10)
var quadtreeCell *Quadtree = NewQuadtree(bounadry, 0)
fmt.Println(point.InsideOf(quadtreeCell))
// Output: true
}
|
