移动对象四叉树的实现
cglacet-smartquadtree的Python项目详细描述
四叉树是一种树型数据结构,其中每个节点正好有四个 孩子们。当您 需要根据它们的x-y坐标快速找到它们。
四叉树中元素的一个常见问题是检测 比一定阈值更接近的元素。
提出的实现有效地解决了这个问题。
fromsmartquadtreeimportQuadtree
创建和插入元素
在实例化四叉树时,必须指定 空间然后是高度和宽度。
q=Quadtree(0,0,10,10)
控制台上四叉树的输出非常明确。(你可以 有关“无掩码集”的含义,请参阅下一节。
q
<smartquadtree.Quadtree at 0x7fc28b93d300> Total number of elements: 0 No mask set
您可以很容易地插入元素,从中可以自然推断x-y 坐标(例如元组或列表)
q.insert((1,2))q.insert((-3,4))q
<smartquadtree.Quadtree at 0x7fc28b93d300> Total number of elements: 2 No mask set First elements: (1, 2), (-3, 4),
如果试图插入的元素在外部,则不会引发错误 四叉树的范围。但无论如何都不会被储存!
q.insert((-20,0))q
<smartquadtree.Quadtree at 0x7fc28b93d300> Total number of elements: 2 No mask set First elements: (1, 2), (-3, 4),
如果要插入其他python对象,请确保提供 get_x()和get_y()方法到您的类!
classPoint(object):def__init__(self,x,y,color):self.x=xself.y=yself.color=colordef__repr__(self):return"(%.2f, %.2f) %s"%(self.x,self.y,self.color)defget_x(self):returnself.xdefget_y(self):returnself.y
不能插入与第一个元素不同类型的元素 插入。
q.insert(Point(2,-7,"red"))
但您可以随意创建一个新的并使用它:
point_quadtree=Quadtree(5,5,5,5)point_quadtree.insert(Point(2,7,"red"))point_quadtree
<smartquadtree.Quadtree at 0x7fc289797a00> Total number of elements: 1 No mask set First elements: (2.00, 7.00) red,
简单迭代
fromrandomimportrandomq=Quadtree(0,0,10,10,16)forainrange(50):q.insert([random()*20-10,random()*20-10])
print函数不显示所有元素并使用 __repr__()每个元素的方法。
print(q)
<smartquadtree.Quadtree at 0x7fc28b94c0b0> Total number of elements: 50 No mask set First elements: [5.576253335483335, 2.9926458306078647], [2.956289387002718, 3.792134207741281], [3.9903269308895766, 5.492168007874362], ...
我们可以编写自己的迭代器并打印遇到的每个元素 我们喜欢的方式。
from__future__importprint_functionforpinq.elements():print("[%.2f, %.2f]"%(p[0],p[1]),end=" ")
[5.58, 2.99] [2.96, 3.79] [3.99, 5.49] [3.43, 1.10] [7.73, 4.09] [9.67, 6.81] [2.95, 4.12] [0.14, 5.80] [2.77, 7.87] [0.05, 1.61] [-8.74, 7.64] [-1.22, 1.90] [-0.95, 3.91] [-3.17, 1.09] [-7.41, 4.26] [-8.25, 6.47] [-6.91, 3.80] [-3.73, 3.10] [-5.74, 8.80] [8.50, -9.31] [2.49, -9.10] [6.64, -8.61] [0.40, -2.93] [7.99, -4.08] [4.71, -6.75] [0.12, -1.84] [0.72, -2.94] [9.62, -9.90] [0.15, -9.75] [8.67, -7.19] [2.44, -3.60] [5.08, -8.63] [8.86, -1.87] [1.07, -9.43] [-7.96, -5.53] [-2.53, -5.75] [-1.31, -5.81] [-7.24, -3.55] [-8.76, -9.37] [-8.48, -1.33] [-1.28, -0.69] [-6.60, -4.65] [-4.28, -0.89] [-7.56, -7.31] [-4.72, -7.02] [-1.98, -2.33] [-3.43, -5.74] [-3.71, -1.13] [-1.01, -7.29] [-2.04, -5.90]
很容易过滤迭代过程并仅应用函数 在给定多边形内的元素上。使用set_mask()方法和 传递一个x-y坐标列表。多边形将自动 关闭。
q.set_mask([(-3,-7),(-3,7),(3,7),(3,-7)])print(q)
<smartquadtree.Quadtree at 0x7fc28b94c0b0> Total number of elements: 50 Total number of elements inside mask: 15 First elements inside the mask: [2.956289387002718, 3.792134207741281], [2.945472950394006, 4.1166899654293765], [0.14379102547949074, 5.797490949080599], ...
同样的方法可以用来计算 四叉树。
print(sum(1forxinq.elements()))print(sum(1forxinq.elements(ignore_mask=True)))
15 50
由于在四叉树上设置了一个掩码,我们只计算了其中的元素 面具。可以使用size()方法计算元素并忽略 默认情况下是遮罩。使用set_mask(None)禁用掩码也是 一种可能性。
print("%d elements (size method)"%q.size())print("%d elements (don't ignore the mask)"%q.size(False))q.set_mask(None)print("%d elements (disable the mask)"%q.size())
50 elements (size method) 15 elements (don't ignore the mask) 50 elements (disable the mask)
播放绘图
%matplotlibinlinefrommatplotlibimportpyplotaspltq=Quadtree(5,5,5,5,10)forainrange(200):q.insert([random()*10,random()*10])fig=plt.figure()plt.axis([0,10,0,10])q.set_mask(None)forpinq.elements():plt.plot([p[0]],[p[1]],'o',color='lightgrey')q.set_mask([(3,3),(3,7),(7,7),(7,3)])forpinq.elements():plt.plot([p[0]],[p[1]],'ro')_=plt.plot([3,3,7,7,3],[3,7,7,3,3],'r')
相邻元素对上的迭代
可以通过 neighbour_elements()函数。它像发电机一样工作并产生 一对元素,第一个元素在掩码内(如果指定), 第二个在同一个牢房或任何相邻的牢房 戴着面具。
注意,如果(a, b)由neighbour_elements()产生, (b, a)将从未来收益中忽略。
q=Quadtree(5,5,5,5,10)q.set_limitation(2)# do not create a new subdivision if one side of the cell is below 2forainrange(200):q.insert([random()*10,random()*10])fig=plt.figure()plt.axis([0,10,0,10])forpinq.elements():plt.plot([p[0]],[p[1]],'o',color='lightgrey')q.set_mask([(1,1),(4,1),(5,4),(2,5),(1,1)])forpinq.elements():plt.plot([p[0]],[p[1]],'o',color='green')forp1,p2inq.neighbour_elements():if((p1[0]-p2[0])**2+(p1[1]-p2[1])**2<1):plt.plot([p1[0]],[p1[1]],'o',color='red')plt.plot([p2[0]],[p2[1]],'o',color='red')plt.plot([p1[0],p2[0]],[p1[1],p2[1]],'red')_=plt.plot([1,4,5,2,1],[1,1,4,5,1],'r')