我有一个由墙壁描述为迷宫线的迷宫（没有给定的顺序） . 鉴于一点，我需要确定它是否在迷宫内或否 . 一切都在Cartezian平面（没有离散化） .
我的想法是将问题转化如下：
给定平面中的一些线段，找到在给定线段的 endpoints 中具有顶点的所有多边形，并且使用位于线段上的边（您可以在下面的图像中看到，您不能假设边将形成线段的子集） .
然后检查：如果一个点只在一个多边形内，那么它在迷宫内，否则没有 .
我想到的解决方案是：哈希 endpoints 和线交叉，然后寻找循环 .
还有其他建议吗？谢谢！
（忽略图像中的颜色）
1 回答
找到边界（外部）多边形就足够了 . 这可以通过在边界上找到一个点而不是从一个方向上的段遍历该点来完成 . 如果有更多的可能性去选择“外部” . 算法可以描述：
第一个点可以找到具有最高Y坐标的点，如果有更多像这样的点，那么它们中的X最低 . 我们可以称之为左上角 .
第一个方向：第一个点连接到其他点，并且该点具有<= Y坐标，这意味着连接段低于第一个点 . 选择最正确的 .
下一个方向：某个（进入）段到达当前点，下一个要进入的段在正方向上最远，与进入段的顺时针方向相同 .