首页 / 算法 / 判断点在多边形内算法的C++实现
判断点在多边形内算法的C++实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了判断点在多边形内算法的C++实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4059字，纯文字阅读大概需要6分钟。
内容图文
目录
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()这里并不是最优算法，可以改成向量计算，效率应该更高。
内容总结
以上是互联网集市为您收集整理的判断点在多边形内算法的C++实现全部内容，希望文章能够帮你解决判断点在多边形内算法的C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。