从顶点坐标创建三角网格

Question

给定一组带有坐标 x 和 y 的 2D 数据点（左图），是否有一种简单的方法在其上构建三角形网格（右图）? 即返回一个元组列表，指示哪些顶点相连。解决方案不唯一，但任何合理的网格都可以。

- Amir

Answer 1

你可以使用scipy.spatial.Delaunay。以下是来自文档的示例：

scipy.spatial.Delaunay

import numpy as np
points = np.array([[-1,1],[-1.3, .6],[0,0],[.2,.8],[1,.85],[-.1,-.4],[.4,-.15],[.6,-.6],[.9,-.2]])
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()

这是类似于您输入的结果:

三角形存储在Delaunay对象的simplices属性中，该属性引用了points属性中存储的坐标:

>>> tri.points
array([[-1.  ,  1.  ],
       [-1.3 ,  0.6 ],
       [ 0.  ,  0.  ],
       [ 0.2 ,  0.8 ],
       [ 1.  ,  0.85],
       [-0.1 , -0.4 ],
       [ 0.4 , -0.15],
       [ 0.6 , -0.6 ],
       [ 0.9 , -0.2 ]])
>>> tri.simplices
array([[5, 2, 1],
       [0, 3, 4],
       [2, 0, 1],
       [3, 0, 2],
       [8, 6, 7],
       [6, 5, 7],
       [5, 6, 2],
       [6, 3, 2],
       [3, 6, 4],
       [6, 8, 4]], dtype=int32)

如果您想知道哪些顶点是连接的，那么还有一个包含该信息的属性：

>>> tri.vertex_neighbor_vertices
(array([ 0,  4,  7, 12, 16, 20, 24, 30, 33, 36], dtype=int32), array([3, 4, 2, 1, 5, 2, 0, 5, 1, 0, 3, 6, 0, 4, 2, 6, 0, 3, 6, 8, 2, 1,
       6, 7, 8, 7, 5, 2, 3, 4, 8, 6, 5, 6, 7, 4], dtype=int32))

- Alex

Answer 2

您可以尝试使用scipy.spatial.Delaunay。请参考该链接：

points = np.array([[0, 0], [0, 1.1], [1, 0], [1, 1]])

from scipy.spatial import Delaunay

tri = Delaunay(points)

plt.triplot(points[:,0], points[:,1], tri.simplices)

plt.plot(points[:,0], points[:,1], 'o')

plt.show()

输出:

- Quang Hoang

Answer 3

我认为 Delanuay 更接近于凸包。在 OP 的图片中，A 不与 C 相连，而是与 B 相连，B 又与 C 相连，这会得到不同的形状。

一个解决方法可能是先运行 Delaunay，然后移除角度超过某个度数（例如 90 或 100）的三角形。初步代码可能如下：

from scipy.spatial import Delaunay
points = [[101, 357], [198, 327], [316, 334], [ 58, 299], [162, 258], [217, 240], [310, 236], [153, 207], [257, 163]]
points = np.array(points)

tri = Delaunay(points,furthest_site=False)
newsimp = []
for t in tri.simplices:
  A,B,C = points[t[0]],points[t[1]],points[t[2]]
  e1 = B-A; e2 = C-A
  num = np.dot(e1, e2)
  denom = np.linalg.norm(e1) * np.linalg.norm(e2)
  d1 = np.rad2deg(np.arccos(num/denom))
  e1 = C-B; e2 = A-B
  num = np.dot(e1, e2)
  denom = np.linalg.norm(e1) * np.linalg.norm(e2)
  d2 = np.rad2deg(np.arccos(num/denom))
  d3 = 180-d1-d2
  degs = np.array([d1,d2,d3])
  if np.any(degs > 110): continue
  newsimp.append(t)

plt.triplot(points[:,0], points[:,1], newsimp)

这将产生上面看到的形状。对于更复杂的形状，可能还需要删除大的边缘。

for t in tri.simplices:
  ...
  n1 = np.linalg.norm(e1); n2 = np.linalg.norm(e2)
  ...
  res.append([n1,n2,d1,d2,d3])

res = np.array(res)
m = res[:,[0,1]].mean()*res[:,[0,1]].std()

mask = np.any(res[:,[2,3,4]] > 110) & (res[:,0] < m) & (res[:,1] < m )

plt.triplot(points[:,0], points[:,1], tri.simplices[mask])

- BBSysDyn

---

通常情况下，Delaunay会产生一个凸边形（凸包）。在Stackoverflow上有时会讨论关于Delaunay的"alpha shapes"的问题。Alpha shape允许存在凹面部分。你可以尝试搜索"delaunay alpha"，看看你是否能找到与你的问题相关的内容。 - Gary Lucas

那个alpha shapes方法并不总是有效。我认为最好使用三角剖分网格生成方法，这可以帮助你在计算机科学代码方面更进一步。这是一个研究活跃的领域，例如如何使Delanuay在有限元素法中更加有效。 - BBSysDyn