Related to this commit bf36bb0
Struggled with this myself for replacing isParallel. (See FS#2495)
The naive implementation of Heron's formula can lead to Catastrophic Cancellation (CC).
Although that based on the length of a side < 1e-9 some flat triangles are simply excluded to start with.
When line segments are collinear and not touching/overlapping then we calculate the area of obtuse triangles with larger sides and where one interior angle is nearly 180° or where the height of the triangle is nearly zero.
For the area to be less than 1e-9 the rootTerm in RTriangle::getArea() has to be be less than 1.0e-18.
Meaning that one of the sides must be nearly as long as half the perimeter what is s = (a + b + c) / 2.
For sides longer than 0.01, such a precision cannot be stored, and we essentially rely on digit cancellation to make the answer true.
There is a more robust method [Kahan 1986] to implement Heron's formula.
rootTerm = (a+(b+c))*(c-(a-b))*(c+(a-b))*(a+(b-c)) where a ≥ b ≥ c and what should not be simplified further.
And then: area = sqrt(rootTerm)/4.
Essentially based on the general advice on how to avoid CC and that is to sum (subtract) smaller values first.And we can expect some discrepancies with the 101 operations (counted
) required to answer with true on the question isCollinear?As implemented, the isCollinear property is segment size relative but also relative to the distance between line segments.
As always, position in the plane affects the precision of the calculations and thus the area result of the triangles.
Farther from the origin, much larger intermediate values with less decimal precision can be expected.
What is important here is precisely the minute difference with zero.
Then both implementation of Heron's formula benefit from translating the triangles to near the origin.
For example by subtracting the start point of the first segment from all 4 coordinates.
Basically the same method as calculating the length of a line segment ...
... What is the magnitude of the end point vector when the start point is translated to the origin.
I finally settled for another approach that calculates the distances of the second endpoints to the infinite line based on the first endpoints.
When about equal the line segments are parallel with a known deviation.
When both about equal to zero then the line segments are collinear, again with a known tolerance.
A method based on RLine::getVectorTo() but then with a twist.
Regards,
CVH