Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

Question

Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.

The algorithm specifies splitting the edges at their midpoint (except in the case of small input angles where concentric circular shells as suggested. This question is unrelated to these cases.)

In certain domains, given a segment, there are points on the segment that I would prefer to split on that are not necessarily the midpoints (unrelated to the concentric shell trick). These points are chosen based on some domain specific underlying data (considerations beyond the graph structure the algorithm is aware of).

• What are the implications of splitting on non-midpoints?
• What needs to be taken into consideration when selecting among several non-midpoint candidates?
• Does splitting on non-midpoints affect any of the convergence properties of the algorithm?

Another way to ask this is: Are there split points that are better than the a-priori selected midpoints?

Answer 1

In Rupert's refinement algorithm, if the circumcenter of a "skinny" (poor quality) triangle were inside the domain and its location is "sufficiently" far away from other points in the triangulation, the algorithm terminates. When the circumcenter is inserted, it is at least a certain distance from all other points (equal to the circumradii), so it will eventually run of space to add more points. Luckily, the ratio of the circumradii and length of the smallest side of a triangle is a function of the smallest angle in the triangle. Therefore, if a skinny triangle is defined as a triangle whose ratio is greater than 1 (corresponds to a minimum angle of 30 degrees), the algorithm is guaranteed to terminate.

But what if the circumcenter is outside the domain? That is when the midpoint on the "nearest" boundary edge is inserted. When the midpoint is inserted, it introduces two short edges whose length is equal the half the length of the original edge. In addition, all points within the diametrical circle of the original edge are deleted so that there are no "even-shorter" edges introduced. And because these two new edges may be shorter than the previous shortest edge in the mesh, during the next step, we should introduce the circumcenter only if the ratio (cumcumradii : shortest length) is greater than some quantity that is strictly greater than 1. In the pdf you shared, it is shown that the ratio should be $\sqrt2$.

If you inserted a point not on the midpoint, but somewhere else on the edge, you will create an edge shorter then half the length of the boundary edge. This edge may be much shorter than the current shortest edge in the mesh. So the ratio that guarantees termination will be greater $\sqrt2$.

To answer your specific questions: 1. Implication: weaker termination guarantee 2. The length of new edges created should be considered. If they all happen to be large, you can happily add a non-midpoint vertex into the mesh. If the boundary edge is a light year long, and other mesh edges are orders of magnitude shorter, you can split the edge almost anywhere ... almost (see below). 3. Yes, splitting on non-midpoints affects termination guarantees.

BUT .....

Alper Ungor's paper attempts to insert off-circumcenter points instead of the circumcenter.

And this paper also allows for insertion of non-midpoint vertices into the mesh. But in the limiting case, it reverts to mid point insertion.

Answer 2

The first paper I am aware of in the literature that has addresses analysis of non-midpoint splitting is:

Pav, S.E.; Walkington, N.J., Delaunay refinement by corner lopping, Proceedings of the 14th International Meshing Roundtable (2005) pdf.

The motivation of that paper was a little different: they authors were analyzing refinement of curved inputs. But the analysis applies to non-midpoint splitting of edge splitting: a split point of a curve is similar in that it is not at the center of the circle with diameter between the segment or curve's end points. The take away from the analysis is that non-midpoint split points can be used but at the expense of a reduction of the guaranteed quality that can be ensured in the algorithm output. In the paper, this is seen in the appearance of $\mu$ and $\eta$ in Corollary 3.

The paper of Foteinos, Chernikov, and Chrisochoides (here) also analyzes non-midpoint splitting although with a different dependence between the parameters: the minimum angle in the output is fixed and the algorithm reverts to midpoint splitting whenever there isn't enough space to permit a midpoint split and guarantee mesh quality.

Are there split points that are better than the a-priori selected midpoints?

There isn't any good evidence of non-midpoint splitting benefiting a particular application. For triangle circumcenters, there are two common motivations for using non-circumcenters,

1. Intentionally create triangles slightly above the quality threshold. The goal is to spread points out as much as possible without triggering further refinement allowing the algorithm to terminate with as few vertices as possible. This was the original motivation in Üngör's paper and Triangle does this.

2. Deliberately create triangles with angles hopefully well above the thresholds of guaranteed termination. Acute does this and on many cases is fortunate enough to create meshes that outperform theoretical expectations.

Figure 7 in this paper shows how the type of off-center selection can be used to manipulate the distribution of triangles created in the final algorithm. The results aren't that surprising: if you go out of your way to create a during type of triangle in the algorithm, then you create lots of that type and can see them over-represented in the distribution.

Non-midpoint edge splitting hasn't been particularly effective an addressing these needs. While circumcenter splitting is done in a way that to avoid creating subsequent poor quality triangles (when filling a empty space in the domain), the midpoint is generally the best position with the local information available. If the algorithm could look ahead 2, 3, 4, ... steps and see what subsequent refinement would be made to the split segment, maybe there could be some better prediction on how the segment should be refined. This paper suggests that if you know the local feature size (i.e., how long the segments needs to be in the final mesh) up front, then you can make better decisions on where to place split points and provide better guarantees on the final output. But for standard Delaunay refinement, no one has found information available at the time of an edge split that justifies a non-midpoint split.