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 获取邻居？感谢您的帮助。

这里是 link 图片。我的声誉不到 10，我现在无法 post 图片。（或者，您可以运行获得相同结果的代码）

索引 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 三角剖分不是唯一定义的：只要在一个公共圆上有四个顶点，Voronoi 图就不会指定应该如何三角剖分。所以相对的点在三角剖分中可能相连也可能不相连。

这里是 Voronoi 图的放大图，在 Voronoi 图中放大了零长度边。

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

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

scipy.spatial.Delaunay 难以找到给定点的所有邻居

Difficulty with scipy.spatial.Delaunay to find all neighbors of a given point

python

scipy

nearest-neighbor

voronoi