davideberly
commented
6 months ago Adding "epsilon" in the algorithms is a rabbit hole I choose not to go down. Infrequently, there might be a need and I use an epsilon, but not as a general solution to dealing with floating-point error. Is the epsilon relative or absolute? How small (or large) must it be? If the epsilon is absolute, the magnitude of epsilon depends on the input data, so the user must decide what epsilon to choose based on an understanding of the characteristics of the input.
Regarding your example, my choice of GetCenteredForm is unfortunate. I tried to formulate the segments in the manner of an oriented bounding box (center+direction+extent), but yes, the rounding errors can be a problem. I am eliminating the GetCenteredForm in GTL. For code that is not time critical (for example, not intended for real-time applications and not used in a very large number of queries), I prefer the rational number approach. If you use BSRational
using Rational = BSRational<UIntegerAP32>;
Segment2<double> segment0{}, segment1{};
segment0.p[0] = { 100.0, 1900.0 };
segment0.p[1] = { 900.0, 1900.0 };
segment1.p[0] = { 550.0, 601.0 };
segment1.p[1] = { 550.00000000000034, 1900.0 };
FIQuery<double, Segment2<double>, Segment2<double>> query{};
auto result = query(segment0, segment1);
// result.intersect = false
// result.numIntersections = 0
// result.segment0Parameter = { 0.0, 0.0 }
// result.segment1Parameter = { 0.0, 0.0 }
// result.point[0] = { 0.0, 0.0 }
// result.point[1] = { 0.0, 0.0 }
result = query.Exact(segment0, segment1);
// result.intersect = true
// result.numIntersections = 1
// result.segment0Parameter = { 0.56250000000000044, 0.56250000000000044 }
// result.segment1Parameter = { 1.0, 1.0 }
// result.point[0] = { 550.00000000000034, 1900.0000000000000 }
// result.point[1] = { 550.00000000000034, 1900.0000000000000 }
Segment2<Rational> rsegment0{}, rsegment1{};
rsegment0.p[0] = { 100.0, 1900.0 };
rsegment0.p[1] = { 900.0, 1900.0 };
rsegment1.p[0] = { 550.0, 601.0 };
rsegment1.p[1] = { 550.00000000000034, 1900.0 };
FIQuery<Rational, Segment2<Rational>, Segment2<Rational>> rquery{};
auto rresult = rquery(rsegment0, rsegment1);
FIQuery<double, Segment2<double>, Segment2<double>>::Result convert{};
convert.intersect = rresult.intersect;
convert.numIntersections = rresult.numIntersections;
convert.segment0Parameter[0] = rresult.segment0Parameter[0];
convert.segment0Parameter[1] = rresult.segment0Parameter[1];
convert.segment1Parameter[0] = rresult.segment1Parameter[0];
convert.segment1Parameter[1] = rresult.segment1Parameter[1];
convert.point[0][0] = rresult.point[0][0];
convert.point[0][1] = rresult.point[0][1];
convert.point[1][0] = rresult.point[1][0];
convert.point[1][1] = rresult.point[1][1];
// convert.intersect = true
// convert.numIntersections = 1
// convert.segment0Parameter = { 50.000000000000341, 50.000000000000341 }
// convert.segment1Parameter = { 649.50000000000000, 649.50000000000000 }
// convert.point[0] = { 550.00000000000034, 1900.0000000000000 }
// convert.point[1] = { 550.00000000000034, 1900.0000000000000 }
owai1980
Hello,
I have a problem while calculating the intersection of 2 "Segment2<double>"
i know it's a precision problem, and maybe the answer is "don't use the double version" ... but i still want to explain:
(they make a "T" shape like this:) segment0 = (100, 1900) , (900,1900) segment1 = (550, 601) , (550.00000000000034,1900)
as you can see, i have a small precision error on the "x1" coordinate of segment1
when i call the Result() function in IntrSegment2Segment2.h (line 215), the result is "intersect = false" (line 244), probably because of the GetCenteredForm() before...
I understand that the precison of the "double" is difficult to manage, but i though there was a "tolerance range" somewhere in GeometricTools (?) maybe i'm wrong...
edit : the "tolerance" parameter is "epsilon", used in Arc2.h ... maybe we should use it in Segment2 too... what do you think?
thank you
Johan