判断点P是否在多边形（凹多边形或者凸多边形）内

http://blog.sina.com.cn/s/blog_8e6bfecf0100zve9.html

方法1：

    从点P向左做射线，计算与多边形的交点数。如果交点个数为奇数，点P在多边形内部；如果交点个数为偶数，点P在多边形外部。可以按任意顺序考虑多边形的每一条边，来求取交点的总个数。

    计算时需要注意：（以边P1P2为例）

1. 如果一个多边形顶点以该射线为切线，则直接忽略该顶点（因为射线会与两条线段的端点相交，而这两条线段有一个共同的端点）；
2. 如果边P1P2水平，射线与其无交点或有无数个交点，该边也可以直接忽略；
3. 如果边P1P2竖直，很容易判断是否相交（只能有一个交点）；
4. 判断相交之前，先判断P是否在边P1P2上，如果在，则P在多边形内部（可根据内部的不同定义更改）。

注意：可以使用bounding box进行加速。

方法2：

    首先保证多边形的所有点都有序。然后，做P点到多边形所有点的连线，计算P点与多边形所有边的端点所成的角度（在P点处所成的角）的和（根据边的顶点位置，求出来的角度有正有负）。如果所有角度的和等于 2PI ，则点P在多边形内；否则，点P在多边形外。

    同样，可以使用bounding box进行加速。

判断一个点P是否在三角形ABC内：

当点p在三角形abc内时，4个三角形的面积满足：abc = abp + apc + pbc

计算面积使用向量外积：abc = |ab x ac| / 2

而且因为：

pb x pc = (ab-ap) x (ac-ap) = ab x ac - ab x ap - ap x ac

所以公式转换为：

ab x ac 是否等于 ab x ap + ap x ac + (ab x ac - ab x ap - ap x ac)