Subsequent errors in difference related to switch traversal

[barendgehrels]

This is a follow up of issue #869 and the pull request #887

@kleunen found an issue with this code (I adapted it slightly to give more output):

#include <iostream>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/multi_polygon.hpp>

using point_t = boost::geometry::model::d2::point_xy<double>;
using polygon_t = boost::geometry::model::polygon<point_t>;
using ring_t = boost::geometry::model::ring<point_t>;
using multi_polygon_t = boost::geometry::model::multi_polygon<polygon_t>;


int main()
{
    std::vector<multi_polygon_t> input(39);

    boost::geometry::read_wkt("MULTIPOLYGON(((0.603549 0.394417,0.517116 0.432156,0.563288 0.385417,0.492528 0.36544,0.577515 0.295956,0.550593 0.255888,0.452782 0.221035,0.459249 0.333709,0.441865 0.351136,0.370548 0.331001,0.385816 0.296593,0.394882 0.293488,0.387958 0.291767,0.423911 0.210747,0.392721 0.199633,0.310001 0.272391,0.236386 0.254095,0.304173 0.168082,0.296274 0.165267,0.207506 0.246917,0.0140798 0.198842,0.069792 0.24609,0.0159663 0.230894,0.0815688 0.362756,0.0156364 0.423401,0.0977468 0.395274,0.108341 0.416568,0.135246 0.382428,0.203132 0.359173,0.207309 0.362716,0.174164 0.39187,0.173365 0.391061,0.173401 0.392541,0.11983 0.439661,0.177364 0.555306,0.177972 0.580239,0.0906064 0.618386,0.127028 0.663916,0.0564116 0.721999,0.127196 0.664127,0.181673 0.732227,0.182236 0.755361,0.188638 0.740934,0.199131 0.754051,0.261029 0.691392,0.320648 0.715618,0.224866 0.786223,0.382462 0.983231,0.466763 0.85994,0.47812 0.838165,0.39515 0.926659,0.476824 0.77908,0.50332 0.789847,0.525393 0.747525,0.505459 0.72734,0.547556 0.651273,0.566996 0.667759,0.59721 0.609827,0.598711 0.558841,0.604247 0.548838,0.621545 0.563169,0.680308 0.450499,0.643761 0.47744,0.668916 0.431986,0.656761 0.413896,0.600941 0.483052,0.603549 0.394417)))", input[0]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.696266 0.142785,0.719425 0.179933,0.684151 0.208773,0.625869 0.119956,0.523067 0.0866194,0.476025 0.144909,0.550593 0.255888,0.603476 0.274731,0.577515 0.295956,0.605233 0.337207,0.603549 0.394417,0.634572 0.380871,0.656761 0.413896,0.710003 0.347935,0.717162 0.344809,0.668916 0.431986,0.729259 0.521793,0.717016 0.583363,0.740154 0.558685,0.74515 0.545443,0.748247 0.550053,0.751874 0.546184,0.780115 0.586441,0.783115 0.512864,0.842285 0.449754,0.788997 0.368549,0.791284 0.312445,0.799738 0.308754,0.992212 0.617482,0.959288 0.239088,0.973756 0.232771,0.958302 0.22776,0.938553 0.000778765,0.745381 0.158712,0.696266 0.142785)))", input[1]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.287131 0.506261,0.174164 0.39187,0.173401 0.392541,0.177364 0.555306,0.187664 0.576007,0.177972 0.580239,0.178814 0.61485,0.142867 0.650888,0.127028 0.663916,0.127196 0.664127,0.178983 0.621787,0.181673 0.732227,0.188638 0.740934,0.226862 0.654796,0.241025 0.683264,0.261029 0.691392,0.36551 0.585627,0.305289 0.524648,0.289209 0.531669,0.301942 0.521258,0.291026 0.510204,0.297299 0.496067,0.287131 0.506261)))", input[2]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.385816 0.296593,0.387958 0.291767,0.310001 0.272391,0.27427 0.30382,0.211225 0.286021,0.236386 0.254095,0.207506 0.246917,0.175851 0.276034,0.069792 0.24609,0.14191 0.307253,0.0815688 0.362756,0.0977468 0.395274,0.135246 0.382428,0.173427 0.333981,0.203132 0.359173,0.216572 0.354569,0.207309 0.362716,0.315687 0.454629,0.370548 0.331001,0.323855 0.317819,0.385816 0.296593)))", input[3]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.621545 0.563169,0.59721 0.609827,0.594811 0.691349,0.566996 0.667759,0.525393 0.747525,0.544737 0.767113,0.594132 0.714429,0.591197 0.814158,0.609997 0.833195,0.590866 0.825421,0.586751 0.965255,0.666999 0.75257,0.606487 0.701251,0.685935 0.616513,0.621545 0.563169)))", input[4]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.719425 0.179933,0.778422 0.274563,0.76895 0.322197,0.791284 0.312445,0.791944 0.296253,0.799738 0.308754,0.959288 0.239088,0.958302 0.22776,0.745381 0.158712,0.719425 0.179933)))", input[5]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.304173 0.168082,0.392721 0.199633,0.448726 0.150373,0.445833 0.0999749,0.468192 0.133251,0.521709 0.086179,0.399861 0.0466657,0.304173 0.168082)))", input[6]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.780115 0.586441,0.779691 0.59685,0.748247 0.550053,0.740154 0.558685,0.710619 0.636962,0.961172 0.844534,0.780115 0.586441)))", input[7]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.684151 0.208773,0.603476 0.274731,0.607034 0.275999,0.605233 0.337207,0.634572 0.380871,0.710003 0.347935,0.727272 0.326541,0.717162 0.344809,0.76089 0.325716,0.684151 0.208773)))", input[8]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.320648 0.715618,0.476824 0.77908,0.505459 0.72734,0.420902 0.641717,0.320648 0.715618)))", input[9]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.59913 0.544599,0.604247 0.548838,0.643761 0.47744,0.60016 0.509579,0.600941 0.483052,0.570444 0.520834,0.577247 0.52647,0.482633 0.596213,0.547556 0.651273,0.598711 0.558841,0.59913 0.544599)))", input[10]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.729259 0.521793,0.74515 0.545443,0.74732 0.539692,0.751874 0.546184,0.783115 0.512864,0.788997 0.368549,0.766538 0.334324,0.729259 0.521793)))", input[11]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.328117 0.465171,0.348942 0.482832,0.492528 0.36544,0.441865 0.351136,0.328117 0.465171)))", input[12]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.696266 0.142785,0.611653 0.00706631,0.573697 0.0404517,0.625869 0.119956,0.696266 0.142785)))", input[13]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.413212 0.537338,0.36551 0.585627,0.420902 0.641717,0.482633 0.596213,0.413212 0.537338)))", input[14]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.199131 0.754051,0.013265 0.942202,0.224866 0.786223,0.199131 0.754051)))", input[15]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.287131 0.506261,0.240627 0.552881,0.187664 0.576007,0.197613 0.596005,0.178814 0.61485,0.178983 0.621787,0.201344 0.603505,0.226862 0.654796,0.277112 0.541559,0.289209 0.531669,0.279648 0.535844,0.291026 0.510204,0.287131 0.506261)))", input[16]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.366654 0.497853,0.413212 0.537338,0.517116 0.432156,0.366654 0.497853)))", input[17]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.173427 0.333981,0.211225 0.286021,0.175851 0.276034,0.14191 0.307253,0.173427 0.333981)))", input[18]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.591197 0.814158,0.544737 0.767113,0.517876 0.795762,0.590866 0.825421,0.591197 0.814158)))", input[19]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.216572 0.354569,0.323855 0.317819,0.27427 0.30382,0.216572 0.354569)))", input[20]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.108341 0.416568,0.0230624 0.524775,0.11983 0.439661,0.108341 0.416568)))", input[21]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.663637 0.851798,0.711342 0.790176,0.681007 0.764449,0.663637 0.851798)))", input[22]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.663637 0.851798,0.60596 0.926301,0.651077 0.91496,0.663637 0.851798)))", input[23]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.279648 0.535844,0.240627 0.552881,0.197613 0.596005,0.201344 0.603505,0.277112 0.541559,0.279648 0.535844)))", input[24]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.701609 0.660841,0.666999 0.75257,0.681007 0.764449,0.701609 0.660841)))", input[25]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.366654 0.497853,0.348942 0.482832,0.301942 0.521258,0.305289 0.524648,0.366654 0.497853)))", input[26]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.791944 0.296253,0.796543 0.183435,0.778422 0.274563,0.791944 0.296253)))", input[27]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.450246 0.176853,0.425156 0.207942,0.423911 0.210747,0.452782 0.221035,0.450246 0.176853)))", input[28]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.70696 0.633931,0.717016 0.583363,0.685935 0.616513,0.70696 0.633931)))", input[29]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.450246 0.176853,0.476025 0.144909,0.468192 0.133251,0.448726 0.150373,0.450246 0.176853)))", input[30]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.47812 0.838165,0.517876 0.795762,0.50332 0.789847,0.47812 0.838165)))", input[31]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.59913 0.544599,0.60016 0.509579,0.577247 0.52647,0.59913 0.544599)))", input[32]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.297299 0.496067,0.328117 0.465171,0.315687 0.454629,0.297299 0.496067)))", input[33]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.573697 0.0404517,0.5677 0.0313133,0.527613 0.0809854,0.573697 0.0404517)))", input[34]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.594132 0.714429,0.606487 0.701251,0.594811 0.691349,0.594132 0.714429)))", input[35]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.701609 0.660841,0.710619 0.636962,0.70696 0.633931,0.701609 0.660841)))", input[36]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.76089 0.325716,0.766538 0.334324,0.76895 0.322197,0.76089 0.325716)))", input[37]);
    boost::geometry::read_wkt("MULTIPOLYGON(((0.527613 0.0809854,0.521709 0.086179,0.523067 0.0866194,0.527613 0.0809854)))", input[38]);

    std::cout << std::boolalpha << std::setprecision(12);
    
    int n = 0;
    std::reverse(input.begin(), input.end());
    while(input.size() > 1) {
        std::size_t divide_i = input.size() / 2 + input.size() % 2;
        for(std::size_t i = 0; i < input.size() / 2; ++i) {
            std::size_t index = i + divide_i;
            if(index < input.size()) {
                multi_polygon_t result;
                boost::geometry::sym_difference(input[index], input[i], result);
                if (!boost::geometry::is_valid(result))
                {
                    multi_polygon_t result_a, result_b, result_i, result_u;
                    boost::geometry::difference(input[index], input[i], result_a);
                    boost::geometry::difference(input[i], input[index], result_b);
                    boost::geometry::intersection(input[index], input[i], result_i);
                    boost::geometry::union_(input[index], input[i], result_u);

                    std::cout << n << " validity: "
                              << " 1: " << boost::geometry::is_valid(input[index])
                              << " 2: " << boost::geometry::is_valid(input[i])
                              << " i: " << boost::geometry::is_valid(result_i)
                              << " u: " << boost::geometry::is_valid(result_u)
                              << " a: " << boost::geometry::is_valid(result_a)
                              << " b: " << boost::geometry::is_valid(result_b)
                              << " s: " << boost::geometry::is_valid(result)
                              << std::endl;

//                    std::cout << boost::geometry::wkt(input[index]) << std::endl;
//                    std::cout << boost::geometry::wkt(input[i]) << std::endl;


                }
                input[i] = std::move(result);
                n++;
            }
        }

        input.resize(divide_i);
    }
    
    std::cout << "Is valid: " << boost::geometry::is_valid(input[0]) << std::endl;
    return 0;
}

