我试图建立一个点区域四叉树存储点在二维地图上与Python,但当我试图插入两个点这是接近(不太接近)彼此,我遇到一个错误: RuntimeError:最大递归深度超过在cmp.我试图提高最大递归数到10000,但不起作用。所以我想有什么问题在我的代码。有人能帮我这个好吗?我是一个新人在编程,已经被困在这两天。BTW,如果你发现任何代码写得不“专业”我真的很感激,如果你能教我如何写在适当的方式。提前非常感谢!
每个点由它的坐标(x, z)和一个指向另一个文件中该点数据的指针组成。在四叉树中,每个点只存储一个点,因此a)当将一个点插入到一个没有子点和没有点的区域时,该点就进入了这个区域;b)当一个区域有孩子时,我们尝试将该点插入到它的一个孩子中。c)当将一个点插入到没有孩子但已经被一个点占据的区域时,这个区域被细分为四个相等的子区域,旧的点从这个区域中取出并放入其中一个子区域中。然后,我们尝试将新点插入孩子们。
class point():
def __init__(self,x,z,pointer):
self.x = x
self.z = z
self.pointer = pointer
class Node():
#_______________________________________________________
# In the case of a root node "parent" will be None. The
# "rect" lists the minx,minz,maxx,maxz of the rectangle
# represented by the node.
def __init__(self, parent, rect):
self.parent = parent
self.children = None
self.point = None
self.leaf = 0 # node is a leaf(=1) if it contains a point
if parent == None:
self.depth = 0
else:
self.depth = parent.depth + 1
self.rect = rect
x0,z0,x1,z1 = rect
#_______________________________________________________
# Subdivides a rectangle. Division occurs
def subdivide(self):
self.point = None
self.leaf = 0
self.children = [None,None,None,None]
x0,z0,x1,z1 = self.rect
h = (x1 - x0)/2
rects = []
rects.append( (x0, z0, x0 + h, z0 + h) )
rects.append( (x0, z0 + h, x0 + h, z1) )
rects.append( (x0 + h, z0 + h, x1, z1) )
rects.append( (x0 + h, z0, x1, z0 + h) )
for n in xrange(len(rects)):
self.children[n] = Node(self,rects[n])
#_______________________________________________________
# A utility proc that returns True if the coordinates of
# a point are within the bounding box of the node.
def contains(self, x, z):
x0,z0,x1,z1 = self.rect
if x >= x0 and x <= x1 and z >= z0 and z <= z1:
return True
return False
def insert(self, p):
if self.contains(p.x, p.z) == False:
return
if self.children == None:
if self.leaf == 1:
temp_point = copy.copy(self.point)
self.subdivide()
self.insert(temp_point)
self.insert(p)
else:
self.point = p
self.leaf = 1
else:
for child in self.children:
child.insert(p)
h = (x1 - x0)/2
如果使用Python2.7,并且x1和x0都是整数,则此除法的结果将被截断为最接近的整数。例如,如果x1为1,x0为0,则可能期望它们的中点为0.5。但是(1-0)/2
等于0。这会导致sub分
中的问题,其中四个子rect中的三个将非常小,而第四个将与父rect相同大小。尝试强制执行浮点除法。
h = (x1 - x0)/2.0