时间戳

首页 > 解决方案 > 确定多边形顶点之间的线段是否为“内部”多边形

algorithm - 确定多边形顶点之间的线段是否为“内部”多边形

问题描述

我正在尝试找到一种有效的算法，该算法可以检查简单（编辑：simple concave）多边形中两个顶点之间的线是否包含位于多边形域之外的点。我能找到的最接近的问题是这个：https ://stackoverflow.com/a/36378838/12135804

但我不确定答案是否完全正确。可能是，在这种情况下，如果有人可以澄清那将是很好的。

基本思想如下图所示： 在此处输入图像描述

我希望红线失败，绿线成功。我知道不能天真地测试中点，因为这在每种情况下都不起作用，但是在多边形域外的线上找到任何点都应该取消它的资格。

我感谢任何和所有的帮助！

编辑：忘记包含数学堆栈交换的交叉链接： https ://math.stackexchange.com/q/4040059/892519

标签： algorithmgeometrypolygoncomputational-geometryline-segment

解决方案

经过大量的谷歌搜索，我终于找到了大约 12 年前的一个 stackoverflow 问题的答案：https ://stackoverflow.com/a/693877/12135804

假设多边形中的边遵循一定的顺序，可以使用直线的起点 (p)、多边形中从该起点开始的下一个 ccw 点作为拐点 (q) 和终点来创建简单的 ccw 测试线 (r)。对于红线BD，测试将检查 B、C、D 是否为 ccw（不是）。对于绿线DF，测试 D,E,F 是否为 ccw（它是！）。即使这些点是不连续的，这也会起作用。但是，当红绿线的顺序颠倒时，这将失败。例如，如果红线变为DB，则测试将检查 D,E,B，这将通过 ccw 测试。

我认为一个更强大的解决方案是在凹多边形中搜索共享要测试的线端点的两条边对。对于这两对，计算两条边与 x 轴之间的角度。还要计算直线与 x 轴的角度。如果线在多边形内，则线的角度应位于两个端点的多边形边角的最大值和最小值之间。

我认为，是否测试角度的钝角或锐角取决于一些因素。红线在 wrt 与 x 轴的角度将在和B之间的钝角范围内，在点 也是如此。从视觉上看，很明显锐界是两个点的最大/最小测试需要使用的。如果可以从逻辑上选择计算边界的基线，则可以完成。ABBCC

当然，如果线在两个端点之间的途中越过多边形外部，这将不起作用，但这确实可以处理正常线-多边形相交测试的退化情况。假设它在每个退化的情况下都有效，也就是说。

我不会将此标记为答案，因为我无法证明它。

编辑：好吧，我又回来考虑这个问题，并决定搜索类似于我上面提出的角度边界的问题，并找到了这个：https ://stackoverflow.com/a/17497339/12135804

这个答案满足不知道线的方向！A但是，它假设和B应该测试之间的最小界限。这不适用于凹顶点，当AxBis < 0 时。在这种情况下，连接到顶点的线由线共享，如果它指向多边形外部A，B则返回 true，反之，如果它在内部，则返回 false。不过，我认为根据 的符号翻转结果AxB应该足以说明这一点。（在此相关答案中验证的预感：https ://stackoverflow.com/a/43384516/12135804 ）

推荐阅读