判断点在多边形内的多种写法(C版)

转载自：http://blog.csdn.net/okvee/article/details/5643407

再经典不过的算法了：

// 功能：判断点是否在多边形内
// 方法：求解通过该点的水平线与多边形各边的交点
// 结论：单边交点为奇数，成立!

//参数：
// POINT p 指定的某个点
// LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致）
// int nCount 多边形定点的个数

BOOL PtInPolygon (POINT p, LPPOINT ptPolygon, int nCount)
{
　　int nCross = 0;

　　for (int i = 0; i < nCount; i++)
　　{
　　　　POINT p1 = ptPolygon[i];
　　　　POINT p2 = ptPolygon[(i + 1) % nCount];

　　　　// 求解 y=p.y 与 p1p2 的交点

　　　　if ( p1.y == p2.y ) // p1p2 与 y=p0.y平行
　　　　　　continue;

　　　　if ( p.y < min(p1.y, p2.y) ) // 交点在p1p2延长线上
　　　　　　continue;
　　　　if ( p.y >= max(p1.y, p2.y) ) // 交点在p1p2延长线上
　　　　　　continue;

　　　　// 求交点的 X 坐标 --------------------------------------------------------------
　　　　double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;

　　　　if ( x > p.x )
　　　　　　nCross++; // 只统计单边交点
　　}

　 // 单边交点为偶数，点在多边形之外 ---
　return (nCross % 2 == 1);
}