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

定义

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

a×b=absinθn

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

一、计算多边形面积

设多边形有n个顶点V0(X0, Y0), V1(X1, Y1)... Vn-1(Xn-1, Yn-1),从原点O(0,0)与每条边做三角形,计算的面积和就是多边形面积。三角形面积可以用叉积计算,比如OV0V1面积为:

S0=0.5*OV0×OV1=0.5*(X0Y1-X1Y0)

于是多边形面积总和为:

S= 0.5*(X0Y1-X1Y0 + X1Y2-X2Y1 +… + Xn-1Y0-X0Yn-1)

  = 0.5*( X0Y1-X1Y0+X0Y0-X1Y1 + X1Y2-X2Y1+X1Y1-X2Y2 +… Xn-1Y0-X0Yn-1+Xn-1Yn-1-X0Y0)

  = 0.5*(Yi+Yi+1)(Xi-Xi+1)  i=0...n-1

二、判断两线段是否相交

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

1. 快速排斥

设有线段P1P2和Q1Q2,以线段 P1P2 为对角线的矩形为R, 以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交,否则进入第二步。

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

2. 跨立实验

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

P1, P2分别在Q1Q2两边 :

(P1-Q1)×(Q2-Q1)*(P2-Q1)×(Q2-Q1)<=0

Q1, Q2分别在P1P2两边:

(Q1-P1)×(P2-P1)*(Q2-P1)×(P2-P1) <=0

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

如下图,Q1Q2在P1P2左边,

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

此时(Q1-Q2)×(P2-P1)与(P1-Q1)×(Q1-Q2)异号,

当Q1Q2向右移动后,如图所示,

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

(Q1-Q2)×(P2-P1)与(P1-Q1)×(Q1-Q2)同号,而且(P1-Q1)×(Q1-Q2)/(Q1-Q2)×(P2-P1),刚好等于|P1O|/|P1P2|,由此关系还可以计算交点的位置。

Q1Q2继续右移,如图所示:

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

交点超出P2,(P1-Q1)×(Q1-Q2)/(Q1-Q2)×(P2-P1)>1

因此,若P1 , P2跨立在Q1Q2,则有

(P1-Q1)×(Q1-Q2)/(Q1-Q2)×(P2-P1)在[0, 1]范围内。

同理,若Q1, Q2跨立P1P2,则有

(P2-P1)×(P1-Q1)/(Q1-Q2)×(P2-P1)在[0, 1]范围内。

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

 

参考:

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

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

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

上一篇:Java多线程系列--“JUC集合”01之 框架


下一篇:(linux自学笔记)linux内核定时器的使用