本篇博客介紹了使用射線法判斷點在多邊形內部還是外部的算法，并通過C++做了具體實現(xiàn)

1. 算法思路

判斷平面內點是否在多邊形內有多種算法，其中射線法是其中比較好理解的一種，而且能夠支持凹多邊形的情況。該算法的思路很簡單，就是從目標點出發(fā)引一條射線，看這條射線和多邊形所有邊的交點數目。如果有奇數個交點，則說明在內部，如果有偶數個交點，則說明在外部。

如下圖所示：射線和多邊形一共有5個交點，為奇數，所以點在多邊形內

2. 算法步驟

? 2.1 已知點point(x,y)和多邊形Polygon的點有序集合（x1,y1;x2,y2;….xn,yn;）；
以point為起點，以無窮遠為終點作平行于X軸的射線line(x,y; -∞,y)；循環(huán)取得多邊形的每一條邊side(xi,yi;xi+1,yi+1)：
? 2.2. 判斷point(x,y)是否在side上，如果是，則返回true。
? 2.3. 判斷l(xiāng)ine與side是否有交點，如果有則count++。判斷交點的總數count，如果為奇數則返回true，偶數則返回false。

2.4?判斷交點的總數count，如果為奇數則返回true，偶數則返回false。

極端情況需要注意：當射線line經過的是多邊形的頂點時，判斷就會出現(xiàn)異常情況。針對這個問題，由于多邊形的每一個頂點都在兩個線段上，可以根據線段的兩個端點的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在多邊形內

?3. 實現(xiàn)代碼

#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		:	多邊形的各個點（需連續(xù)，順時針/逆時針皆可）
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. 執(zhí)行結果

文章來源地址http://www.zghlxwxcb.cn/news/detail-660772.html

到了這里，關于判斷點在多邊形內算法的C++實現(xiàn)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！