判断一个点是否在 2D 三角形内
这是我拿到公司 offer 时美国老大给我的面试题，对于当时我这种文盲来说，还是杀死了不少脑细胞。最近闲来无事（嗯。。。被危机了），又拿出来琢磨了一下各算法。
设一在在 2D 空间中的三角形 △ABC ，三个顶点向量 A(ax, ay)、B(bx, by)、C(cx, cy)，三条有向边 AB、BC、CA，有一点 P(px, py)。
叉乘法
原理：
沿 △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 等人也用的类似算法。
面积法
原理：
若点 P 在 △ABC 内，则 △ABP、△BCP、△CAP 的面积之和应等于 △ABC 的面积。
实现：
利用两个向量叉积的几何意义为该两个向量所围三角形面积的 2 倍，分别计算 AB×BP、BC×CP、CA×AP、AB×BC，若 [...]
