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
|
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)
}
|
