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

这篇具有很好参考价值的文章主要介绍了判断点在多边形内算法的C++实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本篇博客介绍了使用射线法判断点在多边形内部还是外部的算法,并通过C++做了具体实现

1. 算法思路

判断平面内点是否在多边形内有多种算法,其中射线法是其中比较好理解的一种,而且能够支持凹多边形的情况。该算法的思路很简单,就是从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。

如下图所示:射线和多边形一共有5个交点,为奇数,所以点在多边形内

c++ 判断点在多边形内,判断点在多边形内外,判断点在多边形内部外部,射线法

2. 算法步骤

  2.1 已知点point(x,y)和多边形Polygon的点有序集合(x1,y1;x2,y2;….xn,yn;);
以point为起点,以无穷远为终点作平行于X轴的射线line(x,y; -∞,y);循环取得多边形的每一条边side(xi,yi;xi+1,yi+1):
  2.2. 判断point(x,y)是否在side上,如果是,则返回true。
  2.3. 判断line与side是否有交点,如果有则count++。判断交点的总数count,如果为奇数则返回true,偶数则返回false。

2.4 判断交点的总数count,如果为奇数则返回true,偶数则返回false。

极端情况需要注意:当射线line经过的是多边形的顶点时,判断就会出现异常情况。针对这个问题,由于多边形的每一个顶点都在两个线段上,可以根据线段的两个端点的y坐标做上下判断,y值较大的顶点称为上端点,y值较小是下端点。如果射线经过上端点,count加1,如果经过下端点,则count不必加1,如下图

第一个图,交叉点为X,先计算线段(p1,p2),由于经过的是p2,即下端点,count值不加;再计算线段(p2,p3),由于经过的是p2,也是下端点,count值还是不加,总结:射线和 多边形一共有1个交点,为奇数,所以A在多边形内

第二个图,交叉点为X,先计算线段(p1,p2),由于经过的是p2,即上端点,count值加1;再计算线段(p2,p3),由于经过的是p2,也是上端点,count值加1,总结:射线和 多边形一共有3个交点,为奇数,所以A在多边形内

c++ 判断点在多边形内,判断点在多边形内外,判断点在多边形内部外部,射线法

 3. 实现代码

#include<iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

// 浮点数最小精度
#define EPSILON 0.000001

// 向量(也可用来表点)
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;
	}
};

// 判断点在线段上
// (px0, py0)	:	点坐标
// (px1, py1)	:	边的第一个点
// (px2,py2)	:	边的第二个点
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;
}

// 判断两线段相交
// (px1, py1)	:	第一边的第一个点
// (px2, py2)	:	第一边的第二个点
// (px3, py3)	:	第二边的第一个点
// (px4, py4)	:	第二边的第二个点
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;
}

