我需要找到能够找到闭合多边形链和线的 2 个交点的算法。 我的多边形链被定义为一个设定点坐标 (x,y),我也有直线方程。
准确的说,请看下图。我的输入是直线方程和 P1...Pn
。我想找到点 X1 和 X2 的坐标。
最佳答案
鉴于该线的方程式为 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}
.
关于algorithm - 闭合多边形链与线的交点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21030030/