判断点在多边形内算法的C++实现

admin1

算法步骤如下：

已知点point(x,y)和多边形Polygon的点有序集合（x1,y1;x2,y2;….xn,yn;）；
以point为起点，以无穷远为终点作平行于X轴的射线line(x,y; -∞,y)；循环取得多边形的每一条边side(xi,yi;xi+1,yi+1)：

1). 判断point(x,y)是否在side上，如果是，则返回true。

2). 判断line与side是否有交点，如果有则count++。
判断交点的总数count，如果为奇数则返回true，偶数则返回false。

[code]#include<iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define EPSILON 0.000001
using namespace std;
//二维double矢量
struct  Vec2d
{
        double x, y;
        Vec2d()
        {
                x = 0.0;
                y = 0.0;
        }
        Vec2d(double dx, double dy)
        {
                x = dx;
                y = dy;
        }
        void Set(double dx, double dy)
        {
                x = dx;
                y = dy;
        }
};
//判断点在线段上
bool IsPointOnLine(double px0, double py0, double px1, double py1, double px2, double py2)
{
        bool flag = false;
        double d1 = (px1 - px0) * (py2 - py0) - (px2 - px0) * (py1 - py0);
        if ((abs(d1) < EPSILON) && ((px0 - px1) * (px0 - px2) <= 0) && ((py0 - py1) * (py0 - py2) <= 0))
        {
                flag = true;
        }
        return flag;
}
//判断两线段相交
bool IsIntersect(double px1, double py1, double px2, double py2, double px3, double py3, double px4, double py4)
{
        bool flag = false;
        double d = (px2 - px1) * (py4 - py3) - (py2 - py1) * (px4 - px3);
        if (d != 0)
        {
                double r = ((py1 - py3) * (px4 - px3) - (px1 - px3) * (py4 - py3)) / d;
                double s = ((py1 - py3) * (px2 - px1) - (px1 - px3) * (py2 - py1)) / d;
                if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1))
                {
                        flag = true;
                }
        }
        return flag;
}
//判断点在多边形内
bool Point_In_Polygon_2D(double x, double y, const vector<Vec2d> &POL)
{
        bool isInside = false;
        int count = 0;
        //
        double minX = DBL_MAX;
        for (int i = 0; i < POL.size(); i++)
        {
                minX = std::min(minX, POL[i].x);
        }
        //
        double px = x;
        double py = y;
        double linePoint1x = x;
        double linePoint1y = y;
        double linePoint2x = minX -10;                        //取最小的X值还小的值作为射线的终点
        double linePoint2y = y;
        //遍历每一条边
        for (int i = 0; i < POL.size() - 1; i++)
        {
                double cx1 = POL[i].x;
                double cy1 = POL[i].y;
                double cx2 = POL[i + 1].x;
                double cy2 = POL[i + 1].y;
                if (IsPointOnLine(px, py, cx1, cy1, cx2, cy2))
                {
                        return true;
                }
                if (fabs(cy2 - cy1) < EPSILON)   //平行则不相交
                {
                        continue;
                }
                if (IsPointOnLine(cx1, cy1, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
                {
                        if (cy1 > cy2)                        //只保证上端点+1
                        {
                                count++;
                        }
                }
                else if (IsPointOnLine(cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
                {
                        if (cy2 > cy1)                        //只保证上端点+1
                        {
                                count++;
                        }
                }
                else if (IsIntersect(cx1, cy1, cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y))   //已经排除平行的情况
                {
                        count++;
                }
        }
        if (count % 2 == 1)
        {
                isInside = true;
        }
        return isInside;
}
int main()
{
        //定义一个多边形（六边形）
        vector<Vec2d> POL;
        POL.push_back(Vec2d(268.28, 784.75));
        POL.push_back(Vec2d(153.98, 600.60));
        POL.push_back(Vec2d(274.63, 336.02));
        POL.push_back(Vec2d(623.88, 401.64));
        POL.push_back(Vec2d(676.80, 634.47));
        POL.push_back(Vec2d(530.75, 822.85));
        POL.push_back(Vec2d(268.28, 784.75));                                //将起始点放入尾部，方便遍历每一条边
        //
        if (Point_In_Polygon_2D(407.98, 579.43, POL))
        {
                cout << "点（407.98, 579.43）在多边形内" << endl;
        }
        else
        {
                cout << "点（407.98, 579.43）在多边形外" << endl;
        }
        //
        if (Point_In_Polygon_2D(678.92, 482.07, POL))
        {
                cout << "点（678.92, 482.07）在多边形内" << endl;
        }
        else
        {
                cout << "点（678.92, 482.07）在多边形外" << endl;
        }
        return 0;
}[/code]