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

Question

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

所以我有以下代码（based on the example) in order to first get the circles and then triangulate them with the triangle project

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()

现在这会导致外圈和内圈都像这里显示的那样被三角化 , clearly ignoring the hole. However by setting the 'qpa0.05' flag we can cause the circle to use the hole as seen here 。然而这样做会导致三角形分裂，添加许多不同的三角形，将 qpa 增加到更高的值确实会导致三角形的数量有所减少，但它们仍然存在。

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

有人知道如何在不添加额外三角形的情况下使用孔进行三角测量吗？

Answer 1

您可以将一个（或多个）孔连接到外周，这样您就可以得到一个单一的“退化多边形”，该多边形由连接所有点而没有自相交的单个点序列定义。

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

Answer 2

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

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

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

How do I triangulate a polygon with holes without extra points

python

geometry

opencv

triangulation