Question

问题 输入N个点的坐标，判断这N个点能否构成一个凸多边形 求下面这个程序的 设计思路以及问题分析..

#include<stdio.h>
#define N 4
int tt(int p[][2],int a,int b)
{
int temp[N],k=0;
int t;
int i;
int j;
for(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(j=1;j<k;j++)
{
if(temp[0]!=temp[j]) return 0;
}
return 1;
}
int real(int p[][2])
{
int flag[N],m=0;
int i,j;
for(i=0;i<N;i++)
{
flag[i]=0;
}
for( i=0;i<N;i++)
{
for(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()
{
int p[N][2];
int i;
printf("请输入这N个点坐标:\n");
for(i=0;i<N;i++)
{
printf("第%d个点坐标:",i+1);
scanf("%d,%d",&p[i][0],&p[i][1]);
printf("%d,%d\n",p[i][0],p[i][1]);
}
if (real(p))
printf("能构成凸多边形");
else
printf("不能构成凸多边形!!!");
} 希望大神们不要搞雷同~ 谢谢各位啦 发邮箱 445946583的QQ邮箱 写的好的话追加10分

Answer 1

多边形点集 = {P1,P2,P3,P4.....Pn}

多边形所有点满足 点(Pn-3),点(Pn)在线段(Pn-2,Pn-1)的同侧

多边形是凸多边形，否则为凹多边形。

这个函数判断点c在线段ab的左边还是右边，如果返回值大于0在左边，如果小于0在右边，否则共线
double left_right(point a,point b,point c)

{

a.x-=c.x; a.y-=c.y;

b.x-=c.x; b.y-=c.y;

return a.x*b.y-a.y*b.x;

}

c# ：
public partial class Form2 : Form
{
public Form2()
{
InitializeComponent();
}
List<Point> lstPoint = new List<Point>();

private void label1_MouseClick(object sender, MouseEventArgs e)
{
lstPoint.Add(new Point(e.X, e.Y));
listBox1.Items.Add(string.Format("({0},{1})",e.X,e.Y));
}

private void button1_Click(object sender, EventArgs e)
{
lstPoint.Clear();
listBox1.Items.Clear();
Graphics g = label1.CreateGraphics();
g.Clear(label1.BackColor);
}

double left_right(Point a, Point b, Point c)
{
a.X -= c.X; a.Y -= c.Y;
b.X -= c.X; b.Y -= c.Y;
return a.X * b.Y - a.Y * b.X;
}

//删除同线点的中间点点 ...

//判断是否凸变形
bool is_tu()
{
int icount = lstPoint.Count;
if (icount < 3) return false;//数量不足
Point a, b, c;
for (int i = 0; i < icount; i++)//
{
a = lstPoint[i];
for (int j = i + 1; (j < icount)||(i==icount-1 && j==icount); j++)
{
b = lstPoint[j%icount];
//从下一个点开始找；找所有点都在同一侧；
bool bFind = true;
double dFirst = 0, dOther;
for (int k = 1; k < icount; k++)
{
if ((j + k) % icount == i) continue; //对比时跳过a点
c = lstPoint[(j + k) % icount];
if (dFirst == 0)
{
dFirst = left_right(a, b, c);
}
else
{
dOther = left_right(a, b, c);
if (dFirst * dOther < 0)
{
bFind = false;
break;
}
}
}
//如果找到，则交换点，检查是否完成
if (i + 1 == icount) { return bFind; }//搜索完最后一个点，返回结果
//
if (bFind)
{
//if (j == icount) { return false; }//在a点没到最后，仅有第一点符合b点要求，变成需要交换已完成搜索，返回非
if (j > i + 1)
{
lstPoint[j] = lstPoint[i + 1];
lstPoint[i + 1] = b;
}
break;
}
else//找不到，返回非
{
if (j == icount -1) { return false; }//遍历完最后的点，仍没有
}
}
}
return false;//逻辑上不会执行到这里
}

private void button2_Click(object sender, EventArgs e)
{
Graphics g = label1.CreateGraphics();
Pen p = new Pen(Color.Black, 1);
SolidBrush brush = new SolidBrush(Color.Red);

if (is_tu())
{
g.DrawString("是凸边形", label1.Font, brush, new PointF(100, 0));
}
else
{
g.DrawString("不是凸边形", label1.Font, brush, new PointF(100, 0));
}
for (int i = 0; i < lstPoint.Count; i++)
{
g.DrawLine(p, lstPoint[i], lstPoint[(i + 1) % lstPoint.Count]);
}
}
}