// 判断点是否在多边形内(点在多边形的边上也算在内部)
// (x, y)	:	点坐标
// POL		:	多边形的各个点(需连续,顺时针/逆时针皆可)
bool Point_In_Polygon_2D(double x, double y, const vector<Vec2d>& POL)
{
	bool isInside = false;
	int  count    = 0;

	// 求出多边形的最小X
	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;

	// 负X方向的水平射线,(x,y)做起点,(minX, y)做终点
	double linePoint1x = x;
	double linePoint1y = y;
	double linePoint2x = minX - 10;			
	double linePoint2y = y;

	// 遍历每一条边
	for (int i = 0; i < POL.size()-1; i++)
	{
		double cx1 = POL[i].x;	// 多边形的第i个点
		double cy1 = POL[i].y;		
		double cx2 = POL[i+1].x;// 多边形的第i+1个点
		double cy2 = POL[i+1].y;

		// 点在多边形上,算是在内部
		if (IsPointOnLine(px, py, cx1, cy1, cx2, cy2))
		{
			return true;
		}

		// X方向水平的边,不用计算,肯定不会和射线相交
		if (fabs(cy2 - cy1) < EPSILON)
		{
			continue;
		}

		// 多边形的一个顶点在射线上,且该顶点是上顶点(y值较高),算一个交点
		if (IsPointOnLine(cx1, cy1, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
		{
			if (cy1 > cy2)
			{
				count++;
			}
		}
		// 多边形的一个顶点在射线上,且该顶点是上顶点(y值较高),算一个交点
		else if (IsPointOnLine(cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y))
		{
			if (cy2 > cy1)
			{
				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;
	}

	system("pause");
	return 0;
}

4. 执行结果

c++ 判断点在多边形内,判断点在多边形内外,判断点在多边形内部外部,射线法文章来源地址https://www.toymoban.com/news/detail-660772.html

到了这里,关于判断点在多边形内算法的C++实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 如何判断两个多边形是否相交?——多边形相交判定算法详解

    如何判断两个多边形是否相交?——多边形相交判定算法详解 在计算机图形学中,判断两个多边形是否相交是一项很重要的任务。这涉及到各种应用场景,如碰撞检测、模拟物理效果等。在本篇文章中,我们将会介绍多边形相交判定算法的相关知识和实现方式。 首先,我们

    2024年02月14日
    浏览(62)
  • 基于C++ 的OpenCV绘制多边形,多边形多条边用不用的颜色绘制

    使用基于C++的OpenCV库来绘制多边形,并且为多边形的不同边使用不同的颜色,可以按照以下步骤进行操作: 首先,确保你已经安装了OpenCV库并配置好了你的开发环境。 导入必要的头文件: 创建一个空白的图像,然后绘制多边形,并为每条边选择不同的颜色: 在这个示例中,

    2024年02月13日
    浏览(52)
  • [C++] opencv - approxPolyDP(多边形拟合)函数介绍和使用场景

    OpenCV中的 approxPolyDP() 函数用于对形状进行逼近,以减少多边形的顶点数,可以用于对图像轮廓点进行多边形拟合。 函数原型如下: 其中, curve 是输入的点集,类型为 InputArray, 可以是 Mat 、 vectorPoint 等; approxCurve是输出的点集,类型为 OutputArray, 也是 Mat 类型; epsilon 是精

    2024年03月14日
    浏览(65)
  • [C++] opencv - fillPoly(填充多边形)函数介绍和使用场景

    fillPoly() 函数是OpenCV中用于绘制填充多边形的函数。函数原型如下: fillPoly() 函数适用于需要绘制填充多边形的场景,例如在图像上绘制一个封闭的图形、制作一个简单的遮罩等。   fillPoly() 函数是OpenCV中用于绘制填充多边形的函数。可以用来绘制实心三角形,实心矩形,实

    2024年02月19日
    浏览(114)
  • mysql如何实现根据经纬度判断某一个坐标是否在一个多边形区域范围内

    要根据经纬度判断一个坐标是否在一个多边形区域内,MySQL提供了几种函数来处理地理空间数据,其中包括用于处理多边形区域的函数。 首先,创建一个表来存储多边形区域。可以使用 ST_GeomFromText 函数将多边形的坐标转换为地理空间对象。我们给他插入两条数据,默认id第一

    2024年02月08日
    浏览(49)
  • Opencv(C++)笔记--绘制直线、矩形、椭圆、圆、填充多边形、绘制字体和随机产生坐标点

    目录 1--cv::line()绘制直线 2--cv::Rect()绘制矩形 3--cv::ellipse()绘制椭圆 4--cv::circle()绘制圆 5--cv::fillPoly()填充多边形 6--cv::putText()绘制字体 6--cv::RNG随机产生坐标点 使用 cv::Point p1 定义坐标点; 使用 cv::line() 绘制直线,传入的参数依次为:背景图、两个点的坐标、直线的颜色、直线

    2024年02月14日
    浏览(55)
  • 如何判断一个点是否在凸多边形内 - golang

    判断一个点是否在凸多边形内的方法很多,此处仅给出使用 向量叉积法 判断点是否在凸多边形内的方法。 以下图为例说明问题: 原理: 1. 将多边形的第 i 条边的第一个顶点指向点 P 得到向量 v1,然后将从第一个顶点指向第二个顶点得到向量 v2,叉乘这两个向量。 2. 如果叉

    2024年02月07日
    浏览(50)
  • 百度地图API:JavaScript开源库几何运算判断点是否在多边形内(电子围栏)

    漏刻有时百度地图API实战开发(1)华为手机无法使用addEventListener click 的兼容解决方案 漏刻有时百度地图API实战开发(2)文本标签显示和隐藏的切换开关 漏刻有时百度地图API实战开发(3)自动获取地图多边形中心点坐标 漏刻有时百度地图API实战开发(4)显示指定区域在移动端异常的

    2024年02月07日
    浏览(63)
  • 计算机图形学实验——利用MFC对话框实现多边形绘制与填充(扫描线填充算法)附源码

    内容概括: 利用基于对话框的MFC项目 实现鼠标点击绘制多边形 实现扫描线算法填充多边形 源码见Yushan-Ji/ComputerGraphics: ECNU2023秋 计算机图形学课程实验代码 (github.com) 通过鼠标交互输入多边形 对各种多边形进行填充,包括边界自交的情况 利用 OnLButtonDown 和 OnRButtonDown 函数,

    2024年02月04日
    浏览(70)
  • 【Weiler-Atherton算法】 计算机图形学多边形裁剪算法

    源代码: https://github.com/ricar0/Weiler-Atherton-Alogrithm/tree/master 通常来说就是利用多边形来裁剪多边形的一种方法,一般情况下是利用矩形来裁剪凹凸多边形 凸多边形 凹多边形 上面红色划线部分就是裁剪出的部分 OPENGL基础语法 基本上就是一些画线和画多边形的操作,难度较低

    2023年04月09日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包