Hi Luke,
Fernando Cacciola wrote:
IIRC there has never been a precedent of a Boost library practically requiring (to be actually useful) an external non-boost library, so this deserves its own discussion.
While in the case of GTL, it is thechnically up to the user to pick up "their own" multipresicion number types, they actually can't do that without an external non-boost library since such number types do not exists in the SCL.
That may be too strong a statement. Long double provides quite a few bits of precision. There is some upper limit of input bit width which long double is still sufficient to compute the exact result. As that bit width is exceeded the odds of a fault increase as the input bit width increases. If we say the library is by default robust only up to 25 bits (or whatever I determine to be the case) then users have the option of performing robust calculations within that constraint.
The problem with this view is that users have no way to restrain the input in such a way that all calculations are exact within N bits, for whatever N. Users are completely helpless since they just have their input, whatever that is, and they can't do anything about it to make the algorithm work with a number type of N bits because they just wouldn't know what to do. That is, there is no know normalization process that can be applied to the input so as to keep the required number of working bits within long double that can be applied to general geometric algorithms. There has been some research, for example, on using single precision in the input so as to keep exact results within long double when doing line intersections (so that applies to clipping) but it doesn't generalize to other algoritrhms and pose certain restrictions on the input data itself (sort of force a snapping on it), which may very well be unacceptable if the input uses floating-point to begin with (instead of integer or fixed-precision coordinates) Keep in mind that we don't see GTL as a "clipping" library only, so its robustness must be general. Floating point operarions won't even trap if they loose significant precision (if programmed in portable C++), so the ibrary will just silently fail to produce a correct result. I like to consider Robustness as an all or nothing game: it can't work in 100%-epsilon cases. It is either 100% robust or not all.
If they want to handle larger inputs they can provide high precsion data types to override long double.
This won't work. There is no definition of "larger input" that a user can measured. Here's a practical example: Implement a predicate to compare the distance between two intersection points of two *lines* given as two points each against a third using long double. That is, the predicate takes 9 points. Now feed into that two almost parallel lines like these: the first being vertical and VERY SHORT, say with the top point 1e-2 away fromm the botton. the second almost vertical but VERY LARGE, with the top and bottom vertices separated by, say 1e4 or so, and with one of the vertices slightly shifted by a very small amount, say 1e-3 (to make it NOT really vertical) And a similar setup but with vertical lines. Now lay with the small distances in there to see how way off the long double precision you need to be to compute that predicate exactly.
I have been quite successful in executing very large test cases without needing gmp. I performed the n-layer map overlay on dozens of layers of thousands of segmented circles each that were intersecting quite frequently and it ran just fine without gmp.
That experience just isn't sufficient. Here's a tale of a similar experience: When I first incorporated GPC (which btw has, easily, thousands of users) into a project, I spend a lot of time studying its robutness by feeding it specially designed test cases. It passed them all, so it appeared to evident that it was robust for all practical purposes. The project evolved until one day I started to recieve, with increasing frequency, bug reports that boiled down (after many wated hours) to be robustness issues within GPC. Soon a geometric pattern popped up as the culprit: a complex figure F and another figure F2 obtained by shifting F a really *really* small amount, then subtrating F2 from F. That pattern totally choked GPC, even after years of succidingly producing correct results. In the end my client had to buy the CGAL clipper wich is slower, nowhere cheap, but truly 100% robust. For general geometric problems there is no *practical* input geometry constrain (that a user can measure and handle) which would guarantee that only M bits of working precision are needed, so 100% robustness can ONLY come from the ability of the implementation to adaptively use as many bits as needed. Only in a case-by-case basis it is possible to measure the upper bounds on the number of bits needed and then state whether long double is good enough ot not. But then, for the specific case of clipping, it turns out that the number of required working bits for ALL posible input can be shown to be way off the precision of long double, even if the input is restricted to floats unless it is restricted to a float grid. Best -- Fernando Cacciola SciSoft Consulting, Founder http://www.scisoft-consulting.com