//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
{
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 - 博客园
