PythonでQuad-tree（領域分割）


空間（矩形）を再帰的に４分割していく[Quad-tree](http://ja.wikipedia.org/wiki/%E5%9B%9B%E5%88%86%E6%9C%A8)を実装した

ある領域にあらかじめ設定した最大個数以上のデータ点が含まれていたらその再帰的に領域を４分割する

全く同じデータ点が複数存在している場合無限に分割を繰り返してしまう事があるので、最大の分割回数を指定する

```python
# -*- 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
```