public struct Global

Public Structure Global

public value class Global

Floating point arithmetic is not exact. Errors occur due to

• finite precision
• round off errors

This is an intrinsic problem one should specifically be aware of when doing geometric computations. Consider the following example:

CopyC#

public void TestPlaneContainsPoint()
{
       Global.AbsoluteEpsilon = 0; // set all error bound to zero to
       Global.RelativeEpsilon = 0; // enforce exact comparison
       Global.MaxRandom = 1e0;     // produce random values between [0...1]

       int err = 0;
       int n = 100000
       for ( int i = n; i > 0; i-- )
       {
           Plane pl = Plane.RandomPlane();
           Point p = pl.RandomPointOnPlane(); // this point should always lie on the plane!
           if ( !pl.Contains(p) ) err++;
       }
       Console.WriteLine(err + " of " + n + " tests failed!");
}

Although one would expect that a point p always lies on pl, the output is '100000 of 100000 tests failed!'. This simple example shows that a geometric test relying on floating point arithmetic is generally futile if the test depends on an exact result. A formally correct solution could be the implementation of exact arithmetic which on the other hand slows all computations significantly down. The decimal data type decimal does not address this problem since it is a slow finite precision 128 bit data type but still not exact. In many cases the results obtained using exact arithmetic may not be of practical use as well: if the input data does not have infinite precision, tests will fail at large.

This library addresses this problem in three ways by

• implementing robust algorithms
• normalizing data when advantageous
• implementing an absolute AND a relative delta comparison

The absolute delta comparison has the form Math.Abs(a - b) > AbsoluteEpsilon

The relative delta comparison has the form

Math.Abs((a - b) / a) > RelativeEpsilon for a > b

or

Math.Abs((a - b) / b) > RelativeEpsilon else.

Let's give TestPlaneContainsPoint a second chance:

The result looks fine: '0 of 100000 tests failed!'. But then again,

CopyC#

...
       Global.AbsoluteEpsilon = 1e-12; 
       Global.RelativeEpsilon = 0; // set this value zero for absolute epsilon comparison only!
       Global.MaxRandom = 1e9;     // produce random values between [0...1000000000]
...

outputs: '70511 of 100000 tests failed!'. This happens because we only allow a tiny absolute error of 1e-12. Since the double value type has a precision of 15-16 decimal digits, a bound of 1e-12 works well with coordinates between 0 and 1. Setting Global.MaxRandom = 1e9 generates coordinates up to a billion with a precision of only 6-7 decimal digits. Obviously, the absolute epsilon is too restrictive in this case. Increasing the absolute epsilon value is not a good choice. It is better to do a relative comparison in addition:

CopyC#

...
       Global.AbsoluteEpsilon = 1e-12; 
       Global.RelativeEpsilon = 1e-12; 
       Global.MaxRandom = 1e9;  // produce random values between [0...1000000000]
...

The outputs is '8 of 100000 tests failed!'.

The AlmostEquals method

In your own computations, you can easily benefit from the absolute and relative comparison concept of this library. When comparing two double precision values a and b, write

rather than

CopyC#

...
    if (a == b) ...
...

You can still influence the result of the comparison adjusting the AbsoluteEpsilon and RelativeEpsilon fields while you increase the robustness and scalability of your algorithms at the same time.