Der Raum (rechteckig) ist rekursiv in vier [Quad-Tree] unterteilt (http://ja.wikipedia.org/wiki/%E5%9B%9B%E5%88%86%E6%9C%A8). Implementiert
Wenn ein bestimmter Bereich mehr als die voreingestellte maximale Anzahl von Datenpunkten enthält, wird der Bereich rekursiv in vier Bereiche unterteilt.
Wenn mehrere identische Datenpunkte vorhanden sind, kann die Unterteilung auf unbestimmte Zeit wiederholt werden. Geben Sie daher die maximale Anzahl von Unterteilungen an.
# -*- 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):
"""Fügen Sie dem Bereich Datenpunkte hinzu"""
self.points_.append(p)
def points(self):
"""Gibt die Datenpunkte zurück, die zur Region gehören"""
return self.points_
def is_fixed(self):
"""Ob die Trennung vorbei ist"""
return self.fixed
def set_fixed(self):
"""Setzen Sie das Flag, dass die Teilung beendet ist"""
self.fixed = True
def cover(self, p):
"""Ob ein Datenpunkt p in diesem Bereich abgedeckt ist"""
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 = []
"""Länge jeder Seite nach der Teilung"""
xl = (area.x2 - area.x1)/2
yl = (area.y2 - area.y1)/2
"""Fläche nach Teilung erzeugen"""
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)
"""Weisen Sie dem Bereich nach der Division Datenpunkte zu, die zum Bereich vor der Division gehören"""
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]
"""Wiederholen Sie die durch das Argument angegebene Division nur für die maximale Division"""
for n in range(maxdivision):
new_areas = []
for i in range(len(areas)):
if not areas[i].is_fixed():
"""Für Bereiche, die noch nicht aufgeteilt wurden"""
if len(areas[i].points()) > maxpoints:
"""Teilen Sie, wenn die Anzahl der zu dem Bereich gehörenden Datenpunkte die Maximalpunkte überschreitet"""
division = divide(areas[i],n+1)
for d in division:
new_areas.append(d)
else:
"""Wenn die Anzahl der zu dem Bereich gehörenden Datenpunkte die Maximalpunkte nicht überschreitet, teilen Sie nicht mehr"""
areas[i].set_fixed()
new_areas.append(areas[i])
else:
"""Wenn die Teilung abgeschlossen ist, lassen Sie sie unverändert"""
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])
"""Generieren Sie den Zielbereich"""
initial = Area(x1,y1,x2,y2,0)
for d in data:
initial.append(d)
"""Teilt"""
qtree = quadtree(data, initial, maxpoints, maxdivision)
"""Ergebnis"""
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
Ordnen Sie Datenpunkte vertikal in der als Eingabe angegebenen Datendatei an
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
Die Argumente werden in der Reihenfolge des zu teilenden Bereichs (x1, y1, x2, y2), der maximalen Anzahl, der maximalen Anzahl von Unterteilungen und der Datendatei angegeben.
Infolgedessen werden der Bereich (x1, y1, x2, y2) und die Datenpunkte, die ihn enthalten, in einer Zeile ausgegeben.
>> 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
Recommended Posts