ZOJ1081 Points Within-白红宇

计算几何问题，基本思想从要判断的点引一条射线看和多边形交点的个数，如果是奇数个，那么就在多边形内，否则在多边形外。先判断点是否在多边形边上的情况判掉，再判断线段相交。

复制代码

#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，如需转载请自行联系原作者