The result is (both with BOOST_GEOMETRY_NO_ROBUSTNESS and without), in the develop branch:
Is valid: true
but in the branch where it is fixed:

34 validity:  1: true 2: true i: true u: true a: false b: true s: false
37 validity:  1: true 2: true i: true u: true a: true b: false s: false
Is valid: false

First set of input causing invalid output:

MULTIPOLYGON(((0.450246 0.176853,0.476025 0.144909,0.468192 0.133251,0.448726 0.150373,0.450246 0.176853)),((0.719425 0.179933,0.778422 0.274563,0.76895 0.322197,0.791284 0.312445,0.791944 0.296253,0.799738 0.308754,0.959288 0.239088,0.958302 0.22776,0.745381 0.158712,0.719425 0.179933)),((0.701609 0.660841,0.666999 0.75257,0.681007 0.764449,0.701609 0.660841)),((0.594132 0.714429,0.606487 0.701251,0.594811 0.691349,0.594132 0.714429)),((0.224866 0.786223,0.382462 0.983231,0.466763 0.85994,0.47812 0.838165,0.39515 0.926659,0.476824 0.77908,0.50332 0.789847,0.525393 0.747525,0.505459 0.72734,0.547556 0.651273,0.482633 0.596213,0.577247 0.52647,0.570444 0.520834,0.600941 0.483052,0.603549 0.394417,0.517116 0.432156,0.563288 0.385417,0.492528 0.36544,0.577515 0.295956,0.550593 0.255888,0.452782 0.221035,0.459249 0.333709,0.441865 0.351136,0.370548 0.331001,0.385816 0.296593,0.394882 0.293488,0.387958 0.291767,0.423911 0.210747,0.392721 0.199633,0.310001 0.272391,0.236386 0.254095,0.304173 0.168082,0.296274 0.165267,0.207506 0.246917,0.0140798 0.198842,0.069792 0.24609,0.0159663 0.230894,0.0815688 0.362756,0.0156364 0.423401,0.0977468 0.395274,0.108341 0.416568,0.135246 0.382428,0.203132 0.359173,0.207309 0.362716,0.174164 0.39187,0.173365 0.391061,0.173401 0.392541,0.11983 0.439661,0.177364 0.555306,0.177972 0.580239,0.0906064 0.618386,0.127028 0.663916,0.0564116 0.721999,0.127196 0.664127,0.181673 0.732227,0.182236 0.755361,0.188638 0.740934,0.199131 0.754051,0.261029 0.691392,0.320648 0.715618,0.224866 0.786223),(0.216572 0.354569,0.27427 0.30382,0.323855 0.317819,0.216572 0.354569)),((0.224866 0.786223,0.199131 0.754051,0.013265 0.942202,0.224866 0.786223)),((0.598711 0.558841,0.547556 0.651273,0.566996 0.667759,0.59721 0.609827,0.598711 0.558841)),((0.598711 0.558841,0.604247 0.548838,0.59913 0.544599,0.598711 0.558841)),((0.604247 0.548838,0.621545 0.563169,0.680308 0.450499,0.643761 0.47744,0.604247 0.548838)),((0.643761 0.47744,0.668916 0.431986,0.656761 0.413896,0.600941 0.483052,0.60016 0.509579,0.643761 0.47744)))
MULTIPOLYGON(((0.663637 0.851798,0.60596 0.926301,0.651077 0.91496,0.663637 0.851798)),((0.696266 0.142785,0.611653 0.00706631,0.573697 0.0404517,0.625869 0.119956,0.696266 0.142785)),((0.315687 0.454629,0.297299 0.496067,0.328117 0.465171,0.315687 0.454629)),((0.211225 0.286021,0.236386 0.254095,0.207506 0.246917,0.175851 0.276034,0.211225 0.286021)),((0.211225 0.286021,0.173427 0.333981,0.203132 0.359173,0.216572 0.354569,0.207309 0.362716,0.315687 0.454629,0.370548 0.331001,0.323855 0.317819,0.385816 0.296593,0.387958 0.291767,0.310001 0.272391,0.27427 0.30382,0.211225 0.286021)),((0.175851 0.276034,0.069792 0.24609,0.14191 0.307253,0.175851 0.276034)),((0.14191 0.307253,0.0815688 0.362756,0.0977468 0.395274,0.135246 0.382428,0.173427 0.333981,0.14191 0.307253)),((0.684151 0.208773,0.603476 0.274731,0.607034 0.275999,0.605233 0.337207,0.634572 0.380871,0.710003 0.347935,0.727272 0.326541,0.717162 0.344809,0.76089 0.325716,0.684151 0.208773)),((0.450246 0.176853,0.425156 0.207942,0.423911 0.210747,0.452782 0.221035,0.450246 0.176853)),((0.527613 0.0809854,0.521709 0.086179,0.523067 0.0866194,0.527613 0.0809854)))

