Some distance related tests are failing

[vissarion]

This is most probably related to #1461 that changed the andoyer strategy. There are some test now that are failing https://github.com/boostorg/geometry/actions/runs/26745968510/job/78821418143
@mjacobse have you observed these locally?

[mjacobse]

Sorry for having overlooked this, I wasn't aware but I can indeed reproduce it locally.

For the closest_points tests I'm pretty sure one can argue that these tests happened to pass exactly because the andoyer results suffered from loss of precision. Enabling the debug output in those tests and comparing the output for before and after #1461 shows this quite well I believe (see below).

The now failing check dist3 == 0 seems to have passed previously because for too close points andoyer always returned 0 due to loss of precision. Now andoyer can actually still compute relevant values near 0, with the side effect that they are not exactly 0 anymore.

The now failing comparison of distance, dist1 and dist2 with the tiny tolerance 1e-20 seems to have passed previously because loss of precision resulted in the completely wrong value of 9cm (which was also observed in #1461) for all of those distances. Now andoyer actually computes meaningful values, with the side effect that they are not exactly equal anymore. As an example, for the last test case:

• before: Projection: LINESTRING(11.9145197820080248618523910409 50.3191387652345838432665914297,11.9145197830847584833866004139 50.3191387750114706364779060266) was computed to have a distance of 0.0952303502614368509895221258377 where GeodSolve gives a distance of 0.0010902346
• after: Projection: LINESTRING(11.9145197820080248618523910409 50.3191387652345838432665914297,11.9145197820023912441481095392 50.3191387651834230870795394708) was computed to have a distance of 5.72058672978090131263849065891e-06 where GeodSolve gives a distance of 5.7038e-06

So I don't think these closest_points failures reveal an actual regression, I think their tolerances just need to be adapted now that they are comparing actually meaningful distance values. Let me know if I'm wrong. For buffer_linestring_geo I am not sure, will have to look into it later.

closest_points test output before (red) and after (green) #1461:

< Distance: 0
< Projection: LINESTRING(11.8457476006049162720046297181 50.3032477699869531306831049733,11.8457475998077352841164611164 50.303247769809971146059979219)
< Distance 1: 0
< Distance 2: 0
< Distance 3: 0
---
> Distance: 6.01256751754931963714102816088e-05
> Projection: LINESTRING(11.8457476006049162720046297181 50.3032477699869531306831049733,11.8457475998077530476848551189 50.30324776980997825148733682)
> Distance 1: 6.01256751754931963714102816088e-05
> Distance 2: 6.01256751754931963714102816088e-05
> Distance 3: 7.24325323896676570752106716355e-05
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(377): error: in "closest_path_test_1": check dist3 == 0 has failed
11,15c12,17
< Distance: 0
< Projection: LINESTRING(11.8457476006049162720046297181 50.3032477699869531306831049733,11.8457475998078173209243635355 50.3032477698099871228631929654)
< Distance 1: 0
< Distance 2: 0
< Distance 3: 0
---
> Distance: 6.01262586467038521854965301908e-05
> Projection: LINESTRING(11.8457476006049162720046297181 50.3032477699869531306831049733,11.8457475998077444790182455314 50.3032477698099744004012201515)
> Distance 1: 6.01262586467038521854965301908e-05
> Distance 2: 6.01262586467038521854965301908e-05
> Distance 3: 7.24327855055866837426124898146e-05
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(377): error: in "closest_path_test_1": check dist3 == 0 has failed
18,22c20,25
< Distance: 29.1240632519128510580230795313
< Projection: LINESTRING(11.92141819000244140625 50.316425323486328125,11.9214904360830686869121564087 50.3161676201328660340550413821)
< Distance 1: 29.1240632519128510580230795313
< Distance 2: 29.1240632519128510580230795313
< Distance 3: 0
---
> Distance: 29.1241033831801310327591636451
> Projection: LINESTRING(11.92141819000244140625 50.316425323486328125,11.9214904813568800534540059743 50.316167625346636782524001319)
> Distance 1: 29.1241033832001576797665620688
> Distance 2: 29.1241033831801310327591636451
> Distance 3: 4.60897976160482675776763894504e-05
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(377): error: in "clostest_path_test_2": check dist3 == 0 has failed
25,29c28,33
< Distance: 29.1240990443179248482741261483
< Projection: LINESTRING(11.92141819000244140625 50.316425323486328125,11.9214909576474712739335704015 50.3161676801965673209993124004)
< Distance 1: 29.1240990443179248482741261483
< Distance 2: 29.1240990443179248482741261483
< Distance 3: 0
---
> Distance: 29.1241033839194206189054936473
> Projection: LINESTRING(11.92141819000244140625 50.316425323486328125,11.9214904813532107273263416225 50.3161676253462097838098365798)
> Distance 1: 29.1241033839194151666696086522
> Distance 2: 29.1241033839194206189054936473
> Distance 3: 4.63554270051083547192384582016e-05
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(377): error: in "clostest_path_test_2": check dist3 == 0 has failed
32c36
< Distance: 0
---
> Distance: 6.06207341155661465085038863698e-05
34,35c38,39
< Distance 1: 0
< Distance 2: 0
---
> Distance 1: 6.06207341155661465085038863698e-05
> Distance 2: 6.06207341155661465085038863698e-05
39,42c43,46
< Distance: 0
< Projection: LINESTRING(11.9046241249185611689107022748 50.3173498610000256917040850624,11.904624125767752103495500382 50.3173498610365690607293398529)
< Distance 1: 0
< Distance 2: 0
---
> Distance: 6.0620587846145458370692944556e-05
> Projection: LINESTRING(11.9046241249185611689107022748 50.3173498610000256917040850624,11.9046241257677784695576117535 50.3173498610365690607293398529)
> Distance 1: 6.0620587846145458370692944556e-05
> Distance 2: 6.0620587846145458370692944556e-05
46,49c50,53
< Distance: 0
< Projection: LINESTRING(11.9073288875530405306335524074 50.311933736642274084260861855,11.9073288708422673209952336038 50.3119337354121611838309036102)
< Distance 1: 0
< Distance 2: 0
---
> Distance: 0.00019398015225232967699217634383
> Projection: LINESTRING(11.9073288875530405306335524074 50.311933736642274084260861855,11.9073288848476863677205983549 50.3119337364431231662820209749)
> Distance 1: 0.00019398015225232967699217634383
> Distance 2: 0.00019398015225232967699217634383
53,56c57,60
< Distance: 0
< Projection: LINESTRING(11.9073288875530410172234874189 50.3119337366422723079040224547,11.9073288848478320471960256732 50.3119337364431386643015553517)
< Distance 1: 0
< Distance 2: 0
---
> Distance: 0.000193980294539164160187509894763
> Projection: LINESTRING(11.9073288875530410172234874189 50.3119337366422723079040224547,11.9073288848476833302197919195 50.3119337364431259418395825378)
> Distance 1: 0.000193980294594111104929888669867
> Distance 2: 0.000193980294539164160187509894763
57a62,63
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(375): error: in "clostest_path_test_4": difference{2.8326e-10} between distance{0.000193980294539164160188} and dist1{0.00019398029459411110493} exceeds 9.9999999999999995e-21
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(376): error: in "clostest_path_test_4": difference{2.8326e-10} between dist1{0.00019398029459411110493} and dist2{0.000193980294539164160188} exceeds 9.9999999999999995e-21
60c66
< Distance: 98.7573313182803644849627744406
---
> Distance: 98.7573316108711054539526230656
62,63c68,69
< Distance 1: 98.7573313182860488268488552421
< Distance 2: 98.7573313182803644849627744406
---
> Distance 1: 98.7573316102123328619200037792
> Distance 2: 98.7573316108711054539526230656
67c73
< Distance: 98.7573314177873350164227339576
---
> Distance: 98.7573316108269581847789453377
69,70c75,76
< Distance 1: 98.7573314177873350164227339576
< Distance 2: 98.7573314177873350164227339576
---
> Distance 1: 98.7573316108269581847789453377
> Distance 2: 98.7573316108269581847789453377
74c80
< Distance: 0.0952303891580851269438312556304
---
> Distance: 5.7214816833467354003695849729e-06
76,77c82,83
< Distance 1: 0.0952303891580851269438312556304
< Distance 2: 0.0952303891580851269438312556304
---
> Distance 1: 5.72147374098834537379772505195e-06
> Distance 2: 5.7214816833467354003695849729e-06
78a85,86
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(375): error: in "clostest_path_test_6": difference{1.38817e-06} between distance{5.7214816833467354e-06} and dist1{5.7214737409883454e-06} exceeds 9.9999999999999995e-07
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(376): error: in "clostest_path_test_6": difference{1.38817e-06} between dist1{5.7214737409883454e-06} and dist2{5.7214816833467354e-06} exceeds 9.9999999999999995e-07
81,84c89,92
< Distance: 0.0952303502614368509895221258377
< Projection: LINESTRING(11.9145197820080248618523910409 50.3191387652345838432665914297,11.9145197830847584833866004139 50.3191387750114706364779060266)
< Distance 1: 0.0952303502614368509895221258377
< Distance 2: 0.0952303502614368509895221258377
---
> Distance: 5.72058672978090131263849065891e-06
> Projection: LINESTRING(11.9145197820080248618523910409 50.3191387652345838432665914297,11.9145197820023912441481095392 50.3191387651834230870795394708)
> Distance 1: 5.72058707537386660448861116528e-06
> Distance 2: 5.72058672978090131263849065891e-06
85a94,95
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(375): error: in "clostest_path_test_6": difference{6.04122e-08} between distance{5.72058672978090131264e-06} and dist1{5.72058707537386660449e-06} exceeds 9.9999999999999995e-21
> libs/geometry/test/algorithms/closest_points/pl_l.cpp(376): error: in "clostest_path_test_6": difference{6.04122e-08} between dist1{5.72058707537386660449e-06} and dist2{5.72058672978090131264e-06} exceeds 9.9999999999999995e-21

[vissarion]

Thanks @mjacobse for looking into it and for the explanations! They make sense.

[mjacobse]

So to the buffer_linestring_geo test, looks to me like it is somewhat brittle by design with several aimes cases already being skipped? For what it's worth, when not skipping any of the aimes cases, on my machine i get more failures before #1461 than after:

< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(83): error: in "test_main_caller( argc_ argv )": aimes_67_rr has too many points too close 1 0.25
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_67_rr the area is too small, expected at least 1.0038978240812866 15735.3694290676200405
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(83): error: in "test_main_caller( argc_ argv )": aimes_67_rf has too many points too close 1 0.25
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_67_rf the area is too small, expected at least 1.0038978240812866 13870.0487909986804214
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_67_mf the area is too small, expected at least 1.0038978240812866 13870.0487909986804214
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(83): error: in "test_main_caller( argc_ argv )": aimes_75_rr has too many points too close 1 0.25
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_75_rr the area is too small, expected at least 0.88516416214245308 181972.734849147301233
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(83): error: in "test_main_caller( argc_ argv )": aimes_75_rf has too many points too close 1 0.25
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_75_rf the area is too small, expected at least 0.88516416214245308 180107.414211078361618
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_75_mf the area is too small, expected at least 0.88516416214245308 180107.414211078361618
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(83): error: in "test_main_caller( argc_ argv )": aimes_143_rr has too many points too close 0 -nan
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_143_rr the area is too small, expected at least 0 31560.1310448355204148
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(83): error: in "test_main_caller( argc_ argv )": aimes_163_rr has too many points too close 0 -nan
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_163_rr the area is too small, expected at least 0 6078.31722878943595934
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_181_rr the area is too small, expected at least 198.67884304160947 13456.4538307680239546
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_196_rr the area is too small, expected at least 3123.6231780235703 3839.10287117092484532
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(110): error: in "test_main_caller( argc_ argv )": aimes_196_rf the area is too large, expected at most 3085.1102900239348 2181.54878395482597031
< libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(110): error: in "test_main_caller( argc_ argv )": aimes_196_mf the area is too large, expected at most 3095.2041616605575 2181.54878395482597031
---
> libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(83): error: in "test_main_caller( argc_ argv )": aimes_142_rf has too many points too close 27 0.21774193548387097
> libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_163_rr the area is too small, expected at least 0.3960070623284383 6078.23062138917850472
> libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(107): error: in "test_main_caller( argc_ argv )": aimes_196_rr the area is too small, expected at least 3131.6254344328045 3837.61941625412861545
> libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(110): error: in "test_main_caller( argc_ argv )": aimes_196_rf the area is too large, expected at most 3131.6254344328045 2179.90917588889329526
> libs/geometry/test/algorithms/buffer/test_buffer_geo.hpp(110): error: in "test_main_caller( argc_ argv )": aimes_196_mf the area is too large, expected at most 3132.344157293805 2179.90917588889329526

[barendgehrels]

So to the buffer_linestring_geo test, looks to me like it is somewhat brittle by design with several aimes cases already being skipped? For what it's worth, when not skipping any of the aimes cases, on my machine i get more failures before #1461 than after:

Thanks for testing this! So #1461 improves several of these cases, which also shows that it was a good PR (there was no discussion about that). We can turn these newly passing cases on.

About the test design - it's true that there are several tests skipped. And it's also true that it seems hard to manage. So you might indeed say it's brittle.

But we need these tests on themselves. It tests nearly 200 cases, all in 3 combinations of join and end strategies, so nearly 600. Of them, there are around 40 skipped - but then there are still > 500 passing.

It's a test with live data (not simulated) from more than 15 years ago, and have never passed 100% yet for the geo-variant. So that's still a challenge and I'm glad we're a bit closer.

The not passing tests (I investigated some of them several times over the years) fail by different reasons.

I'm sure we can enhance the test design by testing it in a different way (it's indeed complex), but currently I don't have the time for that (and maybe there are other things with more priority).

