#180 Numerical Error when calling CleanPolygon

[Enyi Tang]

Dear Angus,

According to the documentation of Clipper, the function CleanPolygon should remove vertices that join co-linear edges. But a bug occurs with the following code snippet when the points p1, p2, and p3 are collinear exactly.

Paths subj(1);
IntPoint p1(9000000000000000001,9000000000000000501);
IntPoint p2(101,601);
IntPoint p3(1,501);
IntPoint p4(4500000000000000000,15);
subj[0] << p1 << p2 << p3 << p4;

CleanPolygon(subj[0], 10.0);

The function CleanPolygon does not remove any vertices in the code above. But if we add the points in a backward order to the Path subj[0], the result is correct that p2 is removed after CleanPolygon.

We are tracing the bug. It seems that it is a numerical error in the Clipper library. And we would love to provide a fixing advice later if you need it.

Thanks and Regards,

Enyi Tang
Software Institute of Nanjing University

[Enyi Tang]

After analyzing the bug with our numerical tools, we believe the bug can be fixed by changing the code in DistanceFromLineSqrd() as follows: (about line 4339 of clipper.cpp)

-- double C = A * ln1.X + B * ln1.Y;
++ double C = double(ln2.X) * ln1.Y - double(ln2.Y) * ln1.X;

Although the fixed expression is mathematically equivalent to the original expression, they yield different outputs in floating-point values. When A == double(ln1.Y - ln2.Y) && B == double(ln2.X - ln1.X), the fixed expression get the value C in a shorter routine.