Second set of input:

MULTIPOLYGON(((0.573697 0.0404517,0.5677 0.0313133,0.527613 0.0809854,0.573697 0.0404517)),((0.663637 0.851798,0.711342 0.790176,0.681007 0.764449,0.663637 0.851798)),((0.328117 0.465171,0.348942 0.482832,0.492528 0.36544,0.441865 0.351136,0.328117 0.465171)),((0.59913 0.544599,0.60016 0.509579,0.577247 0.52647,0.59913 0.544599)),((0.780115 0.586441,0.779691 0.59685,0.748247 0.550053,0.740154 0.558685,0.710619 0.636962,0.961172 0.844534,0.780115 0.586441)),((0.791944 0.296253,0.796543 0.183435,0.778422 0.274563,0.791944 0.296253)),((0.76089 0.325716,0.766538 0.334324,0.76895 0.322197,0.76089 0.325716)),((0.36551 0.585627,0.420902 0.641717,0.482633 0.596213,0.413212 0.537338,0.36551 0.585627)),((0.36551 0.585627,0.305289 0.524648,0.289209 0.531669,0.301942 0.521258,0.291026 0.510204,0.297299 0.496067,0.287131 0.506261,0.174164 0.39187,0.173401 0.392541,0.177364 0.555306,0.187664 0.576007,0.177972 0.580239,0.178814 0.61485,0.142867 0.650888,0.127028 0.663916,0.127196 0.664127,0.178983 0.621787,0.181673 0.732227,0.188638 0.740934,0.226862 0.654796,0.241025 0.683264,0.261029 0.691392,0.36551 0.585627),(0.279648 0.535844,0.277112 0.541559,0.201344 0.603505,0.197613 0.596005,0.240627 0.552881,0.279648 0.535844)),((0.413212 0.537338,0.517116 0.432156,0.366654 0.497853,0.413212 0.537338)),((0.590866 0.825421,0.591197 0.814158,0.544737 0.767113,0.517876 0.795762,0.590866 0.825421)),((0.590866 0.825421,0.586751 0.965255,0.666999 0.75257,0.606487 0.701251,0.685935 0.616513,0.621545 0.563169,0.59721 0.609827,0.594811 0.691349,0.566996 0.667759,0.525393 0.747525,0.544737 0.767113,0.594132 0.714429,0.591197 0.814158,0.609997 0.833195,0.590866 0.825421)),((0.420902 0.641717,0.320648 0.715618,0.476824 0.77908,0.505459 0.72734,0.420902 0.641717)),((0.685935 0.616513,0.70696 0.633931,0.717016 0.583363,0.685935 0.616513)))
MULTIPOLYGON(((0.594132 0.714429,0.606487 0.701251,0.594811 0.691349,0.594132 0.714429)),((0.663637 0.851798,0.60596 0.926301,0.651077 0.91496,0.663637 0.851798)),((0.550593 0.255888,0.603476 0.274731,0.684151 0.208773,0.625869 0.119956,0.523067 0.0866194,0.476025 0.144909,0.550593 0.255888)),((0.550593 0.255888,0.452782 0.221035,0.459249 0.333709,0.441865 0.351136,0.370548 0.331001,0.315687 0.454629,0.207309 0.362716,0.174164 0.39187,0.173365 0.391061,0.173401 0.392541,0.11983 0.439661,0.177364 0.555306,0.177972 0.580239,0.0906064 0.618386,0.127028 0.663916,0.0564116 0.721999,0.127196 0.664127,0.181673 0.732227,0.182236 0.755361,0.188638 0.740934,0.199131 0.754051,0.261029 0.691392,0.320648 0.715618,0.224866 0.786223,0.382462 0.983231,0.466763 0.85994,0.47812 0.838165,0.39515 0.926659,0.476824 0.77908,0.50332 0.789847,0.525393 0.747525,0.505459 0.72734,0.547556 0.651273,0.482633 0.596213,0.577247 0.52647,0.570444 0.520834,0.600941 0.483052,0.603549 0.394417,0.517116 0.432156,0.563288 0.385417,0.492528 0.36544,0.577515 0.295956,0.550593 0.255888),(0.366654 0.497853,0.305289 0.524648,0.301942 0.521258,0.348942 0.482832,0.366654 0.497853),(0.287131 0.506261,0.291026 0.510204,0.279648 0.535844,0.289209 0.531669,0.277112 0.541559,0.226862 0.654796,0.201344 0.603505,0.178983 0.621787,0.178814 0.61485,0.197613 0.596005,0.187664 0.576007,0.240627 0.552881,0.287131 0.506261),(0.315687 0.454629,0.328117 0.465171,0.297299 0.496067,0.315687 0.454629)),((0.50332 0.789847,0.47812 0.838165,0.517876 0.795762,0.50332 0.789847)),((0.476025 0.144909,0.468192 0.133251,0.448726 0.150373,0.450246 0.176853,0.476025 0.144909)),((0.521709 0.086179,0.399861 0.0466657,0.304173 0.168082,0.392721 0.199633,0.448726 0.150373,0.445833 0.0999749,0.468192 0.133251,0.521709 0.086179)),((0.521709 0.086179,0.523067 0.0866194,0.527613 0.0809854,0.521709 0.086179)),((0.577515 0.295956,0.605233 0.337207,0.607034 0.275999,0.603476 0.274731,0.577515 0.295956)),((0.304173 0.168082,0.296274 0.165267,0.207506 0.246917,0.236386 0.254095,0.304173 0.168082)),((0.392721 0.199633,0.310001 0.272391,0.387958 0.291767,0.423911 0.210747,0.392721 0.199633)),((0.108341 0.416568,0.0230624 0.524775,0.11983 0.439661,0.108341 0.416568)),((0.108341 0.416568,0.135246 0.382428,0.0977468 0.395274,0.108341 0.416568)),((0.668916 0.431986,0.729259 0.521793,0.766538 0.334324,0.788997 0.368549,0.791284 0.312445,0.76895 0.322197,0.778422 0.274563,0.719425 0.179933,0.684151 0.208773,0.76089 0.325716,0.717162 0.344809,0.668916 0.431986)),((0.668916 0.431986,0.656761 0.413896,0.600941 0.483052,0.60016 0.509579,0.643761 0.47744,0.668916 0.431986)),((0.603549 0.394417,0.634572 0.380871,0.605233 0.337207,0.603549 0.394417)),((0.625869 0.119956,0.696266 0.142785,0.611653 0.00706631,0.573697 0.0404517,0.625869 0.119956)),((0.656761 0.413896,0.710003 0.347935,0.634572 0.380871,0.656761 0.413896)),((0.696266 0.142785,0.719425 0.179933,0.745381 0.158712,0.696266 0.142785)),((0.701609 0.660841,0.710619 0.636962,0.70696 0.633931,0.701609 0.660841)),((0.701609 0.660841,0.666999 0.75257,0.681007 0.764449,0.701609 0.660841)),((0.788997 0.368549,0.783115 0.512864,0.842285 0.449754,0.788997 0.368549)),((0.959288 0.239088,0.799738 0.308754,0.992212 0.617482,0.959288 0.239088)),((0.959288 0.239088,0.973756 0.232771,0.958302 0.22776,0.959288 0.239088)),((0.717162 0.344809,0.727272 0.326541,0.710003 0.347935,0.717162 0.344809)),((0.783115 0.512864,0.751874 0.546184,0.780115 0.586441,0.783115 0.512864)),((0.745381 0.158712,0.958302 0.22776,0.938553 0.000778765,0.745381 0.158712)),((0.799738 0.308754,0.791944 0.296253,0.791284 0.312445,0.799738 0.308754)),((0.74515 0.545443,0.729259 0.521793,0.717016 0.583363,0.740154 0.558685,0.74515 0.545443)),((0.74515 0.545443,0.748247 0.550053,0.751874 0.546184,0.74732 0.539692,0.74515 0.545443)),((0.310001 0.272391,0.236386 0.254095,0.211225 0.286021,0.27427 0.30382,0.310001 0.272391)),((0.323855 0.317819,0.370548 0.331001,0.385816 0.296593,0.323855 0.317819)),((0.323855 0.317819,0.27427 0.30382,0.216572 0.354569,0.323855 0.317819)),((0.387958 0.291767,0.385816 0.296593,0.394882 0.293488,0.387958 0.291767)),((0.175851 0.276034,0.14191 0.307253,0.173427 0.333981,0.211225 0.286021,0.175851 0.276034)),((0.175851 0.276034,0.207506 0.246917,0.0140798 0.198842,0.069792 0.24609,0.175851 0.276034)),((0.173427 0.333981,0.135246 0.382428,0.203132 0.359173,0.173427 0.333981)),((0.203132 0.359173,0.207309 0.362716,0.216572 0.354569,0.203132 0.359173)),((0.069792 0.24609,0.0159663 0.230894,0.0815688 0.362756,0.14191 0.307253,0.069792 0.24609)),((0.0815688 0.362756,0.0156364 0.423401,0.0977468 0.395274,0.0815688 0.362756)),((0.224866 0.786223,0.199131 0.754051,0.013265 0.942202,0.224866 0.786223)),((0.643761 0.47744,0.604247 0.548838,0.621545 0.563169,0.680308 0.450499,0.643761 0.47744)),((0.604247 0.548838,0.59913 0.544599,0.598711 0.558841,0.604247 0.548838)),((0.452782 0.221035,0.450246 0.176853,0.425156 0.207942,0.423911 0.210747,0.452782 0.221035)),((0.547556 0.651273,0.566996 0.667759,0.59721 0.609827,0.598711 0.558841,0.547556 0.651273)))

