空間（矩形）を再帰的に４分割していくQuad-treeを実装した
ある領域にあらかじめ設定した最大個数以上のデータ点が含まれていたらその再帰的に領域を４分割する
全く同じデータ点が複数存在している場合無限に分割を繰り返してしまう事があるので、最大の分割回数を指定する
# -*- coding: utf-8 -*-
import sys
class Area:
def __init__(self,x1,y1,x2,y2,level):
self.x1 = x1
self.y1 = y1
self.x2 = x2
self.y2 = y2
self.level = level
self.points_ = []
self.fixed = False
def append(self, p):
""" 領域にデータ点を追加 """
self.points_.append(p)
def points(self):
""" 領域に属しているデータ点を返す """
return self.points_
def is_fixed(self):
""" 分割が終わっているかどうか """
return self.fixed
def set_fixed(self):
""" 分割が終わったフラグを立てる """
self.fixed = True
def cover(self, p):
""" あるデータ点pがこの領域にカバーされるかどうか """
if self.x1 < p[0] and self.y1 < p[1] and self.x2 >= p[0] and self.y2 >= p[1]:
return True
else:
return False
def divide(area,level):
division = []
""" 分割後の各辺の長さ """
xl = (area.x2 - area.x1)/2
yl = (area.y2 - area.y1)/2
""" 分割後の領域を生成 """
for dx in [0,1]:
for dy in [0,1]:
sub_area = Area(area.x1+dx*xl, area.y1+dy*yl, area.x1+(1+dx)*xl, area.y1+(1+dy)*yl,level)
division.append(sub_area)
""" 分割前の領域に属すデータ点を分割後の領域にアサイン """
for p in area.points():
for sub_area in division:
if sub_area.cover(p):
sub_area.append(p)
break
return division
def quadtree(data, initial, maxpoints, maxdivision):
areas = [initial]
""" 引数で与えられたmaxdivision回だけ分割を繰り返す """
for n in range(maxdivision):
new_areas = []
for i in range(len(areas)):
if not areas[i].is_fixed():
""" まだ分割が終わっていない領域に対して """
if len(areas[i].points()) > maxpoints:
""" 領域に属すデータ点の数がmaxpoints個を超えていたら分割 """
division = divide(areas[i],n+1)
for d in division:
new_areas.append(d)
else:
""" 領域に属すデータ点の数がmaxpoints個を超えていなかったらもう分割しない """
areas[i].set_fixed()
new_areas.append(areas[i])
else:
""" 分割が終わっていればそのまま """
new_areas.append(areas[i])
areas = new_areas
return areas
def read_data(file_name):
data = []
for line in open(file_name, 'r'):
p = tuple([float(v) for v in line.rstrip().split(' ')])
data.append(p)
return data
x1 = float(sys.argv[1])
y1 = float(sys.argv[2])
x2 = float(sys.argv[3])
y2 = float(sys.argv[4])
maxpoints = int(sys.argv[5])
maxdivision = int(sys.argv[6])
data = read_data(sys.argv[7])
""" 対象とする領域を生成 """
initial = Area(x1,y1,x2,y2,0)
for d in data:
initial.append(d)
""" 分割 """
qtree = quadtree(data, initial, maxpoints, maxdivision)
""" 結果 """
for a in qtree:
print "%s %s %s %s" % (a.x1, a.y1, a.x2, a.y2),
for p in a.points():
print p,
print
入力として与えるデータファイルには縦にデータ点を並べる
0.567603099626 0.410160220857
0.405568042222 0.555583016695
0.450289054963 0.252870772505
0.373657009068 0.549501477427
0.500192599714 0.352420542886
0.626796922 0.422685113179
0.527521290061 0.483502904656
0.407737520746 0.570049935936
0.578095278433 0.6959689898
0.271957975882 0.450460115198
0.56451369371 0.491139311353
0.532304354436 0.486931064003
0.553942716039 0.51953331907
0.627341495722 0.396617894317
0.454210189397 0.570214499065
0.327359895038 0.582972137899
0.422271372537 0.560892624101
0.443036148978 0.434529240506
0.644625936719 0.542486338813
0.447813648487 0.575896033203
0.534217713171 0.636123087401
0.348346109137 0.312959224746
0.484075186327 0.289521849258
0.588417643962 0.387831556678
0.613422176662 0.665770829308
0.60994411786 0.399778040078
0.425443751505 0.402619561402
0.504955932504 0.610015349003
0.402852203978 0.382379275531
0.387591801531 0.452180343665
実行
引数は分割の対象とする領域(x1,y1,x2,y2)、最大個数、最大分割数、データファイルの順で与える
結果は領域（x1,y1,x2,y2）と、それの含まれるデータ点が一行に出力される
>> python quadtree.py 0 0 1 1 3 3 data
0.0 0.0 0.25 0.25
0.0 0.25 0.25 0.5
0.25 0.0 0.5 0.25
0.25 0.25 0.375 0.375 (0.348346109137, 0.312959224746)
0.25 0.375 0.375 0.5 (0.271957975882, 0.450460115198)
0.375 0.25 0.5 0.375 (0.450289054963, 0.252870772505) (0.484075186327, 0.289521849258)
0.375 0.375 0.5 0.5 (0.443036148978, 0.434529240506) (0.425443751505, 0.402619561402) (0.402852203978, 0.382379275531) (0.387591801531, 0.452180343665)
0.0 0.5 0.25 0.75
0.0 0.75 0.25 1.0
0.25 0.5 0.375 0.625 (0.373657009068, 0.549501477427) (0.327359895038, 0.582972137899)
0.25 0.625 0.375 0.75
0.375 0.5 0.5 0.625 (0.405568042222, 0.555583016695) (0.407737520746, 0.570049935936) (0.454210189397, 0.570214499065) (0.422271372537, 0.560892624101) (0.447813648487, 0.575896033203)
0.375 0.625 0.5 0.75
0.25 0.75 0.5 1.0
0.5 0.0 0.75 0.25
0.5 0.25 0.625 0.375 (0.500192599714, 0.352420542886)
0.5 0.375 0.625 0.5 (0.567603099626, 0.410160220857) (0.527521290061, 0.483502904656) (0.56451369371, 0.491139311353) (0.532304354436, 0.486931064003) (0.588417643962, 0.387831556678) (0.60994411786, 0.399778040078)
0.625 0.25 0.75 0.375
0.625 0.375 0.75 0.5 (0.626796922, 0.422685113179) (0.627341495722, 0.396617894317)
0.75 0.0 1.0 0.25
0.75 0.25 1.0 0.5
0.5 0.5 0.625 0.625 (0.553942716039, 0.51953331907) (0.504955932504, 0.610015349003)
0.5 0.625 0.625 0.75 (0.578095278433, 0.6959689898) (0.534217713171, 0.636123087401) (0.613422176662, 0.665770829308)
0.625 0.5 0.75 0.625 (0.644625936719, 0.542486338813)
0.625 0.625 0.75 0.75
0.5 0.75 0.75 1.0
0.75 0.5 1.0 0.75
0.75 0.75 1.0 1.0