Posted at 09月 29, 2009

这是我拿到公司 offer 时美国老大给我的面试题，对于当时我这种文盲来说，还是杀死了不少脑细胞。最近闲来无事（嗯。。。被危机了），又拿出来琢磨了一下各算法。

设一在在 2D 空间中的三角形 △ABC ，三个顶点向量 A(ax, ay)、B(bx, by)、C(cx, cy)，三条有向边 AB、BC、CA，有一点 P(px, py)。

1. 叉乘法

   原理：

   沿 △ABC 各有向边按一定方向走（顺时针或逆时针），判断点 P 是否在该边的某侧（右侧或左侧），若点 P 在三条边的同侧，则点 P 在 △ABC 内。

   实现：

   分别计算向量 AB、BC、CA 与向量 AP、BP、CP 的向量积（叉乘），若三个结果均同号（正或负，为零表示 P 在边上），则可得点 P 在 △ABC 内。其中AB = B - A，AB×AP = AB.x*AP.y - AB.y*AP.x。

   该算法只需要做 3 次叉乘（6 次普通数值乘法），效率高，且没有浮点误差。
   这是我当时面试想的算法，Azure 等人也用的类似算法。

2. 面积法

   原理：

   若点 P 在 △ABC 内，则 △ABP、△BCP、△CAP 的面积之和应等于 △ABC 的面积。

   实现：

   利用两个向量叉积的几何意义为该两个向量所围三角形面积的 2 倍，分别计算 AB×BP、BC×CP、CA×AP、AB×BC，若 |AB×BP| + |BC×CP| + |CA×AP| = |AB×BC|，则得点 P 在 △ABC 内。

   这个算法用得比较普遍，需要做 4 次叉乘（8 次普通数值乘法），效率和叉乘法差不多，同时避免了用海伦公式计算面积的低效和精度问题（数值除法和开方运算）。

我昨天想的一个算法有点类似这篇文章中的方法 3，比它简单一点，但同样需要对向量做归一化处理，效率不高，故放弃了。另外的算法还包括划线交点法、解方程组法、复数法等，但计算量都较大，不再赘述。

矢量叉积 点积

矢量叉积：（矢量，右手螺旋定则）

设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。

叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：

若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。

应用：

折线段的拐向判断：（可用作多边形凹凸判定）

折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：

若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

矢量点积：（标量，面积）
P。Q ＝ a1a2 + b1b2 = ｜P｜x｜Q｜x COS(P,Q)|
应用：
求点到线段距离
1.确定点到线段所在直线的投影(某一端点到点的矢量为P,以此端点为始点，另一端点为终点的矢量为Q)
a.投影在线段之外，距离为某一端点到点的距离
1) cos(P,Q) < 0
2)|P|cos(P,Q)/|Q｜>1
b.投影在线段之内
求出投影点，计算投影点到点的距离
a = l.p1();//first point of the line
b = l.p2();//second one
QPointF ab = QPointF(b.x()-a.x(),b.y()-a.y());
QPointF ap = QPointF(p.x()-a.x(),p.y()-a.y());
qreal f = ab.x()*ap.x()+ab.y()*ap.y();
//angle between 90 and 270
if(f<0){
ret_pos = a;
return p2pDistance(a,p);
}
qreal d = ab.x()*ab.x() + ab.y()*ab.y();
if(f>d){
ret_pos = b;
return p2pDistance(b,p);
}
f /= d;
QPointF m = QPointF(a.x()+f*ab.x(),a.y()+f*ab.y());
ret_pos = m;
return p2pDistance(m,p);