我已经实现了一种批量加载点四叉树的方法.但对于某些输入,它无法正常工作,例如,如果有许多点具有相同的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：用于检索复合键的数据结构中所述),但是为子树构建子集合的方式是错误的.
原文链接：https://www.f2er.com/python/438742.html例如,使用此排序列表：
[(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]]
然而,这非常难看,并不能确保树平衡.我宁愿检查边界的定义……