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

Question

我正在尝试使用 boost::geometry::difference 和代表我的多边形的 boost::geometry::model::polygon 来计算两个多边形的差异.

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

如何从 boost::geometry::model::polygon 获取多边形 ( in the elementary geometry sense)？

澄清:

In elementary geometry, a polygon is a plane figure that is bounded by a finite chain of straight line segments closing in a loop to form a closed chain or circuit.

boost::geometry::model::polygon 的外圈是多边形，内圈也是多边形。作为一个整体，boost::geometry::model::polygon 不是一个多边形。

所以，我要问的是:如何将 boost::geometry::model::polygon 转换为 normal 多边形(具有单条直线链段)，表示平面上的相同区域。

这是我要实现的目标:

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

绿色/oker 的多边形 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)

预期的灰色差异:

我知 Prop 有内环的相同 boost::geometry::model::polygon 可以由无限多个不同的法线 多边形表示。我不在乎得到哪一个。

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";

打印

Expected: (((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))) invalid: 'Geometry has invalid self-intersections. A self-intersection point was found at (0, 4); method: t; operations: x/u; segment IDs {source, multi, ring, segment}: {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);

相同代码的输出变为