目录
1. 算法思路
2. 具体实现
3. 改进空间
1. 算法思路
判断平面内点是否在多边形内有多种算法, 其中射线法是其中比较好理解的一种, 而且能够支持凹多边形的情况. 该算法的思路很简单, 就是从目标点出发引一条射线, 看这条射线和多边形所有边的交点数目. 如果有奇数个交点, 则说明在内部, 如果有偶数个交点, 则说明在外部. 如下图所示:
算法步骤如下:
已知点 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.
2. 具体实现
在具体的实现过程中, 其实还有一个极端情况需要注意: 当射线 line 经过的是多边形的顶点时, 判断就会出现异常情况. 针对这个问题, 可以规定线段的两个端点, 相对于另一个端点在上面的顶点称为上端点, 下面是下端点. 如果射线经过上端点, count 加 1, 如果经过下端点, 则 count 不必加 1. 具体实现如下:
- #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;
- }
运行结果如下:
3. 改进空间
很多情况下在使用该算法之前, 需要一个快速检测的功能: 当点不在多边形的外包矩形的时候, 那么点一定不在多边形内.
判断点在线上函数 IsPointOnLine()和判断线段相交函数 IsIntersect()这里并不是最优算法, 可以改成向量计算, 效率应该更高.
来源: https://www.cnblogs.com/charlee44/p/10704156.html