Python Scipy Delaunay 2D 无法连接某些点

Question

我生成了 20 个随机点并应用 Delaunay 三角测量并创建了可视化。我不明白为什么外面总是有一些点不相连。我查看了 qhull 文档，但找不到可以解决我的问题的设置。我也尝试过更改种子，但即使使用不同的数字，问题仍然存在。 我尝试了 scipy.spatial.Delaunay 中的选项，例如 farthest_site、incremental 和 qhull_options="QJ"，但它们没有解决问题。

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

#The points that I used

np.random.seed(10)  
points = 10 * np.random.rand(20, 2)


#qhull_options = "QJ"

tri = Delaunay(points)



plt.plot(points[:, 0], points[:, 1], 'o', markersize=8, label='Points')

for simplex in tri.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
    #point1 = points[simplex, 0]
    #point2 = points[simplex, 1]
    #distance = np.linalg.norm(point1 - point2)
    #point_pairs.append((point1, point2))
    #distances.append(distance)
    

plt.xlabel('X')
plt.ylabel('Y')
plt.title('Delaunay Triangulation ')
plt.legend()
plt.axis('equal')  

plt.show()


"""
[[7.71320643 0.20751949]
 [6.33648235 7.48803883]
 [4.98507012 2.24796646]
 [1.98062865 7.60530712]
 [1.69110837 0.88339814]
 [6.85359818 9.53393346]
 [0.03948266 5.12192263]
 [8.12620962 6.12526067]
 [7.21755317 2.91876068]
 [9.17774123 7.14575783]
 [5.42544368 1.42170048]
 [3.7334076  6.74133615]
 [4.41833174 4.34013993]
 [6.17766978 5.13138243]
 [6.50397182 6.01038953]
 [8.05223197 5.21647152]
 [9.08648881 3.19236089]
 [0.90459349 3.00700057]
 [1.13984362 8.28681326]
 [0.46896319 6.26287148]]
"""

'''

Answer 1

一个最小的例子

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

np.random.seed(1234)
points=np.random.rand(10,2)

tri=Delaunay(points)

plt.scatter(points[:,0], points[:,1])
for s in tri.simplices:
    plt.plot(points[s,0], points[s,1], 'k-')

plt.show()

其显示：

我对我的种子很幸运，因为（与你的种子不同——尽管如此，不用吹牛，我也知道你的问题是什么）它清楚地表明了问题是什么：底部的单行不能是三角形（在你的例子中，你似乎只有闭合三角形

仅绘制一个三角形

为什么，你的绘制三角形的方法非常聪明，只需在每个三角形上画两条线。每个

simplex

都是索引的三元组。您可以使用奇特的索引将它们转换为

x

的三元组和

y

的三元组。并绘制这些。但在 matplotlib 中，当您绘制 3 x 和 3 y 时，您会得到 2 条线，而不是 3 条。

只需绘制第一个三角形即可确定（我们又很幸运，第一个三角形恰好是我们已经注意到的三角形）

plt.scatter(points[:,0], points[:,1])
for s in tri.simplices:
    plt.plot(points[s,0], points[s,1], 'k-')
    break

所以，你看，有 2 行（不过我确信此时你并不需要真正令人信服。这种错误有时很难找到，但一旦看到就很明显）。

关闭循环

因此，解决方案之一可以是使用

plt.fill

代替（使用选项

fill=False

，这可能看起来很矛盾，因为这意味着填充，但不填充。但是

fill

的作用是在绘制时关闭循环，并填充内部，除非要求不要）

plt.scatter(points[:,0], points[:,1])
for s in tri.simplices:
    plt.fill(points[s,0], points[s,1], fill=False)

另一种选择可能是更改所有

s

以在末尾添加第一个点

plt.scatter(points[:,0], points[:,1])
for s in tri.simplices:
    tri=s.tolist()+[s[0]]
    plt.plot(points[tri,0], points[tri,1], 'k-')

显示完全相同的结果。