python– 批量加载点四叉树

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

我已经实现了一种批量加载点四叉树的方法.但对于某些输入,它无法正常工作,例如,如果有许多点具有相同的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 – 批量加载点四叉树所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。