我尝试在python中创建一个四叉树结构来检测多边形之间的碰撞,我已经做了很多工作(见文章末尾)。然而,我意识到这种结构只适用于点,因为我是根据对象的中心来决定将对象放在哪个叶中。在
所以我需要弄清楚如何修改这个四叉树,这样我就可以检测出区域的碰撞(就像一个圆!)。在
我可以用几种不同的方法来思考这个问题:
选项#2(将对象放置在多个节点中),我觉得最好是在对象周围绘制一个边界矩形,然后使用对象的范围来决定将它放在哪个叶中——但这需要有效地将每个对象插入4次(每个角点一次),这似乎是一种低效的方法问题。在
有更好的建议吗?在
class Quadtree(object):
"""
A simple Quadtree implementation. This works with any child object that has a getPosition() method that returns a list or tuple.
"""
def __init__(self, depth, min_x, min_y, max_x, max_y):
self.mDepth = depth
self.mMaxDepth = 4
self.mMinX = min_x
self.mMaxX = max_x
self.mMidX = (max_x - min_x) / 2.0
self.mMinY = min_y
self.mMaxY = max_y
self.mMidY = (max_y - min_y) / 2.0
self.mHasChildren = False
self.mMaxChildren = 8
self.mChildren = []
self.mSubtrees = []
def insert(self, newChild):
"""
Insert an object into the tree. Returns True if the insert was successful, False otherwise.
"""
if self.mSubtrees:
#if subtrees exist, add the child to the subtrees
index = getIndex(newChild)
if index != -1:
self.mSubtrees[index].insert(newChild)
return True
#if no subtrees exist, add the child to the child list.
self.mChildren.append(newChild)
#and then check if we need to split the tree
#if there are more than the max children, and we haven't maxed out the tree depth, and there are no subtrees yet
if len(self.mChildren) > self.mMaxChildren and self.mDepth < self.mMaxDepth and not self.mSubtrees:
split()
for child in self.mChildren:
index = getIndex(child)
if index != -1:
self.mSubtrees[index].insert(child)
return True
return False
def retrieveNeighbors(self, targetChild):
index = getIndex(targetChild)
if index != -1 and self.mSubtrees:
return self.mSubtrees[index].retrieve(targetChild)
return self.mChildren
def getIndex(self, child):
"""
Returns the index of the node that the object belongs to. Returns -1 if the object does not exist in the tree.
"""
index = -1
childPosition = child.getPosition()
#check if it fits in the top or bottom
isInTopQuadrant = childPosition[1] > self.mMidY and childPositoin[1] < self.mMaxY
#check if it fits left
if childPosition[0] < self.mMidX and childPosition[0] > self.mMinX:
if isInTopQuadrant:
index = 1
else:
index = 2
#check if it fits right
if childPosition[0] > self.mMidX and childPosition[0] < self.mMidX:
if isInTopQuadrant:
index = 0
else:
index = 3
return index
def split(self):
"""
Split the trees into four subtrees.
"""
#top right
self.mSubtrees.append(Quadtree(depth + 1, self.mMidX, self.mMidY, self.mMaxX, self.mMaxY))
#top left
self.mSubtrees.append(Quadtree(depth + 1, self.mMinX, self.mMidY, self.mMidX, self.mMaxY))
#bottom left
self.mSubtrees.append(Quadtree(depth + 1, self.mMinX, self.mMinY, self.mMidX, self.mMidY))
#bottom right
self.mSubtrees.append(Quadtree(depth + 1, self.mMidX, self.mMinY, self.mMaxX, self.mMidY))
def clear(self):
"""
Clears the quadtree of children, and all subtrees of children.
"""
self.mChildren[:] = []
self.mHasChildren = False
for tree in range(0,4):
if self.mSubtrees[tree].mHasChildren:
self.mSubtrees[tree].clear()
到目前为止,我发现的最好方法是修改
_get_index()
来检查粒子的整个大小如果它不完全适合子树,那么它将成为父节点的子节点:然后
retrieve_neighbors()
可以遍历树并添加它经过的每个节点的子节点,一直向下到叶节点。在相关问题 更多 >
编程相关推荐