如题所述
程序代码如下(直接套用函数pnpoly):
int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
参数说明:
nvert: 多边形的顶点数
vertx, verty: 顶点X坐标和Y坐标分别组成的数组
testx, testy: 需要测试的点的X坐标和Y坐标
扩展资料:
判定一个点是否在多边形内部最简单的方法是使用射线法,因为它能适用于所有类型的多边形,不用考虑特殊的情况而且速度也比较快。
该算法的思想很简单:在多边形外面任意一点画一条虚拟的射线到p(x,y)然后计算该射线与多边形上的边相交的次数。如果该次数是偶数,说明p(x,y)在多边形外,如果是奇数,则在多边形内。
温馨提示:答案为网友推荐,仅供参考
第1个回答 推荐于2017-12-16
#include<stdio.h>
#include<math.h>
#include<string.h>
#define esp 1e-8
#define N 30
int dy(double x,double y) { return x > y + esp;}// x > y
int xy(double x,double y) { return x < y - esp;}// x < y
int dyd(double x,double y) { return x > y - esp;}// x >= y
int xyd(double x,double y) { return x < y + esp;}// x <= y
int dd(double x,double y) { return fabs( x - y ) < esp;}// x == y
double max(double x,double y)
{
if(dy(x,y))return x;
return y;
}
double min(double x,double y)
{
if(xy(x,y))return x;
return y;
}
struct point
{
double x,y;
};
double xmult(point a,point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int onSegment(point a,point b,point c)
{
if(dd(xmult(a,b,c),0.0)&& dyd(c.x,min(a.x,b.x)) && xyd(c.x,max(a.x,b.x)) &&
dyd(c.y,min(a.y,b.y)) && xyd(c.y,max(a.y,b.y)))
return 1;
return 0;
}
int is_Cross(point a,point b,point c,point d)
{
double d1=xmult(c,d,a);
double d2=xmult(c,d,b);
double d3=xmult(a,b,c);
double d4=xmult(a,b,d);
if(xy(d1*d2,0.0) && xy(d3*d4,0.0))return 1;
if(dd(d1,0.0) && onSegment(c,d,a) || dd(d2,0.0) && onSegment(c,d,b)
|| dd(d3,0.0) && onSegment(a,b,c) || dd(d4,0.0) && onSegment(a,b,d) )
return 1;
return 0;
}
int point_inPolygon(point po,point p[],int n)
{
point a=po,b;
b.x=1e20; b.y=po.y;
p[n]=p[0];
int i,cnt=0;
for(i=0;i<n;i++)
{
//点 po 在多边形某条边上
if(onSegment(p[i],p[i+1],po)) return 1;
//点 po 不在多边形边上
if( !dd(p[i].y,p[i+1].y) )//平行的边不考虑
{
//判断 p[i],p[i+1]两点是否在a,b上
int tmp=-1;
if( onSegment(a,b,p[i]) ) tmp=i;
else if( onSegment(a,b,p[i+1]) ) tmp=i+1;
//对于多边形的顶点和射线a,b相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略
if( tmp!=-1 && dd(p[tmp].y,max(p[i].y,p[i+1].y)) || tmp==-1 && is_Cross(p[i],p[i+1],a,b) )
cnt++;
}
}
return cnt%2==1;
}
int main()
{
int i,n,m,time=1,blank=0;
point po,p[N];
while(scanf("%d",&n),n)
{
scanf("%d",&m);
memset(p,0,sizeof(p));
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
if(!blank) blank=1;
else puts("");
printf("Problem %d:\n",time++);
for(i=1;i<=m;i++)
{
scanf("%lf%lf",&po.x,&po.y);
if( point_inPolygon(po,p,n) ) printf("Within\n");
else printf("Outside\n");
}
}
return 0;
}本回答被提问者采纳
#include<math.h>
#include<string.h>
#define esp 1e-8
#define N 30
int dy(double x,double y) { return x > y + esp;}// x > y
int xy(double x,double y) { return x < y - esp;}// x < y
int dyd(double x,double y) { return x > y - esp;}// x >= y
int xyd(double x,double y) { return x < y + esp;}// x <= y
int dd(double x,double y) { return fabs( x - y ) < esp;}// x == y
double max(double x,double y)
{
if(dy(x,y))return x;
return y;
}
double min(double x,double y)
{
if(xy(x,y))return x;
return y;
}
struct point
{
double x,y;
};
double xmult(point a,point b,point c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int onSegment(point a,point b,point c)
{
if(dd(xmult(a,b,c),0.0)&& dyd(c.x,min(a.x,b.x)) && xyd(c.x,max(a.x,b.x)) &&
dyd(c.y,min(a.y,b.y)) && xyd(c.y,max(a.y,b.y)))
return 1;
return 0;
}
int is_Cross(point a,point b,point c,point d)
{
double d1=xmult(c,d,a);
double d2=xmult(c,d,b);
double d3=xmult(a,b,c);
double d4=xmult(a,b,d);
if(xy(d1*d2,0.0) && xy(d3*d4,0.0))return 1;
if(dd(d1,0.0) && onSegment(c,d,a) || dd(d2,0.0) && onSegment(c,d,b)
|| dd(d3,0.0) && onSegment(a,b,c) || dd(d4,0.0) && onSegment(a,b,d) )
return 1;
return 0;
}
int point_inPolygon(point po,point p[],int n)
{
point a=po,b;
b.x=1e20; b.y=po.y;
p[n]=p[0];
int i,cnt=0;
for(i=0;i<n;i++)
{
//点 po 在多边形某条边上
if(onSegment(p[i],p[i+1],po)) return 1;
//点 po 不在多边形边上
if( !dd(p[i].y,p[i+1].y) )//平行的边不考虑
{
//判断 p[i],p[i+1]两点是否在a,b上
int tmp=-1;
if( onSegment(a,b,p[i]) ) tmp=i;
else if( onSegment(a,b,p[i+1]) ) tmp=i+1;
//对于多边形的顶点和射线a,b相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略
if( tmp!=-1 && dd(p[tmp].y,max(p[i].y,p[i+1].y)) || tmp==-1 && is_Cross(p[i],p[i+1],a,b) )
cnt++;
}
}
return cnt%2==1;
}
int main()
{
int i,n,m,time=1,blank=0;
point po,p[N];
while(scanf("%d",&n),n)
{
scanf("%d",&m);
memset(p,0,sizeof(p));
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
if(!blank) blank=1;
else puts("");
printf("Problem %d:\n",time++);
for(i=1;i<=m;i++)
{
scanf("%lf%lf",&po.x,&po.y);
if( point_inPolygon(po,p,n) ) printf("Within\n");
else printf("Outside\n");
}
}
return 0;
}本回答被提问者采纳
第2个回答 2012-02-26
#include <stdio.h>
#include <stdlib.h>
#define MAX_POINT 100
double px[MAX_POINT], py[MAX_POINT]; //n个点的坐标
int n;
double x, y;
//输入n个点和,x,y
void input()
{
int i;
printf("Input n: \n");
scanf("%d", &n);
printf("Input %d points's coordinate: \n", n);
for (i = 0; i < n; i++)
scanf("%lf %lf", px + i, py + i);
printf("Input the point's x and y:\n");
scanf("%lf %lf", &x, &y);
}
//计算两个向量(a,b),(c,d)的叉乘
double muti(double a, double b, double c, double d)
{
return b * c - a * d;
}
int judge()
{
int flag; //判断该点在边的左端还是右端
int tmp, i;
tmp = muti(px[1] - px[0], py[1] - py[0], x - px[0], y - py[0]);
if (tmp > 0) flag = 1;
else if (tmp < 0) flag = -1;
else return 0;
for (i = 2; i < n; i++)
{
tmp = muti(px[i] - px[i - 1], py[i] - py[i - 1],
x - px[i - 1], y - py[i - 1]);
tmp *= flag;
if (tmp <= 0) return 0;
}
return 1;
}
int main()
{
input();
if (judge())
printf("Yes.\n");
else printf("No.\n");
return 0;
}
这个代码的主要大意就是,如果这个点在多边形里面,那么沿着多边形走,这个点一直会在左边或一直在右边。2个向量的叉乘就是计算向量的位置是在左边还是右边。输入有要求,即:1、n至少为3,至少得为三角形吧,2、这n个点必须按多边形顺时针或逆时针依次输入,3、这个多边形必须是凸多边形。本人由于做过和这类似的acm题目,因此此题不是问题。
示例输入:
Input n:
5
Input 5 points's coordinate:
1 2
2 1
3 1
4 2
3 3
Input the point's x and y:
1 1
No.
Hit any key to close this window...
#include <stdlib.h>
#define MAX_POINT 100
double px[MAX_POINT], py[MAX_POINT]; //n个点的坐标
int n;
double x, y;
//输入n个点和,x,y
void input()
{
int i;
printf("Input n: \n");
scanf("%d", &n);
printf("Input %d points's coordinate: \n", n);
for (i = 0; i < n; i++)
scanf("%lf %lf", px + i, py + i);
printf("Input the point's x and y:\n");
scanf("%lf %lf", &x, &y);
}
//计算两个向量(a,b),(c,d)的叉乘
double muti(double a, double b, double c, double d)
{
return b * c - a * d;
}
int judge()
{
int flag; //判断该点在边的左端还是右端
int tmp, i;
tmp = muti(px[1] - px[0], py[1] - py[0], x - px[0], y - py[0]);
if (tmp > 0) flag = 1;
else if (tmp < 0) flag = -1;
else return 0;
for (i = 2; i < n; i++)
{
tmp = muti(px[i] - px[i - 1], py[i] - py[i - 1],
x - px[i - 1], y - py[i - 1]);
tmp *= flag;
if (tmp <= 0) return 0;
}
return 1;
}
int main()
{
input();
if (judge())
printf("Yes.\n");
else printf("No.\n");
return 0;
}
这个代码的主要大意就是,如果这个点在多边形里面,那么沿着多边形走,这个点一直会在左边或一直在右边。2个向量的叉乘就是计算向量的位置是在左边还是右边。输入有要求,即:1、n至少为3,至少得为三角形吧,2、这n个点必须按多边形顺时针或逆时针依次输入,3、这个多边形必须是凸多边形。本人由于做过和这类似的acm题目,因此此题不是问题。
示例输入:
Input n:
5
Input 5 points's coordinate:
1 2
2 1
3 1
4 2
3 3
Input the point's x and y:
1 1
No.
Hit any key to close this window...
第3个回答 2012-02-25
不知道有没有这个定理,画图看出来的? 由n个点确定的n边型,将x,y代入每条边的方程,1)点不在线上时,如果fn(x,y)>0的真值为偶数,则点在多边形内。2)点在线上时点必在多边形上。
第4个回答 2012-02-24
代码就不写了,我说下自己的思路吧:
可以定好3个点得坐标(因为要构成闭合的图形,至少得3个点才行)
分别计算出每两个点的直线方程,如果点得个数大于3,则根据每两个相距最近的点连成直线
然后还是求出该直线方程
判断要判断的点是否在线上,还是左右侧等……
根据这个去编程写代码,我觉得是可以实现的,还有就是n个点的个数,可以先定下来,当然也可以先初始化一个值,然后递增。
可以定好3个点得坐标(因为要构成闭合的图形,至少得3个点才行)
分别计算出每两个点的直线方程,如果点得个数大于3,则根据每两个相距最近的点连成直线
然后还是求出该直线方程
判断要判断的点是否在线上,还是左右侧等……
根据这个去编程写代码,我觉得是可以实现的,还有就是n个点的个数,可以先定下来,当然也可以先初始化一个值,然后递增。