#184 a Numerical bug in the function Area

[Enyi Tang]

Dear Angus,

The function "double Area(const Path &poly);" in the Clipper library may suffer from numerical errors when the loop in the function just adds the components one by one. I build a rectangle with the size of "height*1" to reproduce the bug as follows:

#include <iostream>
#include <iomanip>
#include "clipper.hpp"
using namespace ClipperLib;</iomanip></iostream>

int main() {
Paths subj(2);
cInt height = 9100000000000000; // area of the "height*1" rectangle should be 9.1e+15

subj[0] <<
IntPoint(2,height+1) << IntPoint(2,1) << IntPoint(1,1);

cInt step_num = 26700000; // more errors are accumulated if the memory is big enough
int i=1;
for(i=2;i<=step_num;i++) {
subj[0] << IntPoint(1,i);
}
subj[0]<< IntPoint(1,height+1);
std::cout << "Area: " << std::setprecision(11) << std::scientific << Area(subj[0]) << std::endl;

subj[1] <<
IntPoint(1,1) << IntPoint(1,height+1) <<
IntPoint(2,height+1) << IntPoint(2,1);
std::cout << "Area_correct:" << Area(subj[1]) << std::endl;

return 0;
}

The output of the program is:
Area: -9.10000002670e+15
Area_correct:-9.10000000000e+15

The numerical error will be very big when you increase the value of "step_num " in the program and execute it on a computer with larger memory. For example, the output of the program can be -1.82e+16 if the "step_num" is set to 9.1e+15.

The problem can be improved with Kahan summation algorithm. I can provide a fixing advice later if it is necessary.

Thanks and Regards,

Enyi Tang
Software Institute of Nanjing University