Sym difference may generate polygon with disconnected interior

[kleunen]

Please see this example:
https://wandbox.org/permlink/Ib8ZrLmUlRI8UZEU

#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()
{
    multi_polygon_t a;
    multi_polygon_t b;
    multi_polygon_t c;
    
    boost::geometry::read_wkt("MULTIPOLYGON(((70 50,70 10,10 10,10 70,50 70,50 90,70 90,70 70,90 70,90 50,70 50)))", a);
    boost::geometry::read_wkt("MULTIPOLYGON(((50 50,50 70,70 70,70 50,50 50)))", b);
    boost::geometry::read_wkt("MULTIPOLYGON(((50 50,50 30,30 30,30 50,50 50)))", c);
    
    multi_polygon_t result;
    boost::geometry::sym_difference(b, c, result);
    std::cout << boost::geometry::wkt(result) << std::endl;
    
    multi_polygon_t result_2;
    boost::geometry::sym_difference(result, a, result_2);
    
    std::string message;
    if(!boost::geometry::is_valid(result_2, message))
        std::cout << "Geometry is not valid: " << message << std::endl;
    
    std::cout << boost::geometry::wkt(result_2) << std::endl;
    return 0;
}

Expected output is a valid polygon, output is:
Geometry is not valid: Geometry has disconnected interior
MULTIPOLYGON(((50 70,50 90,70 90,70 70,90 70,90 50,70 50,70 10,10 10,10 70,50 70),(50 70,50 50,70 50,70 70,50 70),(50 50,30 50,30 30,50 30,50 50)))

[awulkiew]

Thanks! I confirm this is a bug.

Reduced issue is that the result of difference():

multi_polygon_t a, b, c;
bg::read_wkt("MULTIPOLYGON(((70 50,70 10,10 10,10 70,50 70,50 90,70 90,70 70,90 70,90 50,70 50)))", a);
bg::read_wkt("MULTIPOLYGON(((50 50,50 70,70 70,70 50,50 50)),((50 50,50 30,30 30,30 50,50 50)))", b);
bg::difference(a, b, c);

is a single polygon with two holes while it should've been 3 separate polygons.

[barendgehrels]

I agree with the fact that it is a bug. I remember that some polygons can have two valid representations, but probably not this one.

http://www.gdmc.nl/publications/2004/Invalid_Valid_Clean_Polygons.pdf
This is an (old) article describing validity in the OGC context. But maybe the rules are a bit stricter in the meantime. I like this part of the article any point inside or on the boundary of the polygon can be reached through the interior of the polygon from any other point inside the polygon and that rule is not fulfilled here.

I'll assign it to myself but I'm not sure how to fix it yet.

(EDITED) This is generated with difference, but most probably it will be a problem with the overlay itself, be it intersection, union or difference, because they are implemented using the same underlying traversals.

The generation with difference is wrong, but with intersection and union (resulting in the same spatial geometry) is fine. This will make it (hopefully) a bit easier to fix, somewhere a decision should be the other way round. To be continued.

[barendgehrels]

Reduced issue is that the result of difference():

Thanks! Adding this testcase

[barendgehrels]

I've a working solution concept and will change it a bit, test it more, and create a PR next week

[barendgehrels]

I've a working solution concept and will change it a bit, test it more, and create a PR next week

In review: #887

[kleunen]

Maybe bit unrelated question, but, how can I check out boost geometry only ?
How do I build against boost geometry from git and keep the rest of normal boost ?

[awulkiew]

@kleunen https://github.com/boostorg/wiki/wiki/Getting-Started%3A-Overview

[barendgehrels]

Maybe bit unrelated question, but, how can I check out boost geometry only ?
How do I build against boost geometry from git and keep the rest of normal boost ?

See link Adam for the official way.
Getting Boost.Geometry from git and making a symbolic link (instead of the shipped geometry) should also work.