c.c

《并行算法实践》附带的mpi源程序

#include <stdio.h>
#include <mpi.h>
#include <math.h>

int my_rank,group_size,sub_group;
int n_all;
double pointx[30],pointy[30];
double tempx[2],tempy[2],xtemp[4],ytemp[4];
MPI_Status status;
int location[30];

/*获得y坐标最小的点,坐标值保存到保存到tempx,tempy数组中*/
void getymin( )
{
    int i,index=0;
    double tempvalue=pointy[0];

    for(i=1;i<n_all;i++)
    {
        if(pointy[i]<tempvalue)
        {
            tempvalue=pointy[i];
            index=i;
        }
        else
        {
			/*若y坐标相同,则取x坐标小者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
            if(pointy[i]==tempvalue)
                if(pointx[index]>pointx[i])
                    index = i;
        }
    }
    tempx[0]=pointx[index];
    tempy[0]=pointy[index];

	/*如果y坐标最小的极点只有1点,就复制该点*/
    tempx[1]=tempx[0];
    tempy[1]=tempy[0];

	/*考察极点是否多于1点*/
    for(i=0;i<n_all;i++)
        if((pointy[i]==tempy[1])&&(pointx[i]>tempx[1]))
    {
		/*极点多于1点,取x坐标大者,保存最后一个极点的坐标*/
        tempx[1]=pointx[i];
        tempy[1]=pointy[i];
    }
    return;
}


/*获得y坐标最大的点,保存到tempx,tempy数组中*/
void getymax()
{
    int i,index=0;
    double temp=pointy[0];

    for(i=1;i<n_all;i++)
    {
        if(pointy[i]>temp)
        {
            temp=pointy[i];
            index=i;
        }
        else
        {
			/*若y坐标相同,则取x坐标大者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
            if(temp==pointy[i])
                if(pointx[i]>pointx[index])
                    index=i;
        }
    }
	/*保存YMAX极点坐标*/
    tempx[0]=pointx[index];
    tempy[0]=pointy[index];

	/*如果y坐标最大的极点只有1点,就复制该点*/
    tempx[1]=tempx[0];
    tempy[1]=tempy[0];

	/*考察极点是否多于1点*/
    for(i=0;i<n_all;i++)
    {
        if((pointy[i]==tempy[1])&&(pointx[i]<tempx[1]))
        {
			/*极点多于1点,取x坐标小者,保存最后一个极点的坐标*/
            tempx[1]=pointx[i];
            tempy[1]=pointy[i];
        }
    }

    return;
}


/*获得x坐标最小的点,坐标保存到tempx,tempy数组中*/
void getxmin()
{
    int i,index=0;
    double temp=pointx[0];

    for(i=1;i<n_all;i++)
    {
        if(pointx[i]<temp)
        {
            temp=pointx[i];
            index=i;
        }
        else
        {
			/*若x坐标相同,则取y坐标大者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
            if(pointx[i]==temp)
                if(pointy[index]<pointy[i])
                    index=i;
        }
    }
	/*保存XMIN极点坐标*/
    tempx[0]=pointx[index];
    tempy[0]=pointy[index];

	/*如果x坐标最小的极点只有1点,就复制该点*/
    tempx[1]=tempx[0];
    tempy[1]=tempy[0];

	/*考察极点是否多于1点*/
    for(i=0;i<n_all;i++)
    {
        if((pointx[i]==tempx[1])&&(pointy[i]<tempy[1]))
        {
			/*极点多于1点,取y坐标小者,保存最后一个极点的坐标*/
            tempx[1]=pointx[i];
            tempy[1]=pointy[i];
        }
    }
    return;
}


/*获得x坐标最大的点,其坐标值保存保存到tempx,tempy数组中*/
void getxmax()
{
    int i,index=0;
    double temp=pointx[0];

    for(i=1;i<n_all;i++)
    {
        if(pointx[i]>temp)
        {
            temp=pointx[i];
            index=i;
        }
        else
        {
			/*若x坐标相同,则取y坐标小者。这是为了保证(tempx[0],tempy[0])->(tempx[1],tempy[1])为逆时针方向*/
            if(temp==pointx[i])
                if(pointy[index]>pointy[i])
                    index=i;
        }
    }
	/*保存XMAX极点坐标*/
    tempx[0]=pointx[index];
    tempy[0]=pointy[index];

	/*如果x坐标最大的极点只有1点,就复制该点*/
    tempx[1]=tempx[0];
    tempy[1]=tempy[0];

	/*考察极点是否多于1点*/
    for(i=0;i<n_all;i++)
    {
        if((pointx[i]==tempx[1])&&(pointy[i]>tempy[1]))
        {
			/*极点多于1点,取y坐标大者,保存第2个极点的坐标*/
            tempx[1]=pointx[i];
            tempy[1]=pointy[i];
        }
    }
    return;
}


/*temp[x],temp[y]设置两个值的作用是为了有多个最值时，保存首尾两个，后面划分
区域时分别以这两个为端点，中间就没有其他的点了*/

/*确定是属于哪一部分*/
void getincludedvertex(int tag)
{
    double linea,lineb,dist;
    int i,count=0;

	/*若该边已退化成一个点, 则除此点外无其它点在处理区域内*/
    if((tempx[1]==tempx[0])&&(tempy[1]==tempy[0]))
    {
        n_all=1;
        pointx[0]=tempx[1];
        pointy[0]=tempy[1];
    }
    else
    {
		/*根据两端点坐标确定直线的斜率和参数*/
        linea=(tempy[1]-tempy[0])/(tempx[1]-tempx[0]);
        lineb=tempy[1]-linea*tempx[1];
		/*根据点在直线的哪一侧来确定该顶点是否在处理区域内*/
        for(i=0;i<n_all;i++)
        {
            dist=linea*pointx[i]+lineb-pointy[i];
            if(tag*dist<0)
            {
                pointx[count]=pointx[i];
                pointy[count++]=pointy[i];
            }
        }
		/*调整各点的位置以加入两个端点*/
        for(i=0;i<count;i++)
        {
            pointx[count-i]=pointx[count-1-i];
            pointy[count-i]=pointy[count-1-i];
        }
		/*将两个端点放在两端*/
        pointx[0]=tempx[0];
        pointy[0]=tempy[0];
        pointx[count+1]=tempx[1];
        pointy[count+1]=tempy[1];
        count+=2;
		/*更新n_all为要处理的新的表列中的点的数量*/
        n_all=count;
    }
}


/*确定此点的后一点的序号，并放入location[]中*/
void nextindex(int i,int x,int y)
{
    double x1,y1,temp,valuemax=0;
    int j;

    x1=pointx[i];
    y1=pointy[i];

	/*遍历各顶, 将有最小极角点的序号作为自己的Nextindex值*/
    for(j=0;j<n_all;j++)
    {
        if(((pointx[j]-x1)*x+(pointy[j]-y1)*y)>0)
        {
			/*由极角的余弦或其余角的正弦来判断极角大小*/
            temp=((pointx[j]-x1)*x+(pointy[j]-y1)*y)/(sqrt((pointx[j]-x1)*(pointx[j]-x1)+(pointy[j]-y1)*(pointy[j]-y1)));
            if(temp>valuemax)
            {
                location[i]=j;
                valuemax=temp;
            }
        }
    }
    if(valuemax==0)
        location[i]=-1;
}


/*输出点的序列*/
void output(int rank)
{
    int j=0,index,temp;
    double xtem,ytem;
    int flag=0;

    printf("输出的是第%d部分的点\n",rank/sub_group);
    if(rank==0)
        flag=1;
    if(flag==0)
        if(!((pointx[n_all-1]==tempx[0])&&
        (pointy[n_all-1]==tempy[0])))
            flag=1;

	/*将nextindex反向,使输出的点按逆时针方向,以保证各行主处理器输出顺序相邻*/
    index=location[j];
    while(location[index]!=-1)
    {
        temp=location[index];
        location[index]=j;
        j=index;
        index=temp;
    }
    location[index]=j;
    location[0]=-1;

	/*按照索引顺序输出各点*/