我找不到一种方法来连接网格的所有点以形成三角形，没有任何交叉

Question

为了解决这个问题，我尝试了很多方法，但都以失败告终，因为我想不出不使用过去的点或不交叉线的方法...所以我没有从使用的点列表中显示应用程序的代码。

points = [
    (5, 6, 'A'),
    (5, -8, 'B'),
    (-2, 2, 'C'),
    (-10, 4, 'D'),
    (8, 1, 'E'),
    (-8, 8, 'F'),
    (2, 7, 'G')
]

我想要一个包含所有可能三角形的点的列表，如下所示：

triangles = [[A, B, C], [B, C, D], ...]

我只想就如何实现这一点提出建议我希望这足够清楚，以便了解我想要实现的目标...

Answer 1

最简单的方法是使用 scipy.spatial.Delaunay。以下示例计算四个点的 Delaunay 三角剖分（直接取自链接页面）：

points = np.array([[0, 0], [0, 1.1], [1, 0], [1, 1]])
from scipy.spatial import Delaunay
tri = Delaunay(points)

import matplotlib.pyplot as plt
plt.triplot(points[:,0], points[:,1], tri.simplices)
plt.plot(points[:,0], points[:,1], 'o')
plt.show()

我不会假装明白到底发生了什么，但如果你对 np/scipy 了解得更多，你应该能够得到一些有用的东西。

我找不到一种方法来连接网格的所有点以形成三角形，没有任何交叉

I cannot find a way to connect all points of a grid to form triangles, without any crossing

python

geometry