python - scipy.spatial.Delaunay 很难找到给定点的所有邻居

Question

这里有一个关于使用 scipy.spatial.Delaunay 查找点中点的最近邻的非常好的讨论: How to find all neighbors of a given point in a delaunay triangulation using scipy.spatial.Delaunay?

我遵循了答案，但是当配置的对称性很高时我遇到了困难。这是我的代码:

import numpy as np
from matplotlib import pyplot as plt
from scipy.spatial import Delaunay

##########################################################

# Gets a Delaunay triangulations and returns the 
# nearest neighbor points for each point

def find_neighbors(tri):    
    l = tri.vertex_neighbor_vertices
    neib = []
    for i in range(len(l[0])-1):
        neib.append(list(l[1][l[0][i]:l[0][i+1]]))
    return neib

# Create a square lattice
t1 = np.array([1,0])
t2 = np.array([0,1])
n = 6
lattice = np.zeros((n**2,2))
for i in range(n):
    for j in range(n):
        lattice[i*n + j] = i* t1 + j * t2


tri = Delaunay(lattice)
Neib = find_neighbors (tri)

pindex = 20
plt.title("particle index: 20")
plt.triplot(lattice[:,0], lattice[:,1], tri.simplices.copy(),"c--")
plt.plot(lattice[:,0], lattice[:,1], 'go')
plt.plot(lattice[pindex,0], lattice[pindex,1], 'bo')
plt.plot([lattice[i,0] for i in Neib[pindex]],[lattice[i,1] for i in Neib[pindex]], 'ro')
plt.show()

pindex = 21
plt.title("particle index: 21")
plt.triplot(lattice[:,0], lattice[:,1], tri.simplices.copy(),"c--")
plt.plot(lattice[:,0], lattice[:,1], 'go')
plt.plot(lattice[pindex,0], lattice[pindex,1], 'bo')
plt.plot([lattice[i,0] for i in Neib[pindex]], [lattice[i,1] for i in Neib[pindex]], 'ro')
plt.show()

from scipy.spatial import Voronoi, voronoi_plot_2d

vor = Voronoi(lattice)
fig = voronoi_plot_2d(vor)
plt.show()

结果如下。正如您所看到的，对于具有相同对称性的两个点，由于 scipy 进行 Delaunay 三角剖分的方式，我得到了不同数量的邻居。 python 中是否有任何代码可以通过 scipy.spatial.Voronoi 获取邻居？感谢您的帮助。

这是图像的链接。我的声誉低于 10，现在无法发布图片。 (或者，您可以运行代码以获得相同的结果)

索引 20

https://i.ibb.co/9bQQqmT/download.png

索引 21

https://i.ibb.co/pfw5hsG/download-1.png

Voronoi 图

https://i.ibb.co/g3NpjVL/download-2.png

Answer 1

这些对称配置的问题在于 Delaunay 三角剖分不是唯一定义的:只要公共(public)圆上有四个顶点，Voronoi 图就不会指定如何对其进行三角剖分。因此，相反的点在三角剖分中可能相连，也可能不相连。

这是一张夸张的 Voronoi 图，其中 Voronoi 图中的零长度边被夸大了。

Voronoi 图中的红色圆圈边实际上是零长度，可能会也可能不会实际出现并对应于 Delaunay 三角剖分中的一条边。

您可能只想忽略与这些退化 Voronoi 边关联的邻居(以便所有顶点的邻居都是 your image here 中的邻居)。然而，scipy .spatial.Voronoi 并没有让这变得非常容易:您可以找到短的 Voronoi 边，但找不到相应的相邻 Voronoi 站点。在 Delaunay 三角剖分中，您可以查看连接到一条边的两个三角形:在这两个三角形之间有四个顶点。如果所有四个顶点都是共圆的(或非常接近共圆的)，则关联的 Voronoi 边是退化的，并且可以忽略该邻居。