Split a triangle into smaller triangles

Question

I have a triangulated mesh. I want to limit the maximum edge length. Therefore I take the all triangles with long edges (longer than the limit), and split them into smaller triangles.

My idea is the following: I split the longest edge in half and get two triangles. If these are also too large I do it recursively. This works nice, because I also split the correspondent adjacent triangle and the vertexes collapse again.

The problem: When there is a acute-angled triangles. The result look a bit weird. Small angles get even smaller, ...

Is there a better way of splitting such triangles. Another idea is, to split a edge into k equidistant edges, (with k the smallest value, such that edgelength/k < limit). I can do this on all 3 edges of the triangle. But how should I connect these vertexes?

Answer 1

As you are bothered with small angles and small triangles, I would advise you to use Delaunay triangulation, because one of its properties is that it maximizes the minimal angle and it avoids small triangles.

Delaunay triangulation requires the points as input. Since you don't have this, you could perform the algorithm recursively, splitting lines when they are too long.

The following Python code does exactly what you would like to achieve. It uses the Delaunay class included in scipy.

    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)

Let's try it out.

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

It outputs

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

Let's see the results now in a figure, created via the matplotlib library from python.

    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)

This is the result: