Greiner-Hormann算法线段相交子程序工作原理及WEC含义问询

我来给你一步步捋清楚这个intersect子程序里的WEC（窗口边缘坐标）逻辑，其实核心就是用带符号的垂直投影距离来高效判断线段相交，同时计算交点在两条线段上的参数化位置——这正是Greiner-Hormann多边形裁剪算法里判断边是否相交的关键步骤。

先搞懂WEC的本质 #

WEC是Window Edge Coordinate的缩写，这里的“窗口”其实就是我们用来做参考的那条线段（比如子程序里的Q1Q2或者P1P2）。先看公式里的符号：

• <A | B⊥> 表示向量A和向量B的垂直向量的点乘。其中B⊥是向量B逆时针旋转90度得到的向量（比如向量(x,y)的垂直向量是(-y,x)，方向只要统一就行，不影响符号判断）。
• 拿WEC_P1 = <P1 - Q1 | (Q2 - Q1)⊥>来说，它本质是把向量P1 - Q1（也就是从Q1指向P1的向量）投影到Q1Q2线段的垂直方向上，得到的带符号数值：
  • 如果结果为正，说明P1在Q1Q2线段的某一侧；
  • 结果为负，说明在另一侧；
  • 结果为0，说明P1刚好落在Q1Q2线段（或其所在直线）上。

简单说，WEC就是一个用来判断点相对于某条线段（直线）位置的“符号标签”。

子程序里的判断逻辑：如何用WEC确定线段相交 #

这个子程序的判断分两步，本质是验证两条线段是否互相跨立对方：

1. 第一步：判断P1P2是否跨立Q1Q2
   计算WEC_P1和WEC_P2（也就是P1和P2相对于Q1Q2的垂直投影符号），如果WEC_P1 * WEC_P2 <= 0，说明：

   • 要么P1和P2分别在Q1Q2的两侧（乘积为负）；
   • 要么其中一个端点刚好落在Q1Q2上（乘积为0）。
     这时候P1P2线段才有可能和Q1Q2相交。

2. 第二步：反过来判断Q1Q2是否跨立P1P2
   计算WEC_Q1 = <Q1 - P1 | (P2 - P1)⊥>和WEC_Q2 = <Q2 - P1 | (P2 - P1)⊥>，同样判断WEC_Q1 * WEC_Q2 <= 0。这一步是为了排除“其中一条线段的端点在另一条线段的延长线上”的情况——只有两条线段互相跨立对方，才能确定它们真正相交于线段内部（或端点）。

计算alphaP和alphaQ：交点的参数化位置 #

当两条线段确定相交后，就可以计算交点在两条线段上的参数比例：

• alphaP = WEC_P1/(WEC_P1 - WEC_P2)：这个值表示交点在线段P1P2上的位置，范围是0到1之间（包含端点）。比如alphaP=0时交点是P1，alphaP=1时是P2，0.5就是线段中点位置。
• alphaQ = WEC_Q1/(WEC_Q1 - WEC_Q2)：同理，这个值表示交点在线段Q1Q2上的位置。

这个计算的原理其实是利用相似三角形的比例关系：WEC的差值对应了垂直投影方向上的长度差，用初始点的WEC除以总差值，就能得到交点在线段上的参数比例，比直接解直线方程组要简洁高效。

为什么用WEC而不是直接解直线方程？ #

在多边形裁剪场景中，我们需要快速批量判断大量线段是否相交，WEC的优势在于：

1. 计算量小：只需要向量减法和点乘，都是简单的算术运算；
2. 自带符号判断：不需要额外计算距离或角度，就能直接判断点的相对位置；
3. 同时完成判断和参数计算：一次计算既能确定是否相交，又能得到交点的参数化位置，完美适配Greiner-Hormann算法后续对交点的标记和处理需求。

内容的提问来源于stack exchange，提问作者NicknEma