python - 散装点四叉树

Question

我实现了一种批量加载点四叉树的方法。但对于某些输入，它无法正常工作，例如，如果有许多点具有相同的 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

Answer 1

您选择中间层的方法是正确的(如 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]]

然而，这非常丑陋，并且不能确保树是平衡的。我宁愿检查边界的定义....