闲聊叉积在计算几何中一些作用

定义

两个向量的叉积写作a×b，可以定义为

a×b=absinθn

其中θ表示a和b之间的角度（0°≤θ≤180°）。它位于这两个矢量所定义的平面上。而n是一个与a、b所在平面均垂直的单位矢量。矢量叉积是计算几何算法的核心部分，具有重要的几何意义。

一、计算多边形面积

设多边形有n个顶点V₀(X_0, Y₀), V₁(X_1, Y₁)... V_n-1(X_n-1, Y_n-1)，从原点O(0,0)与每条边做三角形，计算的面积和就是多边形面积。三角形面积可以用叉积计算，比如OV₀V₁面积为：

S₀=0.5*OV₀×OV₁=0.5*(X₀Y₁-X₁Y₀)

于是多边形面积总和为：

S= 0.5*(X₀Y₁-X₁Y₀ + X₁Y₂-X₂Y₁ +… + X_n-1Y₀-X₀Y_n-1)

  = 0.5*( X₀Y₁-X₁Y₀+X₀Y₀-X₁Y₁ + X₁Y₂-X₂Y₁+X₁Y₁-X₂Y₂ +… X_n-1Y₀-X₀Y_n-1+X_n-1Y_n-1-X₀Y₀)

  = 0.5*（Y_i+Y_i+1）(X_i-X_i+1)  i=0...n-1

二、判断两线段是否相交

判断线段是否相交一般分两步进行:

1. 快速排斥

设有线段P₁P₂和Q₁Q₂，以线段 P₁P₂ 为对角线的矩形为R， 以线段 Q₁Q₂ 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交，否则进入第二步。

2. 跨立实验

如果两线段相交，那么两线段必然相互跨立对方。即

P_1, P₂分别在Q₁Q₂两边 :

(P₁-Q₁)×(Q₂-Q₁)*(P₂-Q₁)×(Q₂-Q₁)<=0

Q_1, Q₂分别在P₁P₂两边：

(Q₁-P₁)×(P₂-P₁)*(Q₂-P₁)×(P₂-P₁) <=0

上面跨立实验需要4次叉积和两次乘法运算，可以这样改进：

如下图，Q₁Q₂在P₁P₂左边，

此时(Q₁-Q₂)×(P₂-P₁)与(P₁-Q₁)×(Q₁-Q₂)异号，

当Q₁Q₂向右移动后，如图所示，

(Q₁-Q₂)×(P₂-P₁)与(P₁-Q₁)×(Q₁-Q₂)同号，而且(P₁-Q₁)×(Q₁-Q₂)/(Q₁-Q₂)×(P₂-P₁)，刚好等于|P₁O|/|P₁P₂|，由此关系还可以计算交点的位置。

Q₁Q₂继续右移，如图所示：

交点超出P₂，(P₁-Q₁)×(Q₁-Q₂)/(Q₁-Q₂)×(P₂-P₁)>1

因此，若P_{1 ,} P₂跨立在Q₁Q₂，则有

(P₁-Q₁)×(Q₁-Q₂)/(Q₁-Q₂)×(P₂-P₁)在[0, 1]范围内。

同理，若Q_1, Q₂跨立P₁P₂，则有

(P₂-P₁)×(P₁-Q₁)/(Q₁-Q₂)×(P₂-P₁)在[0, 1]范围内。

这样只需要3次叉积运算就能算出线段是否相交，而且还可以顺便得到相交点的位置！

 

参考：

http://zh.wikipedia.org/wiki/%E5%8F%89%E7%A7%AF

http://dev.gameres.com/Program/Abstract/Geometry.htm