smartquadtree 1.0

创建和插入元素

在实例化四叉树时，必须指定 空间然后是高度和宽度。

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)将从未来收益中忽略。

# Let's start with a new quadtree because we needq=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')