scipy - 如何获得 Delaunay 三角剖分的“边界”？

Question

在视觉上，我很清楚，给定 Delaunay 三角剖分，有一些点构成了它的“边界”。这个边界与凸包不同，因为它的点数不是最少的，也不一定是凸的。

这叫什么？有没有办法从scipy Delaunay 三角测量中得到它？

（注意：我不是在寻找关于如何确定此边界的算法，而是在寻找预先烘焙的 scipy 函数。我已经知道如何获得Delaunay 三角剖分的边界，但不想重新发明轮。）

标签： scipy

Answer 1

这实际上很简单，不需要凸/凹壳。

假设您已经对封闭曲面进行了三角剖分，关键的观察是要注意，如果三角剖分的边不被两个不同的三角形共享，则它属于边界。

从scipy.spatial.Delaunay 文档中，如果 P 是一组点并且您已经计算了 T = Delaunay(P)，那么如果与第 k 个顶点相对的边属于边界，则 T.neighbors 在其第 k 个坐标中等于 -1 .

示例代码：

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

# Create triangulation of a rectangle
x = np.linspace(0,1,9)
y = np.linspace(0,1,9)
X,Y = np.meshgrid(x,y)
P = np.array([X.flatten(),Y.flatten()]).T
T = Delaunay(P)

# Find edges at the boundary
boundary = set()
for i in range(len(T.neighbors)):
    for k in range(3):
        if (T.neighbors[i][k] == -1):
            nk1,nk2 = (k+1)%3, (k+2)%3 
            boundary.add(T.simplices[i][nk1])
            boundary.add(T.simplices[i][nk2])

# Plot result
plt.triplot(P[:,0], P[:,1], T.simplices)
plt.plot(P[:,0], P[:,1], 'o')
plt.plot(P[list(boundary),0], P[list(boundary),1], 'or')
plt.show()