1
$\begingroup$

I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2:

Both are quite high level in their description and in particular, the first one seems to be making the assumption that your input constrained edges are going to be closed curves.

Assume you have implemented a half edge data structure and all helper functions needed to get the main algorithm. I am looking for detailed pseudo code of the main subroutine.

I have the following (which is broken):

Input:
A list of points, 

A list of ordered integer pairs defining the constraint segments

The angle constraint

Algorithm:
 * compute a delaunay triangulation of the points, store it in a half edge M
 * List item

Define C a set of edges.
Define S a set of edges.
Define T a set of triangles.

For each constrained edge, add it to S
For each boundary edge, add it to S
Copy S into C

For each triangle with an angle smaller than the constraint, add it to T

while T is not empty and S is not empty:
    if S is not empty:
         pop s from S
         split s into two new segments s1 and s2

         if s1 is encroached by some triangle add s1 to S
         if s2 is encroached by some triangle add s2 to S
         
         remove s from C and add s1 and s2 to C
     else:
         pop t from T
         compute its circumcircle c
         if c encroaches a segment in C
             add c to S
         else:
             split t and set the new point to be c
         

This, as mentioned is broken, but it is as close as i have gotten to the wikipedia pseudocode while making it make sense (for example wikipedia just says to add points to the triangulation, but those points need to have some connectivity to the existing points and the wiki says nothing about how to generate that).

Something I think is likely wrong is, this is not restoring the delaunay criterion after inserting new vertices, but the wiki does not really make any mention of it. The other resource does, but that one has a different algorithmic structure, and in particular doesn't seem to deal with constraint edges which do not form closed polygons.

I am hoping someone can lend me a hand.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.