Error in Delone condition test formula

Introduction

On an early Sunday morning, I was already at my third day debugging a program to triangulate the result of a laser scan. A laser scan is a collection of three-dimensional points. As a result of the program, you need to merge points into disjoint polygons, thus creating a surface model. I recounted the function after function on a piece of paper and finally reached the function of checking the fulfillment of the Delaunay condition . Apparently, the error lurked somewhere in it. A detailed analysis turned out that the formula, indicated in a huge number of books about Delone's triangulation, does not always give the correct result. Details under the cut.

Delone condition

I'll tell you briefly about the Delone condition itself. By the way, I drew all the information from the wonderful book AV Skvortsova "Delone Triangulation and its application . " It is said that triangulation satisfies the Delone condition if not one of the given triangulation points falls inside the circle described around any triangle constructed. The fulfillment of this condition is necessary in order to maximize the sum of the minimum angles of all triangles of the triangulation. Simply put, the triangles are not oblate.

The author offers 2 ways to check the condition of Delone with the possibility of optimization for each of them.
')
The first method is the most obvious. He proposes to calculate the center and radius of the circumscribed circle and directly check the belonging of the vertices of the neighboring triangles. As an optimization, it is proposed to store the calculated circumscribed circles in the class of a triangle. Non-optimized verification requires 29 multiplication and division operations and 24 addition and subtraction operations. The complexity of the optimized verification depends on the triangulation algorithm.

The second way is more interesting. He argues that to test the condition, it is enough that for any neighboring triangle, the sum of the opposite angles does not exceed PI ( ), which is equivalent to the condition: .

Further, after coercions and transformations, a rather scary formula is obtained:
The formula corresponds to the sine of the sum: where cosines and sines are expressed in terms of scalar and pseudoscalar products, respectively. In the formulas, the product of vector lengths is omitted (apparently because it does not affect the sign of the expression).

As an optimization, it is proposed to first calculate the cosine signs. If a and means and those. Delone condition is satisfied. If a and means and condition is not satisfied. Otherwise, you should perform a check on the full formula.

Checks on the full condition requires 10 multiplication / division operations and 13 addition / subtraction operations. The optimized check, according to the author of the book, requires approximately 7 multiplication / division operations and 9 addition / subtraction operations.

After reading this information, I made a logical conclusion that the latter method is more optimal than the others and began to use it. As they say, nothing foreshadowed trouble.

Underwater rocks

During debugging, I began to notice the inadequate behavior of the function checking condition Delaunay. The problem turned out to be that the sine sign depends on the order of enumeration of the vertices. Thus, due to the sine sign, the sign of the whole expression changes. Maybe I do not understand something, I will be glad if someone corrects me.

The first and only way to correct the situation that occurred to me is to take the expression of a sine modulo. Thus, the sine shows only the magnitude of the angle, and not the direction of the sweep, which is our advantage.

Conclusion

It is very surprising for me that this formula is indicated in a huge number of books. What does this mean not only Russian-language literature, but here is a publication in which the same information is indicated.

I am not a great expert in mathematics, so I expect from the community adequate criticism and suggestions. Ready for discussion.

Thanks for attention.