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, ...

enter image description here

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?

Just to clarify, you're taking a long edge, finding the center point on that edge and (this is the part I'm not quite clear on) connecting that center point to the opposite vertex of one of the triangles connected to that edge. Is this correct? — beaker
It looks like you can't make all sub-triangles reasonably good here - but you can cut the ill-formed triangle off and triangulate the remaining trapezoid. I'd say: without internal vertices - why do you need them? — HEKTO
In your second approach where you mark the possible points to split first. How about prioritizing it so you draw the edge that is shortest among all the edges that could be draw between those points first? Then split the new edge if needed, and add to the pool of potential edge. Repeat the process. (Not sure how to implement efficiently though) — Apiwat Chantawibul

IPV3001 IPV3001 · Accepted Answer · 2014-07-25T09:46:27

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:

Output of Delaunay triangulation

Split a triangle into smaller triangles

1 Answers