MONTH / February, 2009

判断一个点是否在 2D 三角形内

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

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

  1. 叉乘法
  2. 原理:

    沿 △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 等人也用的类似算法。

  3. 面积法
  4. 原理:

    若点 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,比它简单一点,但同样需要对向量做归一化处理,效率不高,故放弃了。另外的算法还包括划线交点法、解方程组法、复数法等,但计算量都较大,不再赘述。