invalid result of difference

[barendgehrels]

Discussed in #1188

^{Originally posted by fililili August 21, 2023}

#include <iostream>
#include <vector>
#include <cassert>

#include <boost/geometry.hpp>

int main()
{
    using polygon = boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<int> >;
    using multi_polygon = boost::geometry::model::multi_polygon<polygon>;

    multi_polygon one, two;

    boost::geometry::read_wkt(
        "MULTIPOLYGON(((0 0, 0 2, 5 1, 5 0, 0 0)))", one);
    assert(boost::geometry::is_valid(one));

    boost::geometry::read_wkt(
        "MULTIPOLYGON(((3 1, 1 2, 5 1, 3 1)), ((0 0, 0 2, 5 0, 0 0)))", two);
    assert(boost::geometry::is_valid(two));

    multi_polygon output;
    boost::geometry::difference(one, two, output);
    assert(boost::geometry::is_valid(output));

    std::cout << "result:" << std::endl;
    std::cout << boost::geometry::wkt(output) << std::endl;
    
    return 0;
}

Here is an exmple, assert(boost::geometry::is_valid(output)); will failed.
Do we have a well designed snap rouding algorithm? I can find some things in CGAL (https://doc.cgal.org/latest/Snap_rounding_2/index.html).
https://godbolt.org/z/dProo1bf7