Is there a function which can decouple self-intersect polygon?

Question

using namespace boost::polygon;

polygon_data<int> poly;
std::vector<point_data<int>> points;
points.push_back(point_data<int>(10, 6));
points.push_back(point_data<int>(15, 6));
points.push_back(point_data<int>(17, 9));
points.push_back(point_data<int>(13, 9));
points.push_back(point_data<int>(15, 6));
points.push_back(point_data<int>(20, 6));
points.push_back(point_data<int>(20, 11));
points.push_back(point_data<int>(10, 11));
set_points(poly, points.begin(), points.end());

Is there a function can decouple "poly" in boost?

I mean I expect to get a polygon with a hole.

Answer 1

Not that I know of. Boost Geometry does, however, but it obviously cannot fix all inputs. Here's a simple test-bed:

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/polygon.hpp>
namespace bg = boost::geometry;

using point_t   = bg::model::d2::point_xy<int>;
using polygon_t = bg::model::polygon<point_t>;

void do_test(polygon_t p) {
    std::set<std::string> reasons;
    for (std::string reason; !bg::is_valid(p, reason);) {
        if (reasons.insert(reason).second) {
            std::cout << "Correcting " << bg::wkt(p) << ": " << reason << "\n";
            bg::correct(p);
        } else {
            std::cout << "Corrected, but still invalid: " << reason << "\n";
            break;
        }
    }
    std::cout << " === Result: " << bg::wkt(p) << "\n";
}

Let me show you various ways to construct your "polygon" (which sadly isn't) and run that:

Live On Coliru

    do_test(polygon_t{
        {{10, 6}, {15, 6}, {17, 9}, {13, 9}, {15, 6}, {20, 6}, {20, 11}, {10, 11}}, // outer ring
        // {{12, 7}, {13, 7}, {13, 8}, {12, 8}, {12, 7}},                             // inner ring
    });

    {
        polygon_t poly;
        std::vector<point_t> points = {{10, 6}, {15, 6}, {17, 9},  {13, 9},
                                       {15, 6}, {20, 6}, {20, 11}, {10, 11}};
        bg::assign_points(poly, points);
        do_test(poly);
    }

    // or even:
    {
        auto constexpr wkt = "POLYGON((10 6, 15 6, 17 9, 13 9, 15 6, 20 6, 20 11, 10 11))";
        polygon_t poly;
        bg::read_wkt(wkt, poly);
        do_test(poly);
    }

As you can see all three have the exact same output:

Correcting POLYGON((10 6,15 6,17 9,13 9,15 6,20 6,20 11,10 11,10 6)): Geometry is defined as closed but is open
Correcting POLYGON((10 6,10 11,20 11,20 6,15 6,13 9,17 9,15 6,10 6)): Geometry has invalid self-intersections. A self-intersection point was found at (15, 6); method: t; operations: i/u; segment IDs {source, multi, ring, segment}: {0, -1, -1, 3}/{0, -1, -1, 6}
Corrected, but still invalid: Geometry has invalid self-intersections. A self-intersection point was found at (15, 6); method: t; operations: i/u; segment IDs {source, multi, ring, segment}: {0, -1, -1, 3}/{0, -1, -1, 6}
 === Result: POLYGON((10 6,10 11,20 11,20 6,15 6,13 9,17 9,15 6,10 6))

The library was able to see that the polygon wasn't closed. Sadly, the intersection at (15, 6) could not be algorithmically fixed.

Hints

I suspect that the inner shape should perhaps be a hole in the polygon?

That would result in:

// now do it with the rectangle as the outer ring, and the triangle hole as an inner ring:
std::vector<point_t> outer = {{10, 6}, {20, 6}, {20, 11}, {10, 11}, {10, 6}};
std::vector<point_t> inner = {{15, 6}, {17, 9}, {13, 9}, {15, 6}};
do_test({{{10, 6}, {20, 6}, {20, 11}, {10, 11}, {10, 6}}});
do_test({{{15, 6}, {17, 9}, {13, 9}, {15, 6}}});

// or in a single statement:
do_test(polygon_t{{{10, 6}, {20, 6}, {20, 11}, {10, 11}, {10, 6}}, // outer ring
                  {
                      // inner rings
                      {{15, 6}, {17, 9}, {13, 9}, {15, 6}, {15, 6}},
                  }});

// the wkt is:
// POLYGON((10 6,20 6,20 11,10 11,10 6),(15 6,17 9,13 9,15 6,15 6))

Which is valid except for the orientation, which Boost will happily fix:

Live On Coliru

Correcting POLYGON((10 6,20 6,20 11,10 11,10 6)): Geometry has wrong orientation

 === Result: POLYGON((10 6,10 11,20 11,20 6,10 6))


Correcting POLYGON((15 6,17 9,13 9,15 6)): Geometry has wrong orientation

 === Result: POLYGON((15 6,13 9,17 9,15 6))


Correcting POLYGON((10 6,20 6,20 11,10 11,10 6),(15 6,17 9,13 9,15 6,15 6)): Geometry has wrong orientation

 === Result: POLYGON((10 6,10 11,20 11,20 6,10 6),(15 6,17 9,13 9,15 6,15 6))

Note that the orientation of inner rings is opposite to that of the outer ring

Fully corrected code for this example would be:

// the rectangle with a triangle hole:
do_test(polygon_t{{{10, 6}, {10, 11}, {20, 11}, {20, 6}, {10, 6}},
                  {
                      {{15, 6}, {17, 9}, {13, 9}, {15, 6}, {15, 6}},
                  }});

Other Hints?

If you're not actually dealing with polygons, but free linesegments/multi-lines, see e.g. the approaches here: How to determine if A->B line resides in the polygon without hitting any walls?