Natural Neighbor Interpolator fails at borders of problematic TIN about tinfour HOT 5 CLOSED

In a related development, I noticed that the getArea() method for the SimpleTriangle class (see Triangle Collector Techniques ) was computing a small-magnitude negative area for triangle 5,8,0. This glitch violates the rule that all triangles produced by Tinfour are oriented counterclockwise and have a positive area.

This unfortunate result was due to numeric round-off issues arising from the nearly-degenerate geometry of the triangle. However, when I used the extended-precision logic from the GeometricOperations class, I confirmed that the triangle was, in fact, constructed correctly and did have a positive area.

I am looking at the best way to incorporate extended-precision logic into the SimpleTriangle class. The extended-precision logic is slower than simple floating-point operations but does produce more accurate results.

This change will be integrated into the upcoming 2.1.5 release of Tinfour. Once it is addressed, I will be closing this issue.

from tinfour.

A code change for the Natural Neighbor Interpolator class has been posted to the Tinfour code base. This change corrects the behavior of the interpolator. This issue may now be closed.

from tinfour.

I have updated the area calculation for the SimpleTriangle class (now not quite so simple as it was).

Previously, triangle 5,8,0 was computed to have an area of -1.818989e-12. While the formula in the code was correct, numerical issues resulted in the incorrect value. The current version uses extended-precision arithmetic to find an area of 1.752672e-13

As you can see, the new computation produces a more reasonable value and confirms that the triangle has a positive area. Of course, it is possible that if vertex 5 were moved arbitrarily close to line segment 0,8 it could result in a calculation that exceeded the limits of the extended-precision. Computational geometry is notorious for numerical issues. Currently, Tinfour does include logic to tweak the coordinates of a vertex if it gets too close to a line segment and to insert it into the line rather than building a triangle. In this case, vertex 5 wasn't quite close enough to trigger the adjustment. While this situation did not affect the integrity of the TIN, it did challenge the ordinary-precision area computation.

Jonathan Shewchuk has published algorithms and C-language code for various triangle-geometry computations that work under all conditions. Mr. Shewchuk is pretty much the leading authority on Delaunay Triangulations, an excellent writer, and a pretty fair coder. If you are interested in the Delaunay, his work is well worth considering.

from tinfour.

The code changes for this issue are now complete.

I would like to thank Michael Kemper for identifying this problem and providing such an excellent set of test data. Those 9 vertices in his sample set exercise the Tinfour logic with admirable thoroughness.

from tinfour.

This issue in now fully addressed. Fixes are included in the 2.1.5 release which was issued 10 Jan 2021.

from tinfour.