将一个三角形分割成更小的三角形

Question

我有一个三角网格。我想限制最大边长。因此，我选择所有具有长边（比限制更长）的三角形，并将它们分成较小的三角形。

我的想法是：我将最长的边分成两半，得到两个三角形。如果这些也太大了，我会递归地重复这个过程。这很好用，因为我也会分裂相邻的三角形和顶点再次折叠。

问题是：当有锐角三角形时，结果看起来有点奇怪。小角度变得更小，... 有没有更好的方法来分割这样的三角形？另一个想法是将一条边分成k等分边（k是最小值，使得edgelength/k < limit）。我可以在三角形的所有3条边上做到这一点。但是我应该如何连接这些顶点？

- Jakube

---

只是为了澄清，您正在取长边，找到该边上的中心点，然后（这是我不太清楚的部分）将该中心点连接到与该边相连的三角形的相对顶点。这正确吗？ - beaker

看起来您不能在这里使得所有的子三角形都合理 - 但是您可以切掉不良形状的三角形并将其余的梯形三角化。我的意见是：没有内部顶点 - 您为什么需要它们呢？ - HEKTO

在你的第二种方法中，你先标记可能拆分的点。如何优先考虑绘制在这些点之间可以绘制的所有边中最短的边呢？然后再根据需要拆分新的边，并添加到潜在边的池中。重复这个过程。（尚不确定如何高效实现） - Apiwat Chantawibul

Answer 1

由于您遇到了小角度和小三角形的问题，我建议您使用 Delaunay 三角剖分，因为它的一个特性是最大化最小角度并避免小三角形。

Delaunay 三角剖分需要点作为输入。由于您没有这些点，您可以在算法递归时分割线段当它们太长时。

以下Python代码正好实现了您想要实现的内容。 它使用了scipy中包含的Delaunay类。

    def splitViaDelaunay(points, maxLength):
        from scipy.spatial import Delaunay
        from math import sqrt, ceil
        print "Perform Delaunay triangulation with "+str(len(points))+" points" 
        tri = Delaunay(points)
        # get set of edges from the simpleces
        edges = set()
        for simplex in tri.simplices:
            # simplex is one triangle: [ 4  5 17]
            edges.add((simplex[0], simplex[1]))
            edges.add((simplex[1], simplex[2]))
            edges.add((simplex[0], simplex[2]))
        # check if all edges are small enough
        # and add new points if not
        isFinished = True
        for edge in edges:
            p1, p2 = edge
            [x1, y1] = points[p1]
            [x2, y2] = points[p2]
            length = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
            if length > maxLength:
                isFinished = False
                # split in how many pieces?
                nPieces = ceil(length/maxLength)
                for piece in range(1, int(nPieces)):
                    points.append([x1+piece/float(nPieces)*(x2-x1), y1+piece/float(nPieces)*(y2-y1)])
        if not isFinished:
            splitViaDelaunay(points, maxLength)

让我们试一试。

    points = [[0,0], [10,3], [9.5,4]]
    splitViaDelaunay(points, 0.5)

它输出

Perform Delaunay triangulation with 3 points
Perform Delaunay triangulation with 45 points
Perform Delaunay triangulation with 97 points
Perform Delaunay triangulation with 105 points

现在让我们通过Python的matplotlib库创建一个图形，查看结果。

    def plotPointsViaDelaunayTriangulation(pnts):
        from scipy.spatial import Delaunay
        import numpy as np
        points = np.array(pnts)
        tri = Delaunay(points)
        import matplotlib.pyplot as plt
        plt.triplot(points[:,0], points[:,1], tri.simplices.copy())
        plt.plot(points[:,0], points[:,1], 'o')
        plt.show()
    
    plotPointsViaDelaunayTriangulation(points)

这是结果：

- IPV3001