如何在没有额外点的情况下对有孔的多边形进行三角剖分

Question

我正在尝试对多个多边形进行三角剖分，以使三角形不会添加额外的点。为了让问题简短，我将彼此使用 2 个圆圈，实际上这些将是 opencv 轮廓，但是两者之间的转换非常复杂，圆圈也显示了问题。

所以我有以下代码（基于示例），以便首先获取圆圈，然后使用三角形项目

对它们进行三角测量

import matplotlib.pyplot as plt
import numpy as np

import triangle as tr


def circle(N, R):
    i = np.arange(N)
    theta = i * 2 * np.pi / N
    pts = np.stack([np.cos(theta), np.sin(theta)], axis=1) * R
    seg = np.stack([i, i + 1], axis=1) % N
    return pts, seg


pts0, seg0 = circle(30, 1.4)
pts1, seg1 = circle(16, 0.6)
pts = np.vstack([pts0, pts1])
seg = np.vstack([seg0, seg1 + seg0.shape[0]])
print(pts)
print(seg)
A = dict(vertices=pts, segments=seg, holes=[[0, 0]])
print(seg)
B = tr.triangulate(A) #note that the origin uses 'qpa0.05' here
tr.compare(plt, A, B)
plt.show()

现在这会导致外圆和内圆都被三角化，如下所示：

...显然忽略了这个洞。然而，通过设置“qpa0.05”标志，我们可以使圆圈使用孔，如下所示：

然而，这样做会导致三角形被分割，添加许多不同的三角形，将 qpa 增加到更高的值确实会导致三角形的数量有所减少，但它们仍然存在。

请注意，我希望能够处理同一形状的多个孔，并且该形状最终可能会变成凹形。

有人知道如何让三角测量使用孔而不添加额外的三角形吗？

Answer 1

您可以将孔（或多个孔）连接到外周，以便获得由单点序列定义的单个“简并多边形”，该点序列连接所有点而不自相交。

您进出同一个路段。如果顺时针沿着外周长移动，则需要逆时针沿着孔周长移动，反之亦然。否则，它会自相交。

Answer 2

我明白了 “qpa0.05”应该是“p”，p 使代码因子成为孔，a 设置三角形的最大面积，这会导致添加额外的点。

B = tr.triangulate(A,'p')