algorithm - 闭合多边形链与线的交点

Question

我需要找到能够找到闭合多边形链和线的 2 个交点的算法。我的多边形链被定义为一个设定点坐标 (x,y)，我也有直线方程。

准确的说，请看下图。我的输入是直线方程和 P1...Pn。我想找到点 X1 和 X2 的坐标。

Answer 1

鉴于该线的方程式为 a*x+b*y+c=0 , 你可以找出每个点在那条线的哪一侧，只需插入点的 x,y 坐标 P_k进入那个表达:

S_k = a*x_k + b*y_k + c

对于线上的点，结果 S_k为 0(服从直线方程)。对于线一侧的点，结果将 > 0，对于另一侧的点，结果将 < 0。对每个点按顺序执行此操作，直到符号切换:S_k * S_{k-1} < 0 .这条线穿过 P_k和 P_{k-1} .