如何确定A->B线是否位于多边形内而不碰到任何墙壁？

Question

好的，系好安全带。

给定由点 A 和 B 以及多边形 C 构造的线串，我如何确保 A->B 线不与 C 中的任何墙壁相交或位于 C 内部？

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/segment.hpp>

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

typedef bgm::d2::point_xy<double> Point;
typedef bgm::polygon<Point> Polygon;
typedef boost::geometry::model::segment<Point> Segment;
Polygon wall;
Polygon passage;
boost::geometry::model::linestring<Point> AB{start, end}
bool isPassable = false;
bool intersecting = bg::intersects(AB, wall);
if (intersecting) {
    for (int i = 0; i < passage.outer().size(); i += 2) {
      Point p1 = passage.outer()[i];
      Point p2 = passage.outer()[i + 1];
      Segment passageSegment(p1, p2);
      Segment testSegment(start, end);
      if (bg::intersects(passageSegment, testSegment)) {
        isPassable = true;
        break;
      }
    }
} else {
    isPassable = bg::relate(AB, wall, boost::geometry::de9im::mask("T*F**F***"));
}

由于隐私原因，我无法显示完整的代码，但这无论如何都是感兴趣的点。

我们的多边形有问题

POLYGON((2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 5.5,7.5 5.5,7.5 2,2 2)) 

段落

Passage: POINT(2.5 3.5) POINT(3 3.5)
Passage: POINT(4.25 3.5) POINT(4.75 3.5)
Passage: POINT(4 2.5) POINT(4 3)
Passage: POINT(5 4) POINT(5 5)

看起来像这样：

绿线在哪里：

POINT(2.5 3.25) POINT(3 3.625)

运行两个相关函数后

see if this line is related to any walls, if it is not related, check if it is breaching any holes in passages

，这实际上是有效的。对于绿线，我可以获得

true

。问题开始于：

这条绿线。正如你所看到的，它位于多边形内。因此，在第一个

relate

到墙上时，它应该返回 true。但由于线路和墙壁/通道之间没有关系，因此即使不应该返回，也会返回

false

。我该如何处理这个问题？

在官方 Boost 文档中

https://live.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/geometry/reference/algorithms/relate.html

我可以看到

这个方法其实是用来做我想要的东西的。查看兴趣点是否位于多边形内。但是，呃，我们到了。

感谢您的帮助。

1.30 am 更新：要去睡觉了，所以无法很快回复任何解决方案。感谢评论中的任何尝试。非常感谢在我醒来之前收到的任何解决方案。

Answer 1

您输入的多边形无效：

Polygon wall;
bg::read_wkt( //
    "POLYGON((2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 "
    "5.5,7.5 5.5,7.5 2,2 2)) ",
    wall);

if (std::string reason; !bg::is_valid(wall, reason)) {
    std::cerr << "Invalid polygon: " << reason << "\n";
    return 1;
}

打印在Coliru上直播

Invalid polygon: Geometry has invalid self-intersections. A self-intersection point was found at (2, 3.5); method: t; operations: i/u; segment IDs {source, multi, ring, segment}: {0, -1, -1, 0}/{0, -1, -1, 3}

您可以尝试使用

bg::correct

自动修复它

for (std::string reason; !bg::is_valid(wall, reason); bg::correct(wall)) {
    std::cerr << "Invalid polygon: " << reason << "\n";
}

但它对这些问题不起作用。我强烈怀疑你真的希望它是一个（多）线串，甚至只是一个段列表。

通过这些修复，我得到：

住在Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/multi_linestring.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/segment.hpp>
namespace bg  = boost::geometry;
namespace bgm = boost::geometry::model;

using Point    = bgm::d2::point_xy<double>;
using Polygon  = bgm::polygon<Point>;
using Segment  = boost::geometry::model::segment<Point>;
using Segments = std::vector<Segment>;
using String   = bgm::linestring<Point>;
using MString  = bgm::multi_linestring<String>;

int main() {
    String wall
        // {{2, 2}, {2, 3.5}, {4, 3.5}, {4, 2},   {2, 3.5},   {2, 5.5}, {5, 5.5},
        // {5, 3.5}, {4, 2}, {4, 3.5}, {5, 3.5}, {5, 5.5}, {7.5, 5.5}, {7.5, 2}, {2, 2}}
        //
        ;

    bg::read_wkt(
        "LINESTRING(2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 "
        "5.5,7.5 5.5,7.5 2,2 2)",
        wall);

    std::cout << "Wall is " << bg::wkt(wall) << std::endl;
    for (std::string reason; !bg::is_valid(wall, reason); bg::correct(wall)) {
        std::cerr << "Invalid wall: " << reason << "\n";
    }

    Segment AB({2.5, 3.25}, {3, 3.625});

    Segments passages{
        {{2.5, 3.5}, {3, 3.5}},
        {{4.25, 3.5}, {4.75, 3.5}},
        {{4, 2.5}, {4, 3}},
        {{5, 4}, {5, 5}},
    };

    bool isPassable = false;
    if (/*bool intersecting =*/bg::intersects(AB, wall)) {
        for (auto& passage : passages) {
            if (bg::intersects(passage, AB)) {
                isPassable = true;
                break;
            }
        }
    } else {
        bgm::linestring<Point> abls({AB.first, AB.second});
        isPassable = bg::relate(abls, wall, boost::geometry::de9im::mask("T*F**F***"));
    }

    std::cout << "Is passable: " << std::boolalpha << isPassable << std::endl;
}

Wall is LINESTRING(2 2,2 3.5,4 3.5,4 2,2 3.5,2 5.5,5 5.5,5 3.5,4 2,4 3.5,5 3.5,5 5.5,7.5 5.5,7.5 2,2 2)
Is passable: true

我真的建议通过实际删除原始“墙”字符串中的段落来进一步简化它。这对于确保您的检查正确尤其重要。毕竟，当存在多个交叉点时，其中一个在段落中实际上不会改变任何内容，但您的代码假设始终只有一个交叉点。