100steps/Blogs

快速排斥实验和跨立实验

Opened this issue · 0 comments

SihangWu commented

快速排斥实验和跨立试验

  • 当我们知道两 线段 4个点的坐标，如何利用计算几何来判断用他们是否相交？

review

  • 矢量叉积
设矢量 P = (x1, y1), Q = (x2, y2)，
则 P X Q = x1 * y2 - x2 * y1;
其结果是一个由 (0, 0), P, Q, P + Q 所组成的
平行四边形的带符号的面积，
P X Q = -(Q X P),
P X (- Q) = -(P X Q)
叉积的一个非常重要的性质
是可以通过它的符号
来判断两矢量相互之间的顺逆时针关系：  
若 P X Q > 0，则 P 在 Q 的顺时针方向
若 P X Q < 0, 则 P 在 Q 的逆时针方向
若 P X Q = 0，则 P 与 Q 共线，
但不确定 P, Q 的方向是否相同

基本思路

  • 第一步
    • 快速排斥试验
      如果分别以P1P2 ，P3P4 为对角线做矩形，而这两个矩形不相交，则这两条线段肯定不相交，如下左图；即使两个矩形相交，这两条线段也不一定相交，如下右图，这时再用第2 步判断；
      1

表示成语句，即两个矩形相交当且仅当下列式子为真：

（max(x1,x2)≥min(x3,x4)) && (max(x3,x4)≥min(x1,x2)) &&
（max(y1,y2)≥min(y3,y4))
&&(max(y3,y4)≥min(y1,y2))

两个矩形相交必须在两个方向上都相交，式子的前半部分判断在x 方向上是否相交，后半部分判断在y 方向上是否相交。

  • 第二步
    • 跨立试验
      若 P1P2 跨立 Q1Q2，则 P1,P2 分别在 Q1Q2 所在直线的两端，则有
(P1 - Q1)X(Q2 - Q1) * (Q2 - Q1)X(P2 - Q1)> 0,

当 (P1 - Q1) X (Q2 - Q1) = 0 时，
说明 (P1 - Q1) 与 (Q2 - Q1) 共线，但由于已经经过快速排斥试验，所以 Q1 必为 P1P2 与 Q1Q2 的交点，依然满足线段相交的条件，则跨立试验可改为：

当
(P1 - Q1)X(Q2 - Q1) * (Q2 - Q1)X(P2 - Q1) >= 0，
则 P1P2 跨立 Q1Q2，
当 Q1Q2 也跨立 P1P2 的时候，则 P1P2 相交

（注意式子中被隔开的 * 代表两个叉积的值的相乘，而另外的两个 X 则代表计算矢量叉积,另外注意满足跨立试验的特例--共线的情况，所以要同时满足快速排斥实验和跨立实验才能证明两线段相交。）
default