Divisez récursivement l'espace (rectangulaire) en quatre Quad-tree Mis en œuvre
Si une certaine zone contient plus que le nombre maximum prédéfini de points de données, la zone est divisée récursivement en quatre.
S'il y a plusieurs points de données identiques, la division peut être répétée indéfiniment, spécifiez donc le nombre maximum de divisions.
# -*- 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):
"""Ajouter des points de données à la zone"""
self.points_.append(p)
def points(self):
"""Renvoie les points de données appartenant à la région"""
return self.points_
def is_fixed(self):
"""Si la scission est terminée"""
return self.fixed
def set_fixed(self):
"""Définissez le drapeau indiquant que la division est terminée"""
self.fixed = True
def cover(self, p):
"""Si un point de données p est couvert dans cette zone"""
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 = []
"""Longueur de chaque côté après division"""
xl = (area.x2 - area.x1)/2
yl = (area.y2 - area.y1)/2
"""Générer une zone après la division"""
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)
"""Attribuer des points de données appartenant à la zone avant la division à la zone après la division"""
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]
"""Répétez la division uniquement division max donnée par l'argument"""
for n in range(maxdivision):
new_areas = []
for i in range(len(areas)):
if not areas[i].is_fixed():
"""Pour les zones qui n'ont pas encore été divisées"""
if len(areas[i].points()) > maxpoints:
"""Divisez si le nombre de points de données appartenant à la zone dépasse maxpoints"""
division = divide(areas[i],n+1)
for d in division:
new_areas.append(d)
else:
"""Si le nombre de points de données appartenant à la zone ne dépasse pas maxpoints, ne divisez plus"""
areas[i].set_fixed()
new_areas.append(areas[i])
else:
"""Si la division est terminée, laissez-la telle quelle"""
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])
"""Générer la zone cible"""
initial = Area(x1,y1,x2,y2,0)
for d in data:
initial.append(d)
"""Divisé"""
qtree = quadtree(data, initial, maxpoints, maxdivision)
"""résultat"""
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
Organiser les points de données verticalement dans le fichier de données donné en entrée
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
Les arguments sont donnés dans l'ordre de la zone à diviser (x1, y1, x2, y2), le nombre maximum, le nombre maximum de divisions et le fichier de données.
En conséquence, la zone (x1, y1, x2, y2) et les points de données la contenant sont affichés sur une seule ligne.
>> 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