给定N个点的坐标,这N个点依次围成一闭合多边形,再给一点(X,Y),判断它是否在多边形中.

[ 本帖最后由 我是会飞的鱼 于 2014-11-5 16:29 编辑 ]

给定N个点的坐标 ----- 可得 n*(n-1)*(n-2)/6 个三角形
判断(X,Y)是否在其中一个三角形内

当然，这其中还有一个无解的大问题，比如4个点，可以有不同的“围成一闭合多边形”，不知道你怎么想的。

我有一个程序感觉不对

描述中说了是“依次”，所以连接顺序是给定的，图形是唯一的。

判断一个点在多边形内还是外有一条推理：过一点做任意一条射线，如果该射线与多边形边的交点数量为奇数，则该点在多边形内；如果为偶数则在多边形外。

还有一个方法编程比较容易，但效率不如上面的：以该点到多边形上依次相邻两点形成一个夹角，以点的顺序作为角的方向。所有夹角的和为2PI时点在多边形内（上），为0时在多边形外。

能具体点吗? 这个程序运行出来是说能不能构成多边形，感觉与题意不符啊。
#include<iostream.h>
 const int N=4;
 int tt(double p[][2],int a,int b)  
{  
int temp[N],k=0;double t;
for(int i=0;i<N;i++)
{if(i==a||i==b)
{ continue;}  
t=p[i][0]*(p[b][1]-p[a][1])+(p[a][0]-p[b][0])*p[i][1]-p[a][0]*p[b][1]+p[b][0]*p[a][1];
if(t==0) return 0;
 else  if(t>0) temp[k++]=1;
 else  temp[k++]=-1;}
for(int j=1;j<k;j++)  
{if(temp[0]!=temp[j]) return 0;}
 return 1;}
 int    real(double p[][2])
 { int flag[N],m=0; for(int i=0;i<N;i++){flag[i]=0;}
 for( i=0;i<N;i++)
{
for(int j=1;j<N;j++)
 {
if(flag[j]) continue;
if(tt(p,m,j))
{
 flag[m]=1; m=j;break; }
 }
}
flag[m]=1;
 for(i=0;i<N;i++)  
{
if(flag[i]==0) return 0;
}  
 if(tt(p,0,m)) return 1;
return 0;}
void main()
{double p[N][2];
char ch='y';   
while (ch=='y'||ch=='Y')
 {cout<<"请输入点的坐标:"<<endl;
for(int i=0;i<N;i++)  
{cout<<" 下一个点坐标:";cin>>p[i][0]>>p[i][1];cout<<p[i][0]<<","<<p[i][1]<<endl;}  
if (real(p))cout<<"能构成";else cout<<"不能构成";

谢谢，确实是这样，厉害

但是 不对啊，最后程序运行出来是判断能不能构成多边形

就是这样。。