批量加载点四叉树

Question

批量加载点四叉树

5

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

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

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

这是create函数：

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 时

- greedsin

所以现在的输出是[(1, 15), (3, 1), (5, 4), (5, 10), (9, 6), (11, 4), (11, 5), (11, 15), (12, 16), (16, 1), (19, 17)]。你希望输出什么？我有点忘记四叉树是如何工作的了... - gsamaras

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pierre Rust · Accepted Answer

你选择中间值的方法是正确的（正如Finkel在他的原始文章《四叉树：一种用于复合键检索的数据结构》中所解释的），但你建立子树的子集的方式是错误的。

例如，使用此排序列表： [(1, 1), (1, 2), (1, 3)] 中位数是1,2，根据您的边界规则，1,1必须在SE中，1,3必须在NE中。
在原始文章中，SE和NW是“开放”的，NW和SE是“关闭”的：1,1在NW中，1,3在SE中。如您所见，使用这种边界定义，中位数之前的所有元素都将在SE或NW中，中位数之后的所有元素都将在SW或NE中。但是，您的边界定义不符合这一点。

因此，要么您的边界定义有问题，要么您必须检查列表的每个元素，以确保它被放置在正确的区域。例如：

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) for x,y  in point_list if x < relevantPoint[0] and y < relevantPoint[1]]
seBins = [(x,y) for x,y  in point_list if x >= relevantPoint[0] and y <= relevantPoint[1]]
neBins = [(x,y) for x,y  in point_list if x <= relevantPoint[0] and y > relevantPoint[1]]

然而，这样做很丑陋，并不能确保树的平衡。我宁愿检查边界的定义...