Recursively divide the space (rectangle) into four Quad-tree Implemented
If a certain area contains more than the preset maximum number of data points, the area is recursively divided into four.
If there are multiple identical data points, the division may be repeated indefinitely, so specify the maximum number of 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):
"""Add data points to the area"""
self.points_.append(p)
def points(self):
"""Returns the data points that belong to the region"""
return self.points_
def is_fixed(self):
"""Whether the split is over"""
return self.fixed
def set_fixed(self):
"""Flag the split is complete"""
self.fixed = True
def cover(self, p):
"""Whether a data point p is covered in this area"""
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 = []
"""Length of each side after division"""
xl = (area.x2 - area.x1)/2
yl = (area.y2 - area.y1)/2
"""Generate area after 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)
"""Assign data points belonging to the area before division to the area after 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]
"""Repeat the division only maxdivision times given by the argument"""
for n in range(maxdivision):
new_areas = []
for i in range(len(areas)):
if not areas[i].is_fixed():
"""For areas that have not yet been split"""
if len(areas[i].points()) > maxpoints:
"""Divide if the number of data points belonging to the area exceeds maxpoints"""
division = divide(areas[i],n+1)
for d in division:
new_areas.append(d)
else:
"""If the number of data points belonging to the area does not exceed maxpoints, do not divide anymore"""
areas[i].set_fixed()
new_areas.append(areas[i])
else:
"""If the division is finished, leave it as it is"""
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])
"""Generate the target area"""
initial = Area(x1,y1,x2,y2,0)
for d in data:
initial.append(d)
"""Split"""
qtree = quadtree(data, initial, maxpoints, maxdivision)
"""result"""
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
Arrange data points vertically in the data file given as input
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
Arguments are given in the order of the area to be divided (x1, y1, x2, y2), the maximum number, the maximum number of divisions, and the data file.
As a result, the area (x1, y1, x2, y2) and the data points containing it are output in one line.
>> 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