00001
00002
00003
00004
00005
00006
00007 from __future__ import division
00008
00009 from math import sqrt
00010
00011 from enhanced_grid import Container2D
00012
00013
00014
00015 TOP_LEFT = 0
00016
00017 TOP_RIGHT = 1
00018
00019
00020 BOTTOM_LEFT = 2
00021
00022
00023 BOTTOM_RIGHT = 3
00024
00025
00026 ROOT = 4
00027
00028
00029 class Quadtree(Container2D):
00030
00031
00032 class Node:
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045 def __init__(self, tree, grid, corner, dims, parent, corner_index):
00046 self.tree = tree
00047 self.corner = corner
00048 self.dims = dims
00049 self.parent = parent
00050 self.corner_index = corner_index
00051 self.x, self.y = corner
00052 self.width, self.height = dims
00053
00054 self.hw = self.width // 2
00055 self.hh = self.height // 2
00056
00057 if tree.measure.detail(grid, corner, dims, self.width*self.height/(grid.dims[0]*grid.dims[1])) < tree.threshold:
00058 self.value = tree.measure.aproximate(grid, corner, dims)
00059 self.children = None
00060 else:
00061 self.value = None
00062
00063 self.children = (
00064 tree.Node(self.tree, grid, corner, (self.hw, self.hh), self, TOP_LEFT),
00065 tree.Node(self.tree, grid, (self.x + self.hw, self.y), (self.width - self.hw, self.hh), self, TOP_RIGHT),
00066 tree.Node(self.tree, grid, (self.x, self.y + self.hh), (self.hw, self.height - self.hh), self, BOTTOM_LEFT),
00067 tree.Node(self.tree, grid, (self.x + self.hw, self.y + self.hh), (self.width - self.hw, self.height - self.hh), self, BOTTOM_RIGHT))
00068
00069
00070
00071 def __getitem__(self, p):
00072 return self.get_node(p).value
00073
00074
00075
00076
00077 def get_node(self, p):
00078 if self.value == None:
00079 i, j = p
00080
00081 if i < self.x + self.hw:
00082 if j < self.y + self.hh:
00083 return self.children[TOP_LEFT].get_node(p)
00084 else:
00085 return self.children[BOTTOM_LEFT].get_node(p)
00086 else:
00087 if j < self.y + self.hh:
00088 return self.children[TOP_RIGHT].get_node(p)
00089 else:
00090 return self.children[BOTTOM_RIGHT].get_node(p)
00091 else:
00092 return self
00093
00094
00095 def is_root(self):
00096 return self.corner_index == ROOT
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110 def is_left_node(self):
00111 return self.corner_index == TOP_LEFT or self.corner_index == BOTTOM_LEFT
00112
00113
00114 def is_right_node(self):
00115 return self.corner_index == TOP_RIGHT or self.corner_index == BOTTOM_RIGHT
00116
00117
00118 def is_top_node(self):
00119 return self.corner_index == TOP_LEFT or self.corner_index == TOP_RIGHT
00120
00121
00122 def is_bottom_node(self):
00123 return self.corner_index == BOTTOM_LEFT or self.corner_index == BOTTOM_RIGHT
00124
00125
00126 def get_left_parent(self):
00127 if self.is_root():
00128 return None
00129 if self.is_left_node():
00130 return self.parent.get_left_parent()
00131 elif self.corner_index == TOP_RIGHT:
00132 return self.parent.children[TOP_LEFT]
00133 else:
00134 return self.parent.children[BOTTOM_LEFT]
00135
00136
00137 def get_rightmost_node(self, y):
00138 if self.value == None:
00139 if y < self.y + self.hh:
00140 return self.children[TOP_RIGHT].get_rightmost_node(y)
00141 else:
00142 return self.children[BOTTOM_RIGHT].get_rightmost_node(y)
00143 else:
00144 return self
00145
00146
00147 def get_left_neighbor(self, p):
00148 node = self.get_left_parent()
00149
00150 if node == None:
00151 return None
00152 else:
00153 return node.get_rightmost_node(p[1])
00154
00155
00156 def get_right_parent(self):
00157 if self.is_root():
00158 return None
00159 if self.is_right_node():
00160 return self.parent.get_right_parent()
00161 elif self.corner_index == TOP_LEFT:
00162 return self.parent.children[TOP_RIGHT]
00163 else:
00164 return self.parent.children[BOTTOM_RIGHT]
00165
00166
00167 def get_leftmost_node(self, y):
00168 if self.value == None:
00169 if y < self.y + self.hh:
00170 return self.children[TOP_LEFT].get_leftmost_node(y)
00171 else:
00172 return self.children[BOTTOM_LEFT].get_leftmost_node(y)
00173 else:
00174 return self
00175
00176
00177 def get_right_neighbor(self, p):
00178 node = self.get_right_parent()
00179
00180 if node == None:
00181 return None
00182 else:
00183 return node.get_leftmost_node(p[1])
00184
00185
00186
00187 def get_top_parent(self):
00188 if self.is_root():
00189 return None
00190 if self.is_top_node():
00191 return self.parent.get_top_parent()
00192 elif self.corner_index == BOTTOM_LEFT:
00193 return self.parent.children[TOP_LEFT]
00194 else:
00195 return self.parent.children[TOP_RIGHT]
00196
00197
00198 def get_bottommost_node(self, x):
00199 if self.value == None:
00200 if x < self.x + self.hw:
00201 return self.children[BOTTOM_LEFT].get_bottommost_node(x)
00202 else:
00203 return self.children[BOTTOM_RIGHT].get_bottommost_node(x)
00204 else:
00205 return self
00206
00207
00208 def get_top_neighbor(self, p):
00209 node = self.get_top_parent()
00210
00211 if node == None:
00212 return None
00213 else:
00214 return node.get_bottommost_node(p[0])
00215
00216
00217 def get_bottom_parent(self):
00218 if self.is_root():
00219 return None
00220 if self.is_bottom_node():
00221 return self.parent.get_bottom_parent()
00222 elif self.corner_index == TOP_LEFT:
00223 return self.parent.children[BOTTOM_LEFT]
00224 else:
00225 return self.parent.children[BOTTOM_RIGHT]
00226
00227
00228 def get_topmost_node(self, x):
00229 if self.value == None:
00230 if x < self.x + self.hw:
00231 return self.children[TOP_LEFT].get_topmost_node(x)
00232 else:
00233 return self.children[TOP_RIGHT].get_topmost_node(x)
00234 else:
00235 return self
00236
00237
00238 def get_bottom_neighbor(self, p):
00239 node = self.get_bottom_parent()
00240
00241 if node == None:
00242 return None
00243 else:
00244 return node.get_topmost_node(p[0])
00245
00246
00247
00248
00249
00250
00251
00252 def interpolate(self, p):
00253 node = self.get_node(p)
00254
00255 left_node = self.get_left_neighbor(p)
00256 top_node = self.get_top_neighbor(p)
00257
00258 right_node = self.get_right_neighbor(p)
00259 bottom_node = self.get_bottom_neighbor(p)
00260
00261 if node.width == 1:
00262 return node.value
00263
00264 if left_node == None:
00265 col1 = node.value
00266 else:
00267 ratio1 = (p[0] - left_node.x - left_node.width) / (node.width - 1)
00268 col1 = self.tree.measure.blend(node.value, left_node.value, ratio1)
00269
00270 if top_node == None:
00271 col2 = node.value
00272 else:
00273 ratio2 = (p[1] - top_node.y - top_node.height) / (node.height - 1)
00274 col2 = self.tree.measure.blend(node.value, top_node.value, ratio2)
00275
00276 if right_node == None:
00277 col3 = node.value
00278 else:
00279 ratio3 = (right_node.x - p[0]) / node.width
00280 col3 = self.tree.measure.blend(node.value, right_node.value, ratio3)
00281
00282 if bottom_node == None:
00283 col4 = node.value
00284 else:
00285 ratio4 = (bottom_node.y - p[1]) / node.height
00286 col4 = self.tree.measure.blend(node.value, bottom_node.value, ratio4)
00287
00288 col_a = self.tree.measure.blend(col1, col2, 0.5)
00289 col_b = self.tree.measure.blend(col3, col4, 0.5)
00290
00291 return self.tree.measure.blend(col_a, col_b, 0.5)
00292
00293
00294
00295
00296
00297
00298 def interpolate2(self, p):
00299 x, y = p
00300 node = self.get_node(p)
00301 left_node = self.get_left_neighbor(p)
00302 top_node = self.get_top_neighbor(p)
00303
00304 right_node = self.get_right_neighbor(p)
00305 bottom_node = self.get_bottom_neighbor(p)
00306
00307 if None in (left_node, right_node, top_node, bottom_node):
00308 return node.value
00309
00310 top_y = top_node.y + top_node.height
00311 left_x = left_node.x + left_node.width
00312
00313 x1, y1 = (left_x + x) / 2, (y + top_y) / 2
00314 x2, y2 = (x + right_node.x) / 2, (top_y + y) / 2
00315 x3, y3 = (right_node.x + x) / 2, (y + bottom_node.y) / 2
00316 x4, y4 = (x + left_x) / 2, (y + bottom_node.y) / 2
00317
00318 dx1, dy1 = x1 - x, y1 - y
00319 dx2, dy2 = x2 - x, y2 - y
00320 dx3, dy3 = x3 - x, y3 - y
00321 dx4, dy4 = x4 - x, y4 - y
00322
00323 d1 = sqrt(dx1 * dx1 + dy1 * dy1)
00324 d2 = sqrt(dx2 * dx2 + dy2 * dy2)
00325 d3 = sqrt(dx3 * dx3 + dy3 * dy3)
00326 d4 = sqrt(dx4 * dx4 + dy4 * dy4)
00327
00328 a1 = d1 / (d1 + d3)
00329 a2 = d2 / (d2 + d3)
00330
00331 col1 = self.tree.measure.blend(right_node.value, top_node.value, 1-a1)
00332 col2 = self.tree.measure.blend(bottom_node.value, left_node.value, 1-a1)
00333
00334 return self.tree.measure.blend(col2, col1, 1-a2)
00335
00336
00337
00338
00339
00340
00341 def interpolate3(self, p):
00342 x, y = p
00343 node = self.get_node(p)
00344
00345 x1, y1 = node.x + node.hw, node.y + node.hh
00346
00347 col1 = node.value
00348 col2 = node.value
00349 col3 = node.value
00350
00351 x2, y2 = x, y
00352 x3, y3 = x, y
00353
00354
00355
00356 if x < x1:
00357 left_node = self.get_left_neighbor(p)
00358
00359 if left_node != None:
00360 x3, y3 = left_node.x + left_node.width, y
00361 col3 = left_node.value
00362 else:
00363 x3, y3 = node.x, y
00364
00365 if y < y1:
00366 top_node = self.get_top_neighbor(p)
00367
00368 if top_node != None:
00369 x2, y2 = x, top_node.y + top_node.height
00370 col2 = top_node.value
00371 else:
00372 x2, y2 = x, node.y
00373
00374 else:
00375 bottom_node = self.get_bottom_neighbor(p)
00376
00377 if bottom_node != None:
00378 x2, y2 = x, bottom_node.y
00379 col2 = bottom_node.value
00380 else:
00381 x2, y2 = x, node.y + node.height
00382
00383 else:
00384 right_node = self.get_right_neighbor(p)
00385
00386 if right_node != None:
00387 x3, y3 = right_node.x, y
00388 col3 = right_node.value
00389 else:
00390 x3, y3 = node.x + node.width, y
00391
00392 if y < y1:
00393 top_node = self.get_top_neighbor(p)
00394
00395 if top_node != None:
00396 x2, y2 = x, top_node.y + top_node.height
00397 col2 = top_node.value
00398 else:
00399 x2, y2 = x, node.y
00400
00401 else:
00402 bottom_node = self.get_bottom_neighbor(p)
00403
00404 if bottom_node != None:
00405 x2, y2 = x, bottom_node.y
00406 col2 = bottom_node.value
00407 else:
00408 x2, y2 = x, node.y + node.height
00409
00410 col2 = self.tree.measure.blend(col2, col1, 0.5)
00411 col3 = self.tree.measure.blend(col3, col1, 0.5)
00412
00413 dx1, dy1 = x1 - x, y1 - y
00414 dx2, dy2 = x2 - x, y2 - y
00415 dx3, dy3 = x3 - x, y3 - y
00416
00417 d1 = sqrt(dx1 * dx1 + dy1 * dy1)
00418 d2 = sqrt(dx2 * dx2 + dy2 * dy2)
00419 d3 = sqrt(dx3 * dx3 + dy3 * dy3)
00420
00421 s = (d1 + d2 + d3)
00422 col0 = (0, 255, 255, 255)
00423 if s == 0:
00424 return col0
00425
00426 ratio1 = 1-(2*(d1) / s)
00427 ratio2 = 1-(2*(d2) / s)
00428 ratio3 = 1-(2*(d3) / s)
00429 col4 = (255, 0, 0, 255)
00430 col5 = (0, 255, 0, 255)
00431 col6 = (0, 0, 255, 255)
00432
00433 return self.tree.measure.blend3(col1, col2, col3, ratio1, ratio2, ratio3)
00434
00435
00436 def index_iter(self):
00437 return self.tree.window_index_iter((self.corner), (self.x+self.width, self.y+self.height))
00438
00439
00440
00441
00442
00443
00444 def count(self, count_self = True):
00445 if(self.value == None):
00446 count = 1 if count_self else 0
00447
00448 for child in self.children:
00449 count += child.count(count_self)
00450
00451 return count
00452 return 1
00453
00454
00455
00456
00457
00458
00459 def __init__(self, grid, measure, threshold):
00460 self.measure = measure
00461 self.threshold = threshold
00462 self.root = Quadtree.Node(self, grid, (0, 0), grid.dims, None, ROOT)
00463 self.dims = grid.dims
00464 self.width, self.height = self.dims
00465
00466
00467 def __getitem__(self, p):
00468 return self.root[p[0], p[1]]
00469
00470
00471
00472 def count(self, count_self):
00473 return self.root.count(count_self)
00474
00475
00476
00477 class AbstractMeasure:
00478
00479
00480
00481
00482
00483
00484 def detail(self, grid, corner, dims, bias):
00485 raise NotImplementedError()
00486
00487
00488
00489
00490 def aproximate(self, grid, corner, dims):
00491 raise NotImplementedError()
00492
00493
00494
00495
00496 def blend(self, col1, col2, ratio):
00497 raise NotImplementedError()
00498
00499
00500
00501
00502 def blend3(self, col1, col2, col3, ratio1, ratio2, ratio3):
00503 raise NotImplementedError()
00504
00505
00506
00507
00508
00509
00510 class Measure(AbstractMeasure):
00511
00512
00513
00514 def detail(self, grid, corner, dims, bias):
00515 average = self.aproximate(grid, corner, dims)
00516
00517 w, h = dims
00518 x, y = corner
00519 end_corner = (x + w, y + h)
00520 sum = 0
00521
00522 for cell in grid.window_iter(corner, end_corner):
00523 sum += abs(average - cell)
00524
00525 return sum / (w * h)
00526
00527
00528 def aproximate(self, grid, corner, dims):
00529 w, h = dims
00530 x, y = corner
00531 end_corner = (x + w, y + h)
00532 sum = 0
00533
00534 for cell in grid.window_iter(corner, end_corner):
00535 sum += cell
00536
00537 return sum / (w*h)
00538
00539
00540 def blend(self, col1, col2, ratio):
00541 col = col1 * ratio + col2 * (1 - ratio)
00542
00543 return col
00544
00545
00546 def blend3(self, col1, col2, col3, ratio1, ratio2, ratio3):
00547 col = col1 * ratio1 + col2 * ratio2 + col3 * ratio3