如何从boost::geometry::model::polygon获取多边形？

Question

我正在尝试使用boost::geometry::difference计算两个多边形的差异，其中boost::geometry::model::polygon表示我的多边形。

如果第一个多边形包含第二个多边形，则操作的结果是一个单一的boost::geometry::model::polygon，内部和外部环都填充了源多边形的坐标。

我如何从boost::geometry::model::polygon中获取一个多边形（在基础几何意义上）？ 澄清： 在基础几何学中，多边形是由有限条直线段组成的平面图形，这些直线段构成了一个封闭的链或回路。 boost::geometry::model::polygon的外环是一个多边形，内环也是多边形。作为整体，boost::geometry::model::polygon不是一个多边形。

所以，我的问题是：如何将 boost::geometry::model::polygon 转换为一个“普通”的多边形（具有单一的直线段链），它代表了平面上相同的区域。

这是我想实现的目标：

polygon1   = (0,0), (0,8), (8,8), (8,0), (0,0)
polygon2   = (2,2), (2,6), (6,6), (6,2), (2,2)

绿色/土黄色的多边形1和2：

difference = (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)

预期的灰色差异：

我知道同样的boost :: geometry :: model :: polygon具有内部环，可以用无数个不同的正常多边形表示。我不在乎我得到哪一个。

- empty'void

---

你能否澄清你的问题？你已经有了一个表示多边形的对象，你想获得什么其他形式的多边形？你真正想要实现什么？也许你想绘制这个多边形？ - Marko Popovic

关于您的编辑：“我知道同样的boost :: geometry :: model :: polygon具有内环，可以用无限多个不同的普通多边形表示。我不在乎我得到哪一个。”-看起来这与您的真实需求完全相反：您似乎非常在意。这是因为一个带有一个或多个内环的外环不可能以另一种方式表示为“普通多边形¹”。（¹您的定义：“（具有一条直线段链）”） - sehe

正如您在我的示例中所看到的，为了表示两个多边形之间的差异，我引入了一条直线段(0,4)-(2,4)，从而创建了一个弱简单多边形，显然，任何连接内部和外部边界的其他直线段都可以代替它，因此会导致无限多的解决方案。而这个定义不是“我的”，而是来自Wikipedia。 - empty'void

我认为我理解了你的方法。我不会说你期望的结果在拓扑/数学上是等价的，但我确实看到它们可以被视为“实用上”等价。我很快会发布一个自定义算法的尝试。 - sehe

谢谢您的说明，不过看起来polygon1被渲染成了一个边长为10而不是8的正方形。 - empty'void

这可能会引起兴趣 https://github.com/ivanfratric/polypartition/blob/master/src/polypartition.cpp#L174 - Jens Åkerblom

Answer 1

你可以轻松构建一个模拟你期望的“弱简单多边形”的环。首先：

注意

请注意，该结果无法与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；操作：x/u；段ID{源、多、环、段}：{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;
}

唯一需要注意的是反转内环的方向（顺时针/逆时针），使其与外环匹配。

该算法并不试图找到内环的切割点，这可能也意味着它对于具有多个内环的通用情况不起作用。

演示

这是一个完整的实时演示

在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);

相同的代码输出为 。

- sehe

---

是的，我已经有一个类似的解决方案了。不幸的是，它并不通用：在选定的顶点之间可能会有其他“空洞”，或者顶点的顺序可能不同（请参见修改后的演示）。我知道可以通过搜索最近的顶点对并逐个集成一个内环来解决问题，但我希望有一个更高效的算法。 - empty'void

Answer 2

这是旧答案。在问题进行编辑后，我发布了一个适合给定样本的算法的简单实现

它已经完成了。

如果你的意思是“简单”的非孔多边形，那么外环就是你想要的。只需丢弃内部环。

然而，在最一般的情况下，你可能会得到多个完全不相交的多边形，这就是输出是多边形集合的原因。你也必须考虑这种可能性（可选地将不同的结果多边形合并成一个，并丢弃内部环，如果这是你所期望的功能）。

一个示例：

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切成两个独立的部分。因此，您必须准备好处理多个不相交的输出多边形：

在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)))

SVGs渲染：

- sehe

---

我使用 boost::geometry::difference 的整个目的是排除第二个多边形所代表的区域，因此对我来说没有丢弃内环的必要。是的，我知道结果可能是多边形列表，我完全可以接受这种结果。 - empty'void

我只能说，也许你的问题应该更清晰一些（就像我的示例一样清晰）。这将避免浪费很多时间。 - sehe

抱歉，我认为“基本几何意义上的多边形”已经足够清楚了。 - empty'void