录十六

判断一个点是否在多边形内部，一般都采用射线法，它是计算几何常用的一个经典算法。

射线法的主要思路就是从这个点引出一条“射线”，与多边形的任意若干条边相交，累计相交的边数目，如果是奇数，那么点就在多边形内，否则点就在多边形外。

//定义多边形
template<class PointT>
struct Polygon
{
    int      count;
    PointT*  vertices; 
};

//判断点是否在多边形内
template<class PointT>
bool IsPointInPolygon(const Polygon<PointT>& poly, const PointT& p)
{
    bool inside = false;

    int point_num = poly.count;
    for (int i = 0, j = point_num - 1; i < point_num; j = i++)
    {
        PointT  const& U0 = poly.vertices[i];
        PointT  const& U1 = poly.vertices[j];

        double rhs, lhs;

        //(x - x0) *(y1 - y0) - (y - y0) *(x1 - x0)  = 0;
        // 当y1 - y>0时:
        //             f(x)大于0，在右侧；
        //             f(x)小于0，在左侧。

        if (p.y < U1.y)  // U1 above ray
        {
            if (U0.y <= p.y)  // U0 on or below ray
            {
                lhs = (p.y - U0.y)*(U1.x - U0.x);
                rhs = (p.x - U0.x)*(U1.y - U0.y);
                if (lhs > rhs)
                {
                    inside = !inside;
                }
            }
        }
        else if (p.y < U0.y)  // U1 on or below ray, U0 above ray
        {
            lhs = (p.y - U0.y)*(U1.x - U0.x);
            rhs = (p.x - U0.x)*(U1.y - U0.y);
            if (lhs < rhs)
            {
                inside = !inside;
            }
        }
    }
    return inside;
}