空间树结构
289
空间树结构
10-14:使用四叉树的碰撞检测
10.7.1 输入 / 输出
输入是一棵四叉树,它由平面上的一个二维点集
P
构建而成。
为了获得最佳性能,范围查询会返回四叉树中的
结点
,这样可以在目标矩形完全覆盖子
树中点时直接返回。碰撞检测的结果是目标点与已有点的交集。
10.7.2 决方案
在例
10-4
中,
QuadTree
QuadNode
结构
展示了基本的四叉树
Python
实现
smaller2k
larger2k
辅助方法确保初始区域的边长为
2
的幂次
Region
类表示一块矩形区域。
10-4
:四叉树的
QuadNode
实现
class Region:
def __init__(self, xmin,ymin, xmax,ymax):
"""
从两点
(xmin, ymin)
(xmax, ymax)
出发创建区域。
如果这两个点不是区域的左下角和右上角坐标,相应地进行调整。
"""
self.x_min = xmin if xmin < xmax else xmax
self.y_min = ymin if ymin < ymax else ymax
self.x_max = xmax if xmax > xmin else xmin
self.y_max = ymax if ymax > ymin else ymin
class QuadNode:
def __init__(self, region, pt = None, data = None):
"""
创建空结点
QuadNode
,它和原有的给定区域有着相同的中心。
"""
self.region = region
self.origin = (region.x_min + (region.x_max - region.x_min)//2,
region.y_min + (region.y_max - region.y_min)//2)
self.children = [None] * 4
290
10
if pt:
self.points = [pt]
self.data = [data]
else:
self.points = []
self.data = []
class QuadTree:
def __init__(self, region):
"""
在正方形区域上构建四叉树,正方形的边长为
2
的幂次。
"""
self.root = None
self.region = region.copy()
xmin2k = smaller2k(self.region.x_min)
ymin2k = smaller2k(self.region.y_min)
xmax2k = larger2k(self.region.x_max)
ymax2k = larger2k(self.region.y_max)
self.region.x_min = self.region.y_min = min(xmin2k, ymin2k)
self.region.x_max = self.region.y_max = max(xmax2k, ymax2k)
如例
10-5
所示,我们使用了
add
方法将点加入四叉树中。如果点已经在四叉树中,
add
方法会返回
False
因此四叉树加了数学集合语义。如果点位于结点的矩形区域内,
最多可以向该结点添加
4
个这样的点。当添加第
5
个点时,结点区域会被进一步切分成
象限,而点会被分配到结点区域的单个象限中。这个过程会不断持续,直到所有点都被
分配到象限中,并且叶结点象限拥有
4
个或者更少的点。
10-5
:四叉树
add
方法的实现
class QuadNode:
def add (self, pt, data):
"""
(pt, data)
加入
QuadNode
中。
"""
node = self
while node:
#
点不在区域之内。
if not containsPoint (node.region, pt):
return False
#
如果区域存在点,那么就意味着它是叶子结点,然后在此处进行检查。
if node.points != None:
if pt in node.points:
return False
#
如果还有空间,向该
结点中添加点。
if len(node.points) < 4:
node.points.append (pt)
node.data.append (data)
return True
#
找到要加入的象限。
q = node.quadrant (pt)
if node.children[q] is None:
空间树结构
291
空间树结构
#
细分结点,将点重新分配给每个象限,然后添加点。
node.subdivide()
node = node.children[q]
return False
class QuadTree:
def add (self, pt, data = None):
if self.root is None:?
self.root = QuadNode(self.region, pt, data)
return True
return self.root.add (pt, data)
借助这个结构,例
10-6
中的
range
方法可以高效地在四叉树中找到所有被目标区域包含
的点。这一
Python
实现使用了
yield
操作符为结果提供迭代器接口。迭代器包含一个元组,
它可能是单个点也有可能是整个结点。当四叉树结点被目标区域完全包含时,该方法会
返回整个结点作为结果的一部分。调用方可以对结点使用先序遍历来找到所有的子孙值,
QuadNode
的实现。
10-6
:四叉树范围查询实现
class QuadNode:
def range(self, region):
"""
如果结点包含在目标区域内,返回
(node, True)
作为迭代器的生成结果,
否则对于单个点返回
(region, False)
"""
if region.containsRegion (self.region):
yield (self, True)
else:
#
如果区域存在点,那么就意味着它是叶子结点,然后在此处进行检查。
if self.points != None:
for i in range(len(self.points)):
if containsPoint (region, self.points[i]):
yield ((self.points[i], self.data[i]), False)
else:
for child in self.children:
if child.region.overlap (region):
for pair in child.range (region):
yield pair
class QuadTree:
def range(self, region):
"""
如果包含在目标区域内,返回四叉树中的
(node,status)
作为迭代器的生成结果。
"""
if self.root is None:
return None
return self.root.range(region)
为了支持碰撞检测,我们使用
collide
方法(例
10-7
在四叉树中搜索与正方形相交的点,
其中正方形的边长为
r
,中心为给定的点
pt

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.