Edge flipping in Delaunay triangulation

Edge flipping is applied on internal edges (edge shared with two triangles) if they are illegal and can’t be applied on boundary edges. In triangulation (and meshing in general), all triangles (cells) should have the same notation direction (orientation) as this is useful in edge-based data structures used in rendering and simulation. The main trick in edge flipping is the notation of the new triangles. That means: if the original triangles are written in clockwise/counter clockwise orientation (order), then the new triangles should have the same orientation.

Consider that we have two adjacent triangles like the following (written in Scilab/Matlab syntax):

OldTri1=[A, C, B];     OldTri2=[D, B, C];

Where A, B, C, D are integers representing the indices of the vertices, and in our case the notation orientation is clockwise.

Steps of flipping:

§  Get the vertices of the shared edge ⟾ the shared edge is [B, C] or [C, B]

§  Get the edges of the first triangle ⟾ edges=[A, C;C, B;B, A]

§  Remove the shared edge from the edges of the first triangle ⟾ edges=[A, C;B, A]

§  We have two triangles with total of four vertices. Now, get the vertex that we can call far vertex. This vertex is simply the fourth vertex that does not belong to the first triangle, in our case the far vertex is D

§  Now, the new triangles after flipping are

NewTri1=[(the first edge/row in edges) (far vertex)]=[A, C, D];

NewTri2=[(the second edge/row in edges) (far vertex)]=[B, A, D];