《数据结构与算法实训》
实训报告
题 目：凸多边形直径计算研究与实现 完 成 人： 专业班级： 学 号： 指导教师：
年
月
日
广西科技大学计算机学院
计算机学院 班 数据结构与算法实训报告 题目：凸多边形直径计算研究与实现
说明：1.请按实训要求完成实训任务，鼓励提出自己的算法，或是在已有算法基础上进行改进，以提高计算速度；2.程序代码不能低于500行；3.每位同学须完成实训报告，并打印上交；4.每位同学须参加实训答辩。5.答辩成绩占40％，平时成绩占30％，文档书写占30％。 1.生成一个凸多边形
1.1生成来自同一个圆上的点集
阶段一（一次）
对于同一个圆上的点集，按顺时针（逆时针）顺序依次连接这些顶点，即可得到一个凸多形。
思考：是否可以通过随机生成圆上的点，来得到凸多边形的顶点集？ 参考代码：
void generate_circle_points(int n,int seed) { double theta; double temp_x,temp_y; int i; srand(seed); for (i = 1; i
temp_x = cos(theta); temp_y = sin(theta); Point[i][0]=temp_x*350+500; Point[i][1]=temp_y*250+300; } Point[0][0]=Point[n][0]; Point[0][1]=Point[n][1]; } 完成后的截图示例：
图1 生成圆上的点
1.2编程实现已有的凸壳（凸包）算法
阶段二（两次）
利用中国知网下载凸壳（凸包）计算的相关文献，任选择一篇文献编程实现；也可从图书馆查阅相关书籍，寻找简单的凸壳（凸包）计算的方法，编程实现。
完成后的截图示例：
图2 凸壳计算
2.实现文献中的凸多边形直径计算
3 阶段三（三次）
要求编程实现指定文献[1]中的凸多边形直径计算算法。 完成后的截图示例：
图3 待计算的点集
图4 凸多边形直径值
3.利用数据结构中的算法对文献中的方法进行改进
阶段四（两次）：上交改进算法的思想。 阶段五（两次）：实现改进算法。 实验对比
为验证本文算法有效性，进行了大量实验，算法均能正确地计算出凸多边形直径，并分别与文献[1]、[2]、[3]、[4]进行对比实验，实验表
4 明，算法稳定性好，运行效率高。同时为验证本文对找首个对跖点对算法改进的有效性，与文献[1]、[4]算法进行了实验对比，结果表明，算法非常有效，运行效率非常高。限于篇幅，这里仅举出其中一例。该例实验的方法是通过随机函数自动生成以半径为250个象素宽的圆周上的点，点坐标值采用浮点型，则以这些点所构成的多边形必定是凸多边形，测得对比实验运行时间如表1所示，单位为1/10000秒。 4.撰写实训报告
阶段六（一次）：撰写并上交实训报告。
一、本文涉及的知识点有：
宏定义、全局变量、二维数组、一维数组、for循环、自定义头文件、指针
二、功能要求：
1、生成来自同一个圆上的点集
对于同一个圆上的点集，按顺时针（逆时针）顺序依次连接这些顶点，即可得到一个凸多形。
2、实现文献中的凸多边形直径计算，还要包括计算其运行时间。
3、算法设计
void sift(double A[],int s, int m) { //输出以A[m]为根节点的子树为堆
double t; int j; t=A[s]; j=2*s ; while(j
A[s]=A[j];
s=j;
j=2*j; } else
j=m+1; } A[s]=t; }
void heapsort(double A[],int n) { /*A是待排序数组（从下标1开始存储，最大元素下标为n），n为数组的元素的个数*/
int i,k; double temp; k=n/2; for(i=k;i>0;i--) //无序序列建堆
sift(A,i,n); for(i=n;i>1;i--) { //堆顶元素换到最后
temp=A[1];
A[1]=A[i];
A[i]=temp;
sift(A,1,i-1); //调整 建堆
} }
void generate_circle_points(int n,int seed) { //随机生成圆上的点
double angle[MaxLen+1]; double temp_x,temp_y;
int i,k; CString str;
srand(seed);
for (i = 1; i
angle[i] = ((double)rand() / RAND_MAX) * 2 * PI; /*将圆随机的生成圆上点*/
for (k = 1; k
{
if(angle[k]==angle[i] || angle[k]==angle[i]+ 2*PI || angle[k]+
6 2*PI==angle[i]) //将重复的点去掉
{
i--;
break;
}
} }
heapsort(angle,n);
for (i = 1; i
temp_x = cos(angle[i]);
temp_y = sin(angle[i]);
Point[i][0]=temp_x*200+400;
Point[i][1]=temp_y*200+400; }
Point[0][0]=Point[n][0]; Point[0][1]=Point[n][1]; Point[n+1][0]=Point[1][0]; Point[n+1][1]=Point[1][1]; }
double Calculate_Maxdist(int n) { //计算凸多边形上最远的两点的距离
int i=0,j=1,k,antips[MaxLen][2],ant=0,l,pi,pj; double pd,d,dc; while((Point[i+1][0]-Point[i][0])*(Point[j+1][1]-Point[j][1])-(Point[i+1][1]-Point[i][1])*(Point[j+1][0]-Point[j][0]) >0 ) //当其面积之差大于0时
j++; k=j; while ( !(i==k && j==n) ) {
dc=(Point[i+1][0]-Point[i][0])*(Point[j+1][1]-Point[j][1])- (Point[i+1][1]-Point[i][1])*(Point[j+1][0]-Point[j][0]);/*计算其两三角形的面积之差*/
if ( dc
{
i++;
antips[ant][0]=i;
antips[ant++][1]=j;
}
else if ( dc>0 )
{
j++;
antips[ant][0]=i;
antips[ant++][1]=j;
}
else
i++; } pd=-1; for(l=0;l
pi=antips[l][0];
pj=antips[l][1];
d=(Point[pi][0]-Point[pj][0])*(Point[pi][0]-Point[pj][0])+ (Point[pi][1]-Point[pj][1])*(Point[pi][1]-Point[pj][1]);
if ( d>pd )
pd=d; } return sqrt(pd); //返回计算结果 }
void CConvexDiameterView::OnDraw(CDC* pDC) { /*画出生成来自同一个圆上的点集
按顺时针（逆时针）顺序依次连接这些顶点，即可得到一个凸多形。*/
CConvexDiameterDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); CClientDC pa(this); //自定义一个(this)指针
OnPrepareDC (& pa); // TODO: add draw code for native data here if(liulang==1) {
int i;
for(i=0;i
pDC->Ellipse(Point[i][0]+4,Point[i][1]+4,Point[i][0]-4,Point[i][1]-4);
CString pajiho;
pajiho.Format(_T(\"%d\"),i+1); //输出点的序号
pa.TextOut(Point[i][0],Point[i][1],pajiho);
for(int j=0;j
{
if(i>0)
{
//顺序两点相连
pa.MoveTo(Point[i-1][0],Point[i-1][1]);
pa.LineTo(Point[i][0],Point[i][1]);
//任意两点相连
// pa.LineTo(Point[j][0],Point[j][1]);
}
}
}
liulang=0; } //起点和末点链接
pa.MoveTo(Point[MaxLen-1][0],Point[MaxLen-1][1]); pa.LineTo(Point[0][0],Point[0][1]); }
void CConvexDiameterView::OnAngleSign() { // TODO: Add your command handler code here double Maxdis; generate_circle_points(MaxLen,100);/* 生成圆形上数据,第二参数为随机函数的种子*/
clock_t start_time, finish_time; //用于测试时间
double during_time=0.0; start_time = clock();
for(int i=0;i
Maxdis=Calculate_Maxdist(MaxLen);
finish_time= clock(); during_time=((double)(finish_time-start_time)/ CLOCKS_PER_SEC)/xunhuancishu*10000; CString str; str.Format(\"所花费的时间是%lf(万分之一秒)\",during_time); AfxMeageBox(str);
str.Format(\"最大距离为：%lf\",Maxdis); AfxMeageBox(str);
liulang=1;
9 Invalidate(); UpdateWindow();
}
运行结果：
三、实训总结：
由于本次实训采用MFC编程，我对MFC完全没有一丁点的了解，更不知如何使用。但我通过上网搜索来MFC来有了一点了解，MFC的内容非常多，用起来相当不容易。对于随机画圆的部分，我不是很明白，x坐标y坐标的表示等等。在参考了老师的源程序之后，虽然有了一些认识，但由于初次接触这样的实训，还是有些模糊。
