用python3.6的版本 四叉树均匀特征点

四叉树是一种数据结构，用于对空间进行划分和查询。在计算机图形学和计算机视觉中，四叉树常用于均匀地对特征点进行采样和描述。下面是一个使用Python 3.6实现的四叉树均匀特征点采样程序。

import numpy as np

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class QuadTree:
    def __init__(self, x1, y1, x2, y2, depth=0, max_depth=10, max_points=10):
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
        self.depth = depth
        self.max_depth = max_depth
        self.max_points = max_points
        self.points = []
        self.children = []

    def add_point(self, point):
        if len(self.children) == 0:
            self.points.append(point)
            if len(self.points) > self.max_points and self.depth < self.max_depth:
                self.split()
        else:
            for child in self.children:
                if self.is_inside(child, point):
                    child.add_point(point)
                    break

    def is_inside(self, child, point):
        return child.x1 <= point.x <= child.x2 and child.y1 <= point.y <= child.y2

    def split(self):
        cx = (self.x1 + self.x2) / 2
        cy = (self.y1 + self.y2) / 2
        self.children.append(QuadTree(self.x1, self.y1, cx, cy, self.depth+1, self.max_depth, self.max_points))
        self.children.append(QuadTree(cx, self.y1, self.x2, cy, self.depth+1, self.max_depth, self.max_points))
        self.children.append(QuadTree(self.x1, cy, cx, self.y2, self.depth+1, self.max_depth, self.max_points))
        self.children.append(QuadTree(cx, cy, self.x2, self.y2, self.depth+1, self.max_depth, self.max_points))
        for point in self.points:
            self.add_point(point)
        self.points = []

    def get_points(self):
        if len(self.children) > 0:
            points = []
            for child in self.children:
                points.extend(child.get_points())
            return points
        else:
            return self.points

def uniform_sampling(width, height, num_points):
    points = []
    tree = QuadTree(0, 0, width, height, max_depth=10, max_points=10)
    for i in range(num_points):
        point = Point(np.random.randint(0, width), np.random.randint(0, height))
        tree.add_point(point)
    return tree.get_points()

if __name__ == '__main__':
    width = 640
    height = 480
    num_points = 100
    points = uniform_sampling(width, height, num_points)
    print(len(points))

这个程序使用了一个Point类来表示二维空间中的点，使用一个QuadTree类来表示四叉树数据结构。uniform_sampling函数使用QuadTree来对空间进行均匀采样，并返回采样点的集合。在主函数中，我们使用这个函数来采样一个640x480的空间，共100个点，并输出采样点的数量。

请注意，这个程序中的QuadTree实现并没有考虑空间中已有的点的分布情况，因此不能保证采样结果的质量。如果需要更高质量的采样，可以考虑使用基于能量的方法来优化采样点的分布。