Improve epsilon logic

[manubb]

This is an attempt to improve epsilon.js. Failing example of #3 should be correctly handled with an epsilon value less than 1e-14 and it seems that this does not break demo examples.

[velipso]

This is really interesting. Did you pull these from a math reference, or did you derive them yourself? I really want to understand the ideas behind this, do you know how I could go about doing that?

[manubb]

Sorry for the delay. I am using standard math results in plane geometry but i can not give you good reference written in english. Note that a possible solution to get rid of epsilon logic could be to use a arbitrary-length rational number library such as BigRational for example.

[velipso]

Thanks for your help. I don't want to merge until my understanding is better. I will recommend people try these changes if they have epsilon issues in the meantime.

Generally, I don't understand the impact of multiplying the epsilon value by something:

return Math.abs(dx1 * dy2 - dx2 * dy1) <= eps * (n1 + n2);

If (n1 + n2) is less than 1, then it effectively creates a smaller epsilon.

I need more eyeballs looking at this problem.

[manubb]

I add some details for the formula in pointAboveOrOnLine. Consider a line L passing through points: A(Ax, Ay) and B(Bx, By). Then vector v(-(By-Ay)/AB, (Bx-Ax) / AB) is unitary, orthogonal to vector AB and counterclockwise oriented with respect to vector AB. Hence, if C(Cx, Cy) is some point, the inner product of vectors AC and v is the algebraic distance between C and line L which can be expressed by: -(Cx - Ax)(By - Ay) / AB + (Cy - Ay)(Bx - Ax) / AB Now if we want C to be nearly "over" L with a tolerance of epsilon, we get: -(Cx-Ax)(By-Ay) / AB + (Cy - Ay)(Bx - Ax) / AB >= -epsilon or (Cy - Ay)(Bx - Ax) - (Cx - Ax)(By - Ay) >= -epsilon * AB

[manthey]

This branch is more robust than the current master. Specifically, current master often generates polygons that violate epsilon, with generated sides less than fall below the epsilon length. This branch doesn't cure that completely, but reduces it greatly.

[Henry00IS]

I added these changes to a (near 1:1) C# port of PolyBoolJS. It immediately solved all "PolyBool: Zero-length segment detected; your epsilon is probably too small or too large" errors that I encountered with very small intersect operations. It did not break any of my tests and just simply appears to be more robust.