Python：如何判断测量曲线是否未与四点定义的线性包络相交

1. 预处理包络角点 #

• 先将四个包络角点按连续顺序排列（比如顺时针/逆时针，或按x坐标递增顺序，确保四条线段构成完整的包络边界），明确四条连接线段：$P_1-P_2$、$P_2-P_3$、$P_3-P_4$、$P_4-P_1$（若为闭合包络）。
• 为每条线段推导直线方程：
  • 对于非竖直线段（两点x坐标不同），用斜截式 $y = kx + b$，其中斜率 $k = \frac{y_b - y_a}{x_b - x_a}$，截距 $b = y_a - kx_a$。
  • 对于竖直线段（两点x坐标相同），直接记录 $x = x_a$，以及线段的y值范围 $[min(y_a,y_b), max(y_a,y_b)]$。

2. 逐点验证曲线位置 #

遍历曲线的每个数据点 $(x_p, y_p)$：

• 匹配对应包络线段：
  • 若 $x_p$ 小于包络所有角点的最小x值：取最左侧的包络线段，用其直线方程延伸计算对应y值。
  • 若 $x_p$ 大于包络所有角点的最大x值：取最右侧的包络线段，用其直线方程延伸计算对应y值。
  • 若 $x_p$ 落在某条包络线段的x区间内：直接使用该线段的直线方程。
• 计算包络对应位置的y值：
  • 非竖直线段：代入 $x_p$ 得到 $y_{env} = kx_p + b$。
  • 竖直线段：若 $x_p = x_a$，则 $y_{env}$ 的上限为线段的最大y值（因为要判断点在下方，即 $y_p ≤ max(y_a,y_b)$）。
• 比较判断：若存在任意点满足 $y_p > y_{env}$，则曲线在包络上方或相交，不符合要求。

3. 线段相交检测（补充验证） #

仅逐点比较可能遗漏曲线线段穿过包络的情况，需额外检测曲线线段与包络线段是否相交：

• 遍历曲线的每一段相邻点构成的线段 $Q_i-Q_{i+1}$，再遍历包络的四条线段 $P_a-P_b$，用跨立实验判断是否相交：
  1. 计算向量叉积：
     • $cross1 = (x_b - x_a)(y_{q1} - y_a) - (y_b - y_a)(x_{q1} - x_a)$
     • $cross2 = (x_b - x_a)(y_{q2} - y_a) - (y_b - y_a)(x_{q2} - x_a)$
     • $cross3 = (x_{q2} - x_{q1})(y_a - y_{q1}) - (y_{q2} - y_{q1})(x_a - x_{q1})$
     • $cross4 = (x_{q2} - x_{q1})(y_b - y_{q1}) - (y_{q2} - y_{q1})(x_b - x_{q1})$
  2. 若 $(cross1 * cross2 < 0)$ 且 $(cross3 * cross4 < 0)$，则两条线段相交；若叉积为0，需检查点是否在线段的坐标区间内（共线且重叠）。
• 若存在任意一对线段相交，曲线不符合要求。

4. 性能优化 #

• 快速过滤：先计算曲线的最大y值和包络的最小y值，若曲线最大y值 < 包络最小y值，可直接判定曲线在包络下方，跳过后续检测。
• 曲线点数量为1000时，总检测次数仅为1000次逐点验证 + 999*4次线段检测，计算量极小，可实时完成。

内容的提问来源于stack exchange，提问作者will.wo