C++程序 判断某一点/区域 是否在另一区域内部

代码中主要包含两个函数

//1. 判断点point是否在区域rgn内部 1--内部 -1--边界 0--外部
template 
int isPointInRgn(const mVector &point, 
				 const std::vector > &rgn);

//2. 判断区域B是否在区域A内部
template 
bool isRgnInRgn(const std::vector > &rgnB, 
				const std::vector > &rgnA);

使用时包含下面的头文件，然后直接调用函数即可

/*
	利用射线法判断某一点/一个区域 是否属于 另一区域
	2011 3 29 http://blog.lyqx.de/?p=592
*/

#ifndef IS_POINT_IN_RGN
#define IS_POINT_IN_RGN

#include 
#include 

template 
struct mVector //代表一个向量或一个坐标点
{
public:
	T x,y;

	mVector()
		: x(0),y(0)
	{}

	mVector(T a,T b)
	{
		set(a,b);
	}

	void set(T a,T b)
	{
		x=a;
		y=b;
	}

	//向量相加
	mVector add(const mVector &right)const
	{
		return mVector(x+right.x, y+right.y);
	}

	//向量相减
	mVector minus(const mVector &right)const
	{
		return mVector(x-right.x, y-right.y);
	}

	//向量点乘
	T multipy(const mVector &right)const
	{
		return x*right.x + y*right.y;
	}

	//判断两个向量是否平行 0--不平行 1--平行且方向相同 2--平行且方向相反
	int isParallel(const mVector &right)const
	{
		if(x*right.y == y*right.x) //平行
		{
			if(x) //x!=0
			{
				if(right.x/x >= 0) return 1;
				else return -1;
			}
			else //x==0
			{
				if(y)
				{
					if(right.y/y >= 0) return 1;
					else return -1;
				}
				else {return 1;}
			}
		}

		return 0;
	}

	//判断两个向量是否相交
	bool isIntersect(const mVector &right)const
	{
		return ! isParallel(right);
	}

	//判断两个向量是否垂直
	bool isPerpendicular(const mVector &right)const
	{
		return !(this->multipy(right));
	}

	//获取向量的长度
	double getLength()const
	{
		return std::sqrt(double(x*x + y*y));
	}
};

//获取一组点中的下一个点
template 
T getNextPoint(const std::vector &rgn, size_t index)
{
	if(index == rgn.size()-1 ) return rgn.at(0);
	else return rgn.at(index+1);
}

//获取一组点中的上一个点
template 
T getPrevPoint(const std::vector &rgn, size_t index)
{
	if(0 == index) return rgn.at(rgn.size()-1);
	else return rgn.at(index-1);
}

//获取向量的垂直方向 -1--向上 1--向下 0--水平
template 
int getVectorDirect(const mVector &vec)
{
	if(vec.y > 0) return -1;
	else if(vec.y <0) return 1;
	else return 0;
}

//判断点point是否在区域rgn内部 1--内部 -1--边界 0--外部
template 
int isPointInRgn(const mVector &point, const std::vector > &rgn)
{
	int num1=0, num2=0;
	for(std::vector >::size_type index=0; index != rgn.size(); index++ )
	{
		mVector nextPoint = getNextPoint(rgn,index);

		if(rgn[index].x		else if(nextPoint.minus(point).isParallel( point.minus(rgn[index]) ) == 1)
		{
			return -1;//点在边界
		}
		else if(point.y == rgn[index].y) //射线经过边界点
		{	
			mVector prevVector = rgn[index].minus(getPrevPoint(rgn,index)), 
					   nextVector = getNextPoint(rgn,index).minus(rgn[index]);

			num2 += getVectorDirect(prevVector) + getVectorDirect(nextVector);
			
			
		}
		else if( (point.y > rgn[index].y && point.y < nextPoint.y)
			|| (point.y > nextPoint.y && point.y < rgn[index].y) )
		{
			++num1;
		}
		else {}//射线不经过边界线段
	}

	if((num1 + num2/2)%2) return 1;//奇数
	else return 0;
}

//判断区域B是否在区域A内部
template 
bool isRgnInRgn(const std::vector > &rgnB, const std::vector > &rgnA)
{
	for(std::vector >::size_type index = 0;
		index != rgnB.size(); index++)
	{
		if(! isPointInRgn(rgnB[index], rgnA) ) return false;
	}

	return true;
}

#endif //IS_POINT_IN_RGN

使用方法演示

#include "isPointInRgn.h"
#include 
#include 

int main()
{
	double x1,y1;

	std::vector > borderA,borderB;

	std::ifstream finA("in1.txt"), finB("in2.txt");

	while(finA>>x1>>y1)
	{
		borderA.push_back(mVector(x1,y1) );
	}

	while(finB>>x1>>y1)
	{
		borderB.push_back(mVector(x1,y1) );
		
	}
	
	std::cout<}

其中in1.txt 和 in2.txt 为输入文件，内容如下

0 0
0 1
0 2
0 3
1 3
2 3
2 2
3 2
4 2
4 3
5 3
5 2
5 1
5 0

1 1
1 2
2 3
2 1

如果发现代码bug请在本页留言

代码下载：http://bit.ly/isPointInRegion
参考文章：判断区域B是否在区域A内部的快速算法 - xiaotie - 博客园