散装点四叉树
Bulk loading point quadtree
我实现了一种批量加载点四叉树的方法。但对于某些输入,它无法正常工作,例如,如果有许多点具有相同的 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
你选择中间的方法是正确的(如Finkel的原始文章Quadtrees: A data structure for retrieval on composite keys),但是您为子树构建子集合的方式是错误的。
例如这个排序列表:
[(1, 1), (1, 2), (1, 3)]
中位数是 1, 2
,根据您的边界规则,1,1
必须在 SE 中,1,3
必须在 NE 中。
原文中SE和NW是'open',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]]
然而,这很丑陋并且不能确保树是平衡的。我宁愿检查边界的定义....
我实现了一种批量加载点四叉树的方法。但对于某些输入,它无法正常工作,例如,如果有许多点具有相同的 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
你选择中间的方法是正确的(如Finkel的原始文章Quadtrees: A data structure for retrieval on composite keys),但是您为子树构建子集合的方式是错误的。
例如这个排序列表:
[(1, 1), (1, 2), (1, 3)]
中位数是 1, 2
,根据您的边界规则,1,1
必须在 SE 中,1,3
必须在 NE 中。
原文中SE和NW是'open',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]]
然而,这很丑陋并且不能确保树是平衡的。我宁愿检查边界的定义....