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
|
package quadtree
import "fmt"
// coordinate type storing a position
type Coord struct {
x float64
y float64
}
// BoundingBox defines a single cell in the quadtree
type BoundingBox struct {
center Coord
halfDimension float64
}
// 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
}
// 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{
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)
}
func (quadtree *quadtree) Print() {
if quadtree.northEast != nil {
quadtree.northEast.Print()
}
if quadtree.northWest != nil {
quadtree.northWest.Print()
}
if quadtree.southEast != nil {
quadtree.southEast.Print()
}
if quadtree.southWest != nil {
quadtree.southWest.Print()
}
fmt.Println(quadtree)
}
|