简单的四叉树的 Python 代码实现

四叉树是一种用于存储和管理二维空间中的对象的数据结构。它通常用于地图、图像等二维数据的存储和管理。

下面是一个简单的 Python 代码实现：

class QuadTreeNode:
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height
        self.objects = []
        self.subtrees = [None, None, None, None]
 
    def insert(self, obj):
        if len(self.subtrees[0]) > 0:
            # 如果有子节点，则插入到子节点
            index = self.get_subtree_index(obj)
            if index != -1:
                self.subtrees[index].insert(obj)
                return
 
        # 如果没有子节点或者对象不在子节点范围内，则插入到当前节点
        self.objects.append(obj)
 
        # 如果对象数量超过阈值，则分裂
        if len(self.objects) > 4:
            self.split()
 
    def split(self):
        x = self.x
        y = self.y
        width = self.width
        height = self.height
        half_width = width / 2
        half_height = height / 2
 
        # 创建子节点
        self.subtrees[0] = QuadTreeNode(x, y, half_width, half_height)
        self.subtrees[1] = QuadTreeNode(x + half_width, y, half_width, half_height)
        self.subtrees[2] = QuadTreeNode(x, y + half_height, half_width, half_height)
        self.subtrees[3] = QuadTreeNode(x + half_width, y + half_height, half_width, half_height)
 
        # 将原来存在当前节点的对象插入到子节点中
        for obj in self.objects:
            index = self.get_subtree_index(obj)
            if index != -1:
                self.subtrees[index].insert(obj)
 
        # 清空当前节点