散装装载点

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函数：

^{pr2}$

以及QuadNode：

^{3}$

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

• swNodepoint.x < parent.x和{}
• seNodepoint.x >= parent.x和{}
• nwNodepoint.x < parent.x和{}
• neNodepoint.x >= parent.x和{}

Answer 1

您选择中间层的方法是正确的（正如Finkel的原始文章《Quadtrees:A data structure for retrieval on composite keys中所述），但是为子树构建子集合的方法是错误的。在

例如，对于这个排序列表：

[(1, 1), (1, 2), (1, 3)]

中位数是1, 2，并且，根据你的边界规则，1,1必须在SE，1,3在东北。
在原文中，SE和NW是“开”的，NW和SE是闭的：1,1是NW，1,3是SE。正如您在边界定义中看到的，中间带之前的所有元素都位于东南或西北，而中间带之后的所有元素都位于西南或东北。但这不符合你对边界的定义。在

所以要么你的边界定义有问题，要么你必须检查列表中的每个元素，以确保它在正确的区域结束。例如：

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]]

然而，这是相当丑陋的，并不能确保树将是平衡的。我宁愿检查边界的定义。。。。在