单域单向水平倾角最小化圈绕凸壳新算法的编程实现.docx

单域单向水平倾角最小化圈绕凸壳新算法的编程实现

单域单向水平倾角最小化圈绕凸壳算法，是本创新研究团队提出的凸壳新算的最早者之一。单域单向水平倾角最小化圈绕凸壳新算法的C++编程实现示例，其关键部分代码可简要列示如下：

#include
#include
struct Point /*定义点的结构*/
{
/*x坐标*/
float x；
/*y坐标*/
float y；
/*到最近找到的外点（最近外点）倾角的正弦*/
float sin；
/*离最近外点倾角大小排序名次*/
int order；
distance； /*离最近外点的距离*/
float
type； /*凸壳图形中点的类型：-1：待定；=0：外点；=1：内点*/
int
direction； /*=1：离最近外点的倾角0-90度；=2：离最近外点的倾角90-180度；=3：离最近外点
int
的倾角180-270度4：离最近外点的倾角270-360度；*/
}；
void SinAndDirection（float x1，float y1，float x2，float y2，float *sinOfPitch，int *direction，float *distance）；
/*int IsInTriangle（float x1，float y1，float x2，float y2，float x3，float y3，float x4，float y4）；
/*IsInTriangle判断（x4，y4）是否在（x2，y2），（x2，y2），（x2，y2）所组成的三角形内部*/
int main（）{
int i，j；
/*p指向凸壳图形中点数组的首地址*/
struct Point *p；
/*endFlag结束标志，=1表示问题已经解决*/
int endFlag=0；
/*tempOrder与最近外点倾角大小的排序名次临时变量*/
int tempOrder；
int firstPoint，secondPoint； /*最近找到的2个外点的序号*/
int numOfOut=0； /*找到的外点的个数*/
/*在所有与最近外点的倾角最小的点中，maxDistancePoint是离最近外点距离最
int maxDistancePoint；
大的点的序号*/
/*找最近外点水平基线倾角最小的点中使用的临时变量*/
float minSin；
float maxDistance； /*找离最近外点距离最大的点中使用的临时变量*/
int minDirection； /*最近外点水平基线倾角最小的点相对于最近外点的象限*/
/*判定一个待定点是否在最近找到的2个外点和最低顶点构成三角形的内部的标志*/
int inTriangle；
unsigned int pNum； /*pNum表示凸壳图形中点的个数*/
printf（"Please input the number of point："）；
scanf（"%u"，&pNum）； /*输入平面中点的个数pNum*/
printf（"\n"）； getchar（）；
p=（struct Point *）calloc（pNum+1，sizeof（struct Point））；/*为pNum个点分配存储空间*/
…… /*空间分配失败处理，已从略*/
…… /*输入各个点的坐标（x，y），并置结点类型type
为-1*/
/*顺序查找法查找Y坐标最小的结点序号lowPoint */
lowPoint = 1；
for（i=2；i<=pNum；i++）
if（p[i].y < p[lowPoint].y）lowPoint = i；
firstPoint=lowPoint； /*lowPoint作为找到的第一个外点*/
p[firstPoint].type=0；
/*numOfOut是找到的外点的个数*/
numOfOut=1；
printf（"%10d ：（%10 while（endFlag==0）{
endFlag=1；
tempOrder=0；
/*计算第一个待定点到最近外点firstPoint的距离、sin、象限，
并求minSin、minDirection*/
……. /*其处理，已从略*/
/*计算其余待定点到最近外点firstPoint的距离、sin、象限，并求minSin、minDirection*/
for（i=j+1；i<=pNum；i++）{
p[i].order=0；
if（i!=firstPoint&&p[i].type==-1）
{ endFlag=0；/*置结束标志位*/
SinAndDirection（p[firstPoint].x，p[firs &（p[i].distance））；
if（p[i].direction （p[i].direction==1 || p[i].direction==3）|| p[i].sin>minSin && p[i].direction==inDirection &&
（p[i].direction==2 || p[i].direction==4））
{ minSin=p[i].sin；
minDirection=p[i].direction；
p[i].order=++tempOrder；
}
if（p[i].si /*问题求解结束*/
if（endFlag==1）break；
/*在所有与最近外点的倾角最小的点中，求最近外点距离最大的点的序号maxDistancePoint*/
maxDistance=0；
for（i=1；i<=pNum；i++）{
if（p[i].order==tempOrder&&p[i].type==-1）
{ p[i].type=0；
if（p[i].distance-maxDistance>=0）
{ maxDistancePoint=i；maxDistance=p[i].distance；}
}
}
numOfOut++；
p[maxDistancePoint].type=0；/*置外点标志*/
if（numOfOut==2）
{ firstPoint=maxDistancePoint；
printf（"%10d：（%10.2f，%10.2f）\n"，firstPoint，p[firstPoint].x，p[firstPoint].y）；
}
else if（numOfOut>2）
{ thirdPoint=secondPoint；
secondPoint=firstPoint；
firstPoint=maxDistancePoint；
printf（"%10d ：（%10.2f，%10.2f）\n"，firstPoint，p[firstPoint].x，p[firstPoint].y）；
for（i=1；i<=pNum；i++）{/*排除最低点和最近两外点所成三角形各点，置内点标志*/
if（p[i].type==-1）
{ inTriangle=IsInTriangle（p[firstPoint].x，p[firstPoint].y， p[secondPoint].x，p[secondPoint].y，
p[lowPoint].x，p[lowPoint].y，p[i].x，p[i].y）；
if（inTriangle==1）p[i].type=1； /*置内点标志*/
}
}
}
}
free（p）；
}
int IsInTriangle（float x1，float y1，float x2，float y2，float x3，float y3，float
x4，float y4） {/*利用三线法判定一个点（x4，y4）是否在（x1，y1），（x2，y2），（x3，y3）所组
成的三角形中*/
float t1，t2，t3，t4，t5，t6；
t1=（y2-y1）*（x4-x1）+（x1-x2）*（y4-y1）； t2=（y2-y1）*（x3-x1）+（x1-x2）*（y3-y1）；
t3=（y3-y1）*（x4-x1）+（x1-x3）*（y4-y1）； t4=（y3-y1）*（x2-x1）+（x1-x3）*（y2-y1）；
t5=（y3-y2）*（x4-x2）+（x2-x3）*（y4-y2）；void SinAndDirection（float x1，float y1，float x2，float y2，
float *sinOfPitch，int *direction，float *distance）{
float disX，disY； /*disX表示两点的X△，disY表示两点的Y*/△
disX=x2-x1；disY=y2-y1；
if（disX>=0&&disY>=0） /*（X2，Y2）点相对于（X1，Y1）点在第一象限*/
*direction=1；
else if（disX<=0&&disY>=0） /*（X2，Y2）点相对于（X1，Y1）点在第二象限*/
*direction=2；
else if（disX<=0&&disY<=0） /*（X2，Y2）点相对于（X1，Y1）点在第三象限*/
*direction=3；
else if（disX>=0&&disY<=0） /*（X2，Y2）点相对于（X1，Y1）点在第四象限*/
*direction=4；
*distance=sqrt（disX*disX+disY*disY）； /**distance表示（X2，Y2）点到（X1，Y1）的距离*/
*sinOfPitch=fabs（disY）/（*distance）； /**sinOfPitch表示（X2，Y2）点与（X1，Y1）点水平基线的
倾角的sin值*/}

（本文档由缩阴产品 整理发布，版权原作者所有）