Question

速求 c语言编程 给定n个点的坐标，这n个点依次围成一闭合多边形，再给一点（x，y），判断它是否在多边形中

Answer 1

程序代码如下（直接套用函数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)在多边形外，如果是奇数，则在多边形内。

Answer 2

#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;
}

Answer 3

#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...

Answer 4

不知道有没有这个定理，画图看出来的？ 由n个点确定的n边型，将x,y代入每条边的方程，1）点不在线上时，如果fn(x,y)>0的真值为偶数，则点在多边形内。2）点在线上时点必在多边形上。

Answer 5

代码就不写了，我说下自己的思路吧：
可以定好3个点得坐标（因为要构成闭合的图形，至少得3个点才行）
分别计算出每两个点的直线方程，如果点得个数大于3，则根据每两个相距最近的点连成直线
然后还是求出该直线方程
判断要判断的点是否在线上，还是左右侧等……
根据这个去编程写代码，我觉得是可以实现的，还有就是n个点的个数，可以先定下来，当然也可以先初始化一个值，然后递增。