计算几何问题，基本思想从要判断的点引一条射线看和多边形交点的个数，如果是奇数个，那么就在多边形内，否则在多边形外。先判断点是否在多边形边上的情况判掉，再判断线段相交。
复制代码
#include <iostream>
#include <vector>
using namespace std;
const int MAXSIZE = 100;
const double Max = 100000000;
struct Point
{
double x;
double y;
}points[MAXSIZE];
Point pc;//选择的射线点
double CrossMultiply(const Point& a,const Point& b,const Point& c)
{//叉乘
double x1,y1,x2,y2;
x1= b.x - a.x;
y1 = b.y - a.y;
x2 = c.x - b.x;
y2 = c.y - b.y;
return x1 * y2 - x2 * y1;
}
double interSect(const Point& a,const Point& b,const Point& c,const Point& d)
{
double d1,d2,d3,d4;
d1 = CrossMultiply(a,b,c),
d2 = CrossMultiply(a,b,d),
d3 = CrossMultiply(c,d,a),
d4 = CrossMultiply(c,d,b);
if((d1 * d2) < 0 && (d3 * d4) < 0)
return 1.;
else if((d1 * d2) == 0 || (d3 * d4) == 0)
return 0;
else
return -1.;
}
bool IsOnEdge(const Point& p,const vector<Point>& ptVect)
{//点是否在边上
int i,j,size,minX,maxX,minY,maxY;
size = ptVect.size();//点的数目
for (i=0;i<size;++i)
{
j= i+1;
if (j==size)
{
j=0;
}
if (CrossMultiply(ptVect[i],ptVect[j],p)==0)
{//在同一直线上
if (p.x>=min(ptVect[i].x,ptVect[j].x)&&p.x<=max(ptVect[i].x,ptVect[j].x)&&p.y>=min(ptVect[i].y,ptVect[j].y)&&p.y<=max(ptVect[i].y,ptVect[j].y))
{//在线段内
return true;
}
}
}
return false;
}
bool isInside(const Point& p,const vector<Point>& ptVect)
{//判断点是否在多边形内部
int i,j,num,size;
double d;
num = 0; //射线与线段相交的点的个数
size = ptVect.size();
for(i = 0 ; i <size; ++i)
{ //处理每条线段
j= i+1;
if (j==size)
{
j=0;
}
d = interSect(p,pc,ptVect[i],ptVect[j]);
if(d > 0)
num++; //严格相交
else if(d == 0)
{ //有一端点在另一直线上
if(ptVect[i].y > 0 || ptVect[j].y > 0)
num++;
}
}
if(num % 2 == 0)
return false;
else
return true;
}
int main(void)
{
int N,M,i,pX,pY,cases=0;
while (cin>>N&&N!=0)
{
cin>>M;
if(cases != 0)
cout << endl;
vector<Point> pointVect;
for (i=0;i<N;++i)
{
cin>>points[i].x>>points[i].y;
pointVect.push_back(points[i]);
}
cout << "Problem " << ++cases<< ":" << endl;
for (i=0;i<M;++i)
{
Point p;
cin>>p.x>>p.y;
pc.x = Max,pc.y = p.y;//故意把射线点选择在同一水平线，无穷远处
if (IsOnEdge(p,pointVect))
{//在一条边上
cout<<"Within"<<endl;
continue;
}
else if (isInside(p,pointVect))
{//在多边形内部
cout<<"Within"<<endl;
}
else
{
cout<<"Outside"<<endl;
}
}
}
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/10/30/1323289.html，如需转载请自行联系原作者
