python – 批量加载点四叉树

我已经实现了一种批量加载点四叉树的方法.但对于某些输入,它无法正常工作,例如,如果有许多点具有相同的x坐标或y坐标.
示例数据集将是：

test = [(3,1),(16,(11,4),(5,(9,6),10),(1,15),5),(12,16),(19,17)]
tree = create(test)

问题出现在以下几点：(11,15)和(5,4).

这是创建功能：

def create(point_list,presorted=False):
    if not point_list:
        return QuadNode()

    if not presorted:
        point_list.sort(key=lambda p: [p[0],p[1]])

    median = len(point_list) >> 1

    relevantPoint = point_list[median]
    relevantYCoordinate = relevantPoint[1]

    node = QuadNode(data=relevantPoint)

    leftBins = point_list[:median]
    rightBins = point_list[median + 1:]

    nwBins = [bin for bin in leftBins if bin[1] >= relevantYCoordinate]
    swBins = [bin for bin in leftBins if bin[1] < relevantYCoordinate]

    neBins = [bin for bin in rightBins if bin[1] >= relevantYCoordinate]
    seBins = [bin for bin in rightBins if bin[1] < relevantYCoordinate]

    node.nwNode = create(nwBins,presorted=True)
    node.swNode = create(swBins,presorted=True)

    node.neNode = create(neBins,presorted=True)
    node.seNode = create(seBins,presorted=True)
    return node

和QuadNode：

class QuadNode(object):
    def __init__(self,data=None,nwNode=None,neNode=None,swNode=None,seNode=None):
        self.data = data
        self.nwNode = nwNode
        self.neNode = neNode
        self.swNode = swNode
        self.seNode = seNode

我想遵循插入,删除等规则：

> swNode point.x< parent.x和point.y< parent.y
> seNode point.x> = parent.x和point.y< parent.y
> nwNode point.x< parent.x和point.y> = parent.y
> neNode point.x> = parent.x和point.y> = parent.y

最佳答案

您选择中间的方法是正确的(如Finkel的原始文章Quadtrees：用于检索复合键的数据结构中所述),但是为子树构建子集合的方式是错误的.

例如,使用此排序列表：

[(1,2),3)]

中位数为1,2,根据您的边界规则,1,1必须在SE中,3在NE中.
在原始文章中,SE和NW是“开放的”,NW和SE是封闭的：1,1在NW中,3在SE中.正如你可以看到边界的这个定义,中位数之前的所有元素都在SE或NW中,中位数之后的所有元素都在SW或NE中.但这并不符合您对边界的定义.

因此,要么边界定义有问题,要么必须检查列表中的每个元素以确保它最终位于正确的区域.对于eaxmple：

relevantPoint = point_list[median]
node = QuadNode(data=relevantPoint)
del point_list[median]

nwBins = [(x,y) for x,y  in point_list if x < relevantPoint[0] and y >= relevantPoint[1]]
swBins = [(x,y  in point_list if x < relevantPoint[0] and y < relevantPoint[1]]
seBins = [(x,y  in point_list if x >= relevantPoint[0] and y <= relevantPoint[1]]
neBins = [(x,y  in point_list if x <= relevantPoint[0] and y > relevantPoint[1]]

然而,这非常难看,并不能确保树平衡.我宁愿检查边界的定义……

python – 批量加载点四叉树

猜你在找的Python相关文章