经过大量的谷歌搜索,我终于找到了大约 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
之间的钝角范围内,在点 也是如此。从视觉上看,很明显锐界是两个点的最大/最小测试需要使用的。如果可以从逻辑上选择计算边界的基线,则可以完成。AB
BC
C
当然,如果线在两个端点之间的途中越过多边形外部,这将不起作用,但这确实可以处理正常线-多边形相交测试的退化情况。假设它在每个退化的情况下都有效,也就是说。
我不会将此标记为答案,因为我无法证明它。
编辑:好吧,我又回来考虑这个问题,并决定搜索类似于我上面提出的角度边界的问题,并找到了这个:https ://stackoverflow.com/a/17497339/12135804
这个答案满足不知道线的方向!A
但是,它假设和B
应该测试之间的最小界限。这不适用于凹顶点,当AxB
is < 0 时。在这种情况下,连接到顶点的线由线共享,如果它指向多边形外部A
,B
则返回 true,反之,如果它在内部,则返回 false。不过,我认为根据 的符号翻转结果AxB
应该足以说明这一点。(在此相关答案中验证的预感:https ://stackoverflow.com/a/43384516/12135804 )