Как получить многоугольник из boost :: geometry :: model :: polygon?

Вы можете легко построить кольцо, моделирующее ваш ожидаемый слабый простой многоугольник. Первый:

Предостережение

Однако обратите внимание, что результат недействителен для дальнейшего использования с алгоритмами библиотеки Boost Geometry.

Возьмем ваш буквальный пример:

std::string reason;
poly expected;
bg::read_wkt("POLYGON((0 0, 0 4, 2 4, 2 2, 6 2, 6 6, 2 6, 2 4, 0 4, 0 8, 8 8, 8 0, 0 0))", expected);
bool ok = bg::is_valid(expected, reason);
std::cout << "Expected: " << bg::dsv(expected) << (ok?" valid":" invalid: '" + reason + "'") << "\n";

Печать

Ожидается: (((0, 0), (0, 4), (2, 4), (2, 2), (6, 2), (6, 6), (2, 6), (2, 4) ), (0, 4), (0, 8), (8, 8), (8, 0), (0, 0))) недопустимо: 'Геометрия имеет недопустимые самопересечения. Точка самопересечения была найдена в (0, 4); метод: t; операции: х / у; идентификаторы сегментов {источник, мульти, кольцо, сегмент}: {0, -1, -1, 0} / {0, -1, -1, 7} '

Реализация алгоритма

После этого вот простой алгоритм построения простого слабого многоугольника из заданного многоугольника:

ring weak_simple_ring(poly& p) {
    ring r = p.outer();

    for (auto& i: p.inners()) {
        auto last = r.back();
        r.insert(r.end(), i.rbegin(), i.rend());
        r.insert(r.end(), last);
    }

    return r;
}

Единственный более тонкий момент - это изменить направление (CW / CCW) внутренних колец, чтобы оно соответствовало направлению внешнего кольца.

Алгоритм не пытается найти точку разреза на внутреннем кольце, что, вероятно, также означает, что он не будет хорошо работать в общем случае с несколькими внутренними кольцами.

ДЕМО

Вот полная живая демонстрация

Live On Coliru

Если ввод -

bg::read_wkt("POLYGON((0 0,0 10,10 10,10 0,0 0))", a);
bg::read_wkt("POLYGON((2 2, 2 6, 6 6, 6 2, 2 2))", b);

Преобразование

std::vector<poly> output;
bg::difference(a, b, output);

for (auto& p : output) {
    ring r = weak_simple_ring(p);
    bg::convert(r, p);
}

Результат станет .

Более сложный образец

Представьте, когда у b была дыра:

bg::read_wkt("POLYGON((0 0,0 10,10 10,10 0,0 0))", a);
bg::read_wkt("POLYGON((2 2, 2 6, 6 6, 6 2, 2 2)(3 3, 5 3, 5 5, 3 5, 3 3))", b);

Результат с тем же кодом становится .

Это старый ответ. После редактирования вопроса я опубликовал простую реализацию алгоритма, подходящего для данного образца

Уже есть.

Если вы имеете в виду «простой» многоугольник без дырок, то внешнее кольцо - это все, что вам нужно. Просто выбросьте внутренние кольца.

Однако в самом общем случае вы можете получить несколько полностью разобщенных многоугольников, поэтому результат представляет собой набор многоугольников. Вам также нужно будет рассмотреть эту возможность (необязательно объединение различных результирующих полигонов в один и отказ от внутренних колец, если вы этого хотите, функционально).

Образец:

bg::read_wkt("POLYGON((0 0,0 10,10 10,10 0,0 0))", a);
bg::read_wkt("POLYGON((2 -2,2 12,5 12,5 -2,2 -2))", b);

Здесь b разрезает a на две отдельные части. Итак, вы должны быть готовы обрабатывать несколько разрозненных выходных полигонов:

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/io/io.hpp>
#include <iostream>
#include <fstream>

namespace bg = boost::geometry;
using pt   = bg::model::d2::point_xy<int>;
using poly = bg::model::polygon<pt>;

int main() {
    poly a, b;
    bg::read_wkt("POLYGON((0 0,0 10,10 10,10 0,0 0))", a);
    bg::read_wkt("POLYGON((2 -2,2 12,5 12,5 -2,2 -2))", b);

    std::cout << bg::dsv(a) << "\n";
    std::cout << bg::dsv(b) << "\n";

    {
        std::ofstream svg("/tmp/input.svg");
        boost::geometry::svg_mapper<pt> mapper(svg, 400, 400);
        mapper.add(a);
        mapper.add(b);

        mapper.map(a, "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:2");
        mapper.map(b, "fill-opacity:0.5;fill:rgb(204,153,0);stroke:rgb(202,153,0);stroke-width:2");
    }

    std::vector<poly> output;
    bg::difference(a, b, output);
    for (auto& p : output)
        std::cout << "\n\t" << bg::dsv(p);

    {
        std::ofstream svg("/tmp/output.svg");
        boost::geometry::svg_mapper<pt> mapper(svg, 400, 400);
        assert(output.size() == 2);
        mapper.add(output[0]);
        mapper.add(output[1]);
        mapper.add(b);

        mapper.map(output[0], "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:2");
        mapper.map(output[1], "fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-width:2");
        mapper.map(b, "fill-opacity:0.15;fill:rgb(153,153,153);stroke-width:0");
    }
}

Печать:

(((0, 0), (0, 10), (10, 10), (10, 0), (0, 0)))
(((2, -2), (2, 12), (5, 12), (5, -2), (2, -2)))

    (((5, 10), (10, 10), (10, 0), (5, 0), (5, 10)))
    (((2, 10), (2, 0), (0, 0), (0, 10), (2, 10)))

Визуализированные SVG: