When should i do Edge Flip in this case ? (For Delaunay Triangulation)

Question

The problem is the following : I have to transform a triangulation $t1$ intro a triangulation $t2$ of the same set of points.

First i use the Edge Flip Algorithm to get the flips needed to transform triangulation $t1$ into the Delaunay triangulation of the set of points.

I do the same for the second one.

Now the answer would be that the correct way to transform $t1$ into $t2$ is to transform $t1$ into the Delaunay triangulation and after that apply the opposite operations of the $t2$ to Delaunay transformation.

The issue i found is the following : I have four points. Three that form a triangle(A,B,C) and one that is not contained in it (D). The problem is that there might exist cases where even the fourth point might be found in the circumscribed circle of triangle ABC.

To be more precise, the determinant of the four points is equal to 0.

How should i decide if i should make a flip ? The Flip is this case doesn't seem to do anything.

P.S. I know if A,B,C are in CCW or CW position.

Answer 1

As you said, the flip accomplishes nothing in particular. Nevertheless, you should specify an ordering such that also in such a setting the outcome of your algorithm is well defined. An example would be to use the vertex indices to apply an ordering and therefore decide if a flip is made or not.

Answer 2

The determinant being equal to zero means that the four points lie on the same circle, otherwise it should be less o greater than zero. For the Delaunay Triangulation being unique the set of points should be in general position (in this case no three collinear points, no four points on the same circle.) If the points are not in general position they are said to be degenerate. There are strategies to convert a degenerate set to general position by means of a perturbation of the points. In the case you have four points on a circle you have two choices to triangulate them, the diagonal could be between two ot the points of else between the other two points. Both configurations result in delaunay triangles, but if you are not consistent in selecting the location of the diagonal you end up with two different triangulations. Briefly, you transform your points to general position (which may be involved) or you apply a rule to break the tie in a consistent way.