[kleunen]

Excellent. So two additional test cases to make sure regression does not occur?

[barendgehrels]

Excellent. So two additional test cases to make sure regression does not occur?

Indeed. The related PR #889 can be merged first. Then (or actually I'm starting already locally) I can try to fix that in the branch where I've the traverse fix, and it should (ideally) not regress (if I can manage)

[kleunen]

Take your time. Next week i am away on summer break. I wont be able to test for a while.

[barendgehrels]

Take your time. Next week i am away on summer break. I wont be able to test for a while.

Thanks!

It seems to be a one line fix which is already done 🙂
It fixes these extra cases (and your whole sample), and keeps the original fix valid, and all other cases too.

Do you have more testsuites? Can you verify the new behaviour? (no hurry)

Have a nice break anyway!

[kleunen]

I think i can try if this works before my summer break. Generating more test cases might be possible. But this will surely be after my summer break.

[kleunen]

If all goes well i can also try to merge back into tilemaker and see if it works well. If i do a planet conversion you really have a test suite of 10.000s of polygons

[barendgehrels]

That is more than enough! After break is fine of course.

For the first set, let me know if it works / if you agree with merging the PR (#887)

[kleunen]

For the first set, let me know if it works / if you agree with merging the PR (#887)

There is one additional case I would like to try before i can answer this question. And this requires me to change some things to my geometry correct. But I think i can manage to do this within coming days. I also would like to check the existing test cases in geometry correct, so, please be patient.

[barendgehrels]

Sure, all right and I’ll be patient! Thanks for all your efforts!

[kleunen]

I have the following additional test-case which was valid before and generates invalid polygon with #887:
https://wandbox.org/permlink/gr8EFMV1OZbu3eZK

I did some more testing, and changed the test-case. The other test-case i found, had also errors in the old boost, but this one only has one invalid sym_difference:

53 validity:  1: true 2: true i: true u: true a: false b: true s: false
Is valid: false

[barendgehrels]

I have the following additional test-case which was valid before and generates invalid polygon with #887:
https://wandbox.org/permlink/gr8EFMV1OZbu3eZK

I did some more testing, and changed the test-case. The other test-case i found, had also errors in the old boost, but this one only has one invalid sym_difference:

53 validity:  1: true 2: true i: true u: true a: false b: true s: false
Is valid: false

Thanks again. I will add this testcase. And I analyzed it already. It is not easy to fix. Not only because it's huge, the specific conditions for this one, why it should be kept isolated and all others not, are not easy to determine. This requires either more conditions or even another approach.

Therefore, and also because it already had errors before as you mention, it is not a regression, and I propose to merge the current approach. I will add a specific ticket for this one later. I prefer to first continue with the effort I was working on (finish remove scaling) and have that in next Boost version, then concentrate on this complex and (I think) uncommon case.

@awulkiew @vissarion agree? If yes please approve #887 (Adam did already) and I will merge it and create a small PR for this testcase only after that.

[kleunen]

Are you sure? Because this is indeed an uncommon case. But the case which triggered this bug report was also uncommon. and the behaviour of previous version was working well in many cases it seems.

[barendgehrels]

My reasoning is that the nearly trivial case (which Adam extracted) might be quite common and should be supported. But revising traversal/switch might take me several weeks again (I work only ~4 hours/week on this project) and we really want to release the version in 1.78 where rescaling is removed (that is my main goal for already more than a year). Therefore I consider that more important than fixing this huge, complex, difficult and uncommon case... (though I keep it on my list and want to fix that afterwards, of course)