[barendgehrels]

Thanks @mjacobse for looking into it and for the explanations! They make sense.

Indeed thanks @mjacobse for this

The now failing check dist3 == 0 seems to have passed previously because for too close points andoyer always returned 0 due to loss of precision. Now andoyer can actually still compute relevant values near 0, with the side effect that they are not exactly 0 anymore.

The now failing comparison of distance, dist1 and dist2 with the tiny tolerance 1e-20 seems to have passed previously because loss of precision resulted in the completely wrong value of 9cm (which was also observed in #1461) for all of those distances. Now andoyer actually computes meaningful values, with the side effect that they are not exactly equal anymore.

So we now know exactly what happens, great.

What's the best way to "fix" it? At least we can add these comments.

[barendgehrels]

About the text boost_geometry_algorithms_buffer_linestring_geo

For me the next set runs

#if defined(BOOST_GEOMETRY_TEST_FAILURES)
    std::set<int> const cases_with_artefacts{};
    std::set<int> const curved_cases_min_area{};
    std::set<int> const curved_cases_max_area{};
    std::set<int> const skip_cases_round_round{};
    std::set<int> const skip_cases_round_flat{};
    std::set<int> const skip_cases_miter_flat{};
#else
    // Cases where the algorithm is still failing.
    // It might differ in debug/release mode.
    // It might also depend on the compiler and on the operating system.

    // Cases which are curved and have some artefacts
    std::set<int> const cases_with_artefacts{119, 142};
    // Cases which are curved such that the min area is smaller than expected.
    std::set<int> const curved_cases_min_area{86, 181};
    // Cases which are curved such that the max area is larger than expected.
    std::set<int> const curved_cases_max_area{5, 95, 119, 142};

    std::set<int> const skip_cases_round_round{196};
    std::set<int> const skip_cases_round_flat{142, 196};
    std::set<int> const skip_cases_miter_flat{196};
#endif

Original there were more cases marked as failing:

    std::set<int> const skip_cases_round_round{17, 22, 38, 67, 75, 109, 163, 181, 143, 196};
    std::set<int> const skip_cases_round_flat{17, 22, 38, 67, 75, 103, 109, 142, 196};
    std::set<int> const skip_cases_miter_flat{17, 18, 22, 38, 67, 75, 103, 109, 196};

That means a lot of cases are fixed in the meantime, by some reasons.
Seeing @mjacobse 's list, 67 and 75 143 and 181 are solved by the enhanced Andoyer.
However, this is on my machine (@mjacobse also reported 163 as failing) - in Debug and Release mode