-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathoctree.py
325 lines (271 loc) · 13.2 KB
/
octree.py
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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
class node():
"""
Class to be a node in my octree
"""
def __init__(self,parent, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit):
self.parent = parent
self.Xupperlimit = Xupperlimit
self.Yupperlimit = Yupperlimit
self.Zupperlimit = Zupperlimit
self.Xlowerlimit = Xlowerlimit
self.Ylowerlimit = Ylowerlimit
self.Zlowerlimit = Zlowerlimit
self.Xcenter = (self.Xupperlimit + self.Xlowerlimit)/2.
self.Ycenter = (self.Yupperlimit + self.Ylowerlimit)/2.
self.Zcenter = (self.Zupperlimit + self.Xlowerlimit)/2.
parent = None
value = None
#children
posXposYposZ = None
posXposYnegZ = None
posXnegYposZ = None
posXnegYnegZ = None
negXposYposZ = None
negXposYnegZ = None
negXnegYposZ = None
negXnegYnegZ = None
#array of children
chidren = [posXposYposZ,posXposYnegZ,posXnegYposZ,posXnegYnegZ,negXposYposZ,negXposYnegZ,negXnegYposZ,negXnegYnegZ]
#position in space
Xupperlimit = None
Yupperlimit = None
Zupperlimit = None
Xlowerlimit = None
Ylowerlimit = None
Zlowerlimit = None
def get_array_of_children(self):
"""
helper function to return array of children
because there is some weird issue where just setting an
array variable isn't cutting it
"""
children = [self.posXposYposZ,self.posXposYnegZ,self.posXnegYposZ,self.posXposYnegZ,self.negXposYposZ,self.negXposYnegZ,self.negXnegYposZ,self.negXnegYnegZ ]
return children
def print_types(self):
"""
helper function to printout types of children
"""
print type(self.posXposYposZ)
print type(self.posXposYnegZ)
print type(self.posXnegYposZ)
print type(self.posXnegYnegZ)
print type(self.negXposYposZ)
print type(self.negXposYnegZ)
print type(self.negXnegYposZ)
print type(self.negXnegYnegZ)
def print_info(self):
"""
helper function to dump node paramaters
"""
print "parent:\t {0}".format(self.parent)
print "value:\t {0}".format(self.value)
#children
print "posXposYposZ: \t {0}".format(self.posXposYposZ)
print "posXposYnegz: \t {0}".format(self.posXposYnegZ)
print "posXnegYposZ: \t {0}".format(self.posXnegYposZ)
print "posXnegYnegZ: \t {0}".format(self.posXnegYnegZ)
print "negXposYposZ: \t {0}".format(self.negXposYposZ)
print "negXposYnegZ: \t {0}".format(self.negXposYnegZ)
print "negXnegYposZ: \t {0}".format(self.negXnegYposZ)
print "negXnegYnegZ: \t {0}".format(self.negXnegYnegZ)
#position in space
print "Xupperlimit: \t {0}".format(self.Xupperlimit)
print "Yupperlimit: \t {0}".format(self.Yupperlimit)
print "Zupperlimit: \t {0}".format(self.Zupperlimit)
print "Xlowerlimit: \t {0}".format(self.Xlowerlimit)
print "Ylowerlimit: \t {0}".format(self.Ylowerlimit)
print "Zlowerlimit: \t {0}".format(self.Zlowerlimit)
print "Xcenter: \t {0}".format(self.Xcenter)
print "Ycenter: \t {0}".format(self.Ycenter)
print "Zcenter: \t {0}".format(self.Zcenter)
def add(self, payload, coord, level):
"""
Create a subnode
"""
if level == 0:
try:
self.value.append((coord,payload))
except AttributeError:
self.value = []
self.value.append((coord,payload))
else:
level -= 1
#Determine quadrant
if coord[0] <= self.Xcenter:
#negX
if coord[1] <= self.Ycenter:
#negY
if coord[2] <= self.Zcenter:
#negZ
Xupperlimit = self.Xcenter
Yupperlimit = self.Ycenter
Zupperlimit = self.Zcenter
Xlowerlimit = self.Xlowerlimit
Ylowerlimit = self.Ylowerlimit
Zlowerlimit = self.Zlowerlimit
self.negXnegYnegZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.negXnegYnegZ.add(payload, coord, level)
else:
#posZ
Xupperlimit = self.Xcenter
Yupperlimit = self.Ycenter
Zupperlimit = self.Zupperlimit
Xlowerlimit = self.Xlowerlimit
Ylowerlimit = self.Ylowerlimit
Zlowerlimit = self.Zcenter
self.negXnegYposZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.negXnegYposZ.add(payload, coord, level)
else:
#posY
if coord[2] <= self.Zcenter:
#negZ
Xupperlimit = self.Xcenter
Yupperlimit = self.Yupperlimit
Zupperlimit = self.Zcenter
Xlowerlimit = self.Xlowerlimit
Ylowerlimit = self.Ycenter
Zlowerlimit = self.Zlowerlimit
self.negXposYnegZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.negXposYnegZ.add(payload, coord, level)
else:
#posZ
Xupperlimit = self.Xcenter
Yupperlimit = self.Yupperlimit
Zupperlimit = self.Zupperlimit
Xlowerlimit = self.Xlowerlimit
Ylowerlimit = self.Ycenter
Zlowerlimit = self.Zcenter
self.negXposYposZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.negXposYposZ.add(payload, coord, level)
else:
#posX
if coord[1] <= self.Ycenter:
#negY
if coord[2] <= self.Zcenter:
#negZ
Xupperlimit = self.Xupperlimit
Yupperlimit = self.Ycenter
Zupperlimit = self.Zcenter
Xlowerlimit = self.Xcenter
Ylowerlimit = self.Ylowerlimit
Zlowerlimit = self.Zlowerlimit
self.posXnegYnegZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.posXnegYnegZ.add(payload, coord, level)
else:
#posZ
Xupperlimit = self.Xupperlimit
Yupperlimit = self.Ycenter
Zupperlimit = self.Zupperlimit
Xlowerlimit = self.Xcenter
Ylowerlimit = self.Ylowerlimit
Zlowerlimit = self.Zcenter
self.posXnegYposZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.posXnegYposZ.add(payload, coord, level)
else:
#posY
if coord[2] <= self.Zcenter:
#negZ
Xupperlimit = self.Xupperlimit
Yupperlimit = self.Yupperlimit
Zupperlimit = self.Zcenter
Xlowerlimit = self.Zcenter
Ylowerlimit = self.Ycenter
Zlowerlimit = self.Zlowerlimit
self.posXposYnegZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.posXposYnegZ.add(payload, coord, level)
else:
#posZ
Xupperlimit = self.Xupperlimit
Yupperlimit = self.Yupperlimit
Zupperlimit = self.Zupperlimit
Xlowerlimit = self.Xcenter
Ylowerlimit = self.Ycenter
Zlowerlimit = self.Zcenter
self.posXposYposZ = node(self.negXnegYnegZ, Xupperlimit, Yupperlimit, Zupperlimit, Xlowerlimit, Ylowerlimit, Zlowerlimit)
self.posXposYposZ.add(payload, coord, level)
class Octree():
"""
class to hold the whole tree
We decided on using maxiter = 6 so that we would have each of the smallest subnodes be 1x1x1.
"""
def __init__(self, Xmax, Ymax, Zmax, Xmin, Ymin, Zmin, root_coords=(0,0,0), maxiter=6):
self.Xmax = Xmax
self.Ymax = Ymax
self.Zmax = Xmax
self.Xmin = Xmin
self.Ymin = Ymin
self.Zmin = Zmin
self.root_coords = root_coords
self.maxiter = maxiter
self.root = node('root', Xmax, Ymax, Zmax, Xmin, Ymin, Zmin)
def add_item(self, payload, coord):
"""
Create recursively create subnodes until maxiter is reached
then deposit payload in that node
"""
self.root.add(payload, coord, self.maxiter)
def find_within_range(self, center, size, shape):
"""
Return payloads and coordinates of every payload within
a specified area
"""
if shape == "cube":
payloads = []
templist = [self.root]
list_list = []
list_list.append([self.root])
for level in range(self.maxiter):
list_list.append([])
#print list_list
for level in range(self.maxiter):
for node in list_list[level]:
Xedge_max = center[0] + size
Xedge_min = center[0] - size
Yedge_max = center[1] + size
Yedge_min = center[1] - size
Zedge_max = center[2] + size
Zedge_min = center[2] - size
corner0 = (Xedge_max, Yedge_max, Zedge_max)
corner1 = (Xedge_max, Yedge_max, Zedge_min)
corner2 = (Xedge_max, Yedge_min, Zedge_max)
corner3 = (Xedge_max, Yedge_min, Zedge_min)
corner4 = (Xedge_min, Yedge_max, Zedge_max)
corner5 = (Xedge_min, Yedge_max, Zedge_min)
corner6 = (Xedge_min, Yedge_min, Zedge_max)
corner7 = (Xedge_min, Yedge_min, Zedge_min)
corners = [corner0, corner1, corner2, corner3, corner4, corner5, corner6, corner7]
table = ((corner0[0] > node.Xcenter),(corner0[1] > node.Ycenter) ,(corner0[2] > node.Zcenter))
if not False in table:
list_list[level+1].append(node.posXposYposZ)
table = ((corner1[0] > node.Xcenter),(corner1[1] > node.Ycenter) ,(corner1[2] < node.Zcenter))
if not False in table:
list_list[level+1].append(node.posXposYnegZ)
table = ((corner2[0] > node.Xcenter),(corner2[1] < node.Ycenter) ,(corner2[2] > node.Zcenter))
if not False in table:
list_list[level+1].append(node.posXnegYposZ)
table = ((corner3[0] > node.Xcenter),(corner3[1] < node.Ycenter) ,(corner3[2] < node.Zcenter))
if not False in table:
list_list[level+1].append(node.posXnegYnegZ)
table = ((corner4[0] < node.Xcenter),(corner4[1] > node.Ycenter) ,(corner4[2] > node.Zcenter))
if not False in table:
list_list[level+1].append(node.negXposYposZ)
table = ((corner5[0] < node.Xcenter),(corner5[1] > node.Ycenter) ,(corner5[2] < node.Zcenter))
if not False in table:
list_list[level+1].append(node.negXposYnegZ)
table = ((corner6[0] < node.Xcenter),(corner6[1] < node.Ycenter) ,(corner6[2] > node.Zcenter))
if not False in table:
list_list[level+1].append(node.negXnegYposZ)
table = ((corner7[0] < node.Xcenter),(corner7[1] < node.Ycenter) ,(corner7[2] < node.Zcenter))
if not False in table:
list_list[level+1].append(node.negXnegYnegZ)
#must remove children that aren't real yet
temp_templist = []
for node in list_list[level+1]:
try:
node.Xcenter
temp_templist.append(node)
except AttributeError:
pass
list_list[level+1] = temp_templist
payloads = [i.value for i in list_list[-1]]
return payloads