289

10-14：使用四叉树的碰撞检测
10.7.1 输入 / 输出

P

，这样可以在目标矩形完全覆盖子

10.7.2 决方案

10-4

Python

smaller2k
larger2k

2

Region

10-4
：四叉树的

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
def __init__(self, region, pt = None, data = None):
"""

，它和原有的给定区域有着相同的中心。
"""
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 = []
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

False

4

5

4

10-5
：四叉树

"""
(pt, data)

"""
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
#

if node.children[q] is None:

291

#

node.subdivide()
node = node.children[q]
return False
def add (self, pt, data = None):
if self.root is None:?
return True

10-6

range

Python

yield

10-6
：四叉树范围查询实现
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
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.