左转算法C++实战

admin1

1，  选择顶点，遵循着根据结点编号从小到大的顺序选取。

2，  选取起始边，选择方位角最小的边作为起始边，其次选取使用过一次的边作为起始边。

3，  选取后续边，若当前边的方位角不是与该结点有关边的方位角最大的边，则逆时针选取与当前边夹角最小的边作为后续边（体现左转原则），否则（即使方位角最大边），则选取方位角最小的边作为后续边。

4，  回到原点，构建一个多边形。

备注：一条边有两方向，可作为两条边使用。

==================================================================================================

其中很折腾人的一个问题是在多边形拓扑中存在岛的问题，一下是岛的检测和解决思路

1，  计算多边形面积，面积为负的是岛。并形成正多边形几何和负多边形集合。

2，  依次从正多边形集合中取出一个多边形，对应的遍历所有负多边形，如果包含（首先要负多边形面积（绝对值）小于正多边形的面积，其次，判断两个最小外界矩形是否相交，如果相交，则取负多边形上任意一点判断是否位于正多边形内部，是，则包含，否则，不包含），则将二者复合为复杂多边形，并从负多边形集合中删除该负多边形。

3，  步骤2中，若负多边形集合中个数为1时（只剩下最大的边界负多边形），则结束，或者若正多边形都遍历结束，则结束。

==================================================================================================

具体的实现流程：

1，  基于左转算法进行，左转算法具体思路详见同期实验报告9.GIS算法实验报告_多边形拓扑。.gen文件读取参考第5周的方法并稍作修改，使其能够根据用户指定输入读取文件，而无需通过修改代码实现读取不同文件的功能。下面具体描述如何将左转算法转换为计算机程序的过程。

2，  预备知识：区分节点，结点的关系。在左转算法中，节点定义为与其相关点数目有且只有两个的点，显然节点只会出现在弧端的中间，不可能存在弧端的首尾。结点则是节点的补充，定义为关联点的数目至少有三个的点。在算法中，将节点作为基类，也就是说节点包含结点，再从中筛选出结点。

3，  定义几个数据结构：点，线，面。其关系与几何中的相似。

4，  获取节点。通过读取.gen文件获取点与点之间的关系，以线段为依托。初始化节点数据结构，遍历每条线段上的每个点，并根据改点去文件中匹配，获取其前后点，也就是步骤2中所说的关联点。遍历完成后，即获得了节点信息，并通过判断节点的关联点的数量，确定哪些为结点。

5，  完善结点。通过结点的关联点搜寻其所在的弧端，知道遇到另一个结点为止。

6，  构建多边形。根据左转算法的内涵：确定选择起始点方式的优先性（方位角最小的，相反边被使用过一次的），确定选择后续边方式的优先性（若当前边为目标结点的方位角最大的边的相反边，则后续边为该结点的方位角最小的边，否则，按逆时针规则选取）。

7，岛的监测。对于到的情况，本算法不同于左转算法，是根据已建立的数据结构来监测岛存在的。在步骤4，5构建节点和结点时，对关联点只有两个的点要做进一步处理：初始化一个岛链数据结构，可理解为边，给该节点定义一个初始方向，及从该节点的两个关联点钟选择一个点作为tobuild，判断tobuild是否为节点，是则将该节点写入岛链的数据结构中，并选择tobuild的另一个节点（一个节点已处理了）作为下次判断的tobuild；若判断结果为否，销毁岛链数据结构，完成对该点的监测，不可能为岛。形成岛链的条件是，tobuild的点与岛链的起始点相匹配。

// TurnLeft.cpp : 定义控制台应用程序的入口点。
//
//点分为点，节点，结点三种：
//点具有点必须具备的位置信息（x,y），POINT
//节点是在点的基础上拓展的，附加与其相关联的点信息，可通过附加点的数量判断是否为结点，NODE
//结点是具有3个及以上的附加点的点，NODE_ARC

#include "stdafx.h"
#include "math.h"
#include <iostream>
#include <algorithm>  
#include <string>
#include <vector>
#include <gl/glut.h>
#include <vector>
#pragma comment(lib,"glut32.lib")
using namespace std;
#define Length 22
#define pi 3.1415926

//点结构体
typedef struct POINT{
        double x;
        double y;
}point;

//节点结构体
typedef struct NODE{
        point centre;
        vector<point> points;
}node;

//arc,边由首尾结点及若干各个中间节点组成组成，含方向性
typedef struct ARC{
        int id;  //弧端编号
        vector<point> points;
        bool used;
}arc;

//node-arc,结点-边的关系
typedef struct NODE_ARC{
        int id;  //结点编号
        vector<arc> index;  //根据方位角从小到大排列与结点有关的边
}node_arc;

//polygon-arc
typedef struct POLYGON_ARC{
        int polygonid;
        vector<arc> index;  //弧端的矢量存储
}polygon_arc;

//gen struct
typedef struct VectorLine{
        int id;
        double **location;
}vectorline;

//传入结构体变量和存储信息的数组
double **createlocation(int n)
{
        //开辟动态数组
        double **location = (double **)malloc(sizeof(double*)*n);
        for (int j = 0; j < n; j++)
        {
                location[j] = (double *)malloc(sizeof(int)*2);
        }
        return location;
}

void gen_reader(VectorLine gen[],int info[],string filename)
{
        FILE *fp;
        //读取gen文件
        //注意此处的路径方式,相对路径
        string directory="..//"+filename;
        if ((fp = fopen(directory.c_str(), "r")) == NULL)
        {
                printf("Canot Open this file!");
                exit(EXIT_FAILURE);
        }
        else
        {
                //temp variable to store the line id
                char temp[40];

                //读取所有的数据信息
                for(int i=0;i<Length;i++)
                {
                        VectorLine arc;
                        //编号
                        fscanf(fp, "%d", &arc.id);

                        fscanf(fp,"%s",&temp);

                        int flag=0;

                        //直到读取END结束本次读取
                        while(temp[0]<59&&temp[0]>=49)
                        {
                                flag++;
                                fscanf(fp,"%s",&temp);
                        }

                        //给存储.gen文件的数组赋值
                        info[i]=flag;
                }
                //关闭读文件流
                fclose(fp);
        }

        //再次读取文件信息
        //存储信息
        if ((fp = fopen(directory.c_str(), "r")) == NULL)
        {
                printf("Canot Open this file!");
                exit(EXIT_FAILURE);
        }
        else
        {
                //temp variable to store the line id
                char temp[40];

                //遍历所有数据
                for(int i=0;i<Length;i++)
                {
                        //读取ID编号
                        fscanf(fp, "%d", &gen[i].id);

                        //根据第一次读文件获取的块的大小动态开辟数组存储位置信息
                        gen[i].location=createlocation(info[i]);

                        //读取该ID下的点位信息
                        for (int m = 0; m < info[i]; m++)
                        {
                                //数据读取存在误差
                                fscanf(fp, "%s", &temp);
                                char *p;
                                //通过，将经纬度分开
                                p=strtok(temp,",");
                                //存储经度
                                gen[i].location[m][0]=atof(p);
                                p=strtok(NULL,",");
                                //存储纬度
                                gen[i].location[m][1]=atof(p);
                        }
                        fscanf(fp,"%s",&temp);
                }
                //关闭文件读取流
                fclose(fp);
        }
}

//寻找一个中心点的前继点集和后点集
void Ahead_After(VectorLine gen[],int info[],point center,vector<point> &ahead,vector<point> &after)
{
        int i,j;
        for(i=0;i<Length;)
        {
                for(j=0;j<info[i];j++)
                {
                        //匹配该点，通过i,j确定位置
                        while((gen[i].location[j][0]==center.x) && (gen[i].location[j][1]==center.y))
                        {
                                //寻找前继点，前继点存在
                                if((j-1)>=0)
                                {
                                        point bridge={gen[i].location[j-1][0],gen[i].location[j-1][1]};
                                        ahead.push_back(bridge);  //添加到前继点矢量集合中
                                }
                                //寻找后继点，后几点存在
                                if((j+1)<info[i])
                                {
                                        point bridge={gen[i].location[j+1][0],gen[i].location[j+1][1]};
                                        after.push_back(bridge);  //添加到继点矢量集合中
                                }
                                goto number1;  //每个弧端中最多只有一个相同的点，当完成while(..)时可之间跳转至下一个弧端
                        }
                }
                number1:i++;  //GOTO 语句
        }
}

//已经出现过，返回false,否则返回true
bool NotEquation(vector<node>been,point temp)
{
        for(int i=0;i<been.size();i++)
        {
                if((been[i].centre.x==temp.x) && (been[i].centre.y==temp.y))
                {
                        return false;
                }
        }
        return true;
}

//构建边
void BuildArc(vector<node> Junction,point hasbuild,point tobuild,vector<point> &newpoint)
{
        int i,j,k;
        point bridge;
        for(i=0;i<Junction.size();i++)
        {
                //在Junction中寻找附加点作为中心点时的位置
                if((tobuild.x==Junction[i].centre.x) && tobuild.y==Junction[i].centre.y)
                {
                        //该附加点为中心点
                        if(Junction[i].points.size()==2)
                        {
                                //该点为弧端上的节点
                                //bridge.push_back(Junction[i].centre);
                                newpoint.push_back(Junction[i].centre);

                                //对该点的另一附加点继续判断
                                //寻找另一个节点，排出已遍历过的点
                                if((Junction[i].points[0].x==hasbuild.x) && (Junction[i].points[0].y==hasbuild.y))
                                {
                                        BuildArc(Junction,tobuild,Junction[i].points[1],newpoint);
                                }
                                else
                                {
                                        BuildArc(Junction,tobuild,Junction[i].points[0],newpoint);
                                }
                        }
                        //该附加点为结点
                        else
                        {
                                //将该点作为结点，存储边的信息
                                //bridge.points.push_back(Junction[i].centre);
                                newpoint.push_back(Junction[i].centre);
                                return;  //提前结束
                        }
                }
        }
}

//若building与已构建的岛状部分匹配则返回true,否则返回false
bool Repeat(vector<arc> Island,vector<point> building)
{
        int i,j;

        for(i=0;i<Island.size();i++)
        {
                //有一个点能够匹配即可，安全吗？
                for(j=0;j<Island[i].points.size();j++)
                {
                        if(building.size()>1)
                        {
                                //防止出现一个点视为首尾相连的情况，采用第二个点
                                if((building[1].x==Island[i].points[j].x)&(building[1].y==Island[i].points[j].y))
                                {
                                        return true;
                                }
                        }
                }
        }
        return false;
}

//构建岛
void BuildIsland(vector<node> Junction,vector<arc> Island,point hasbuild,point tobuild,vector<point> &newpoint)
{
        int i,j,k;
        point bridge;
        //若出现部分匹配则结束，防止可能出现的同一岛重复存储的现象
        if(Repeat(Island,newpoint))
        {
                newpoint.erase(newpoint.begin(),newpoint.end());
                return;
        }
               
        //若首尾元素相同，则结束
        if(newpoint[0].x!=tobuild.x | newpoint[0].y!=tobuild.y)
        {
                for(i=0;i<Junction.size();i++)
                {
                        //在Junction中寻找附加点作为中心点时的位置
                        if((tobuild.x==Junction[i].centre.x) && tobuild.y==Junction[i].centre.y)
                        {
                                //该附加点为中心点
                                if(Junction[i].points.size()==2)
                                {
                                        newpoint.push_back(Junction[i].centre);
                                        //对该点的另一附加点继续判断
                                        //寻找另一个节点，排出已遍历过的点
                                        if((Junction[i].points[0].x==hasbuild.x) && (Junction[i].points[0].y==hasbuild.y))
                                        {
                                                BuildIsland(Junction,Island,tobuild,Junction[i].points[1],newpoint);
                                        }
                                        else
                                        {
                                                BuildIsland(Junction,Island,tobuild,Junction[i].points[0],newpoint);
                                        }
                                }
                                else
                                {
                                        newpoint.erase(newpoint.begin(),newpoint.end());
                                }
                                break;
                        }
                }
        }
}

//计算方位角，逆时针方向0-360°
void  PositionAngle(vector<arc> &onenode)
{
        int i,j;
        //传入的可能是折线,只对开始两个点组成的线段进行计算
        vector<double>angle;
        for( i=0;i<onenode.size();i++)
        {
                double dety=onenode[i].points[1].y-onenode[i].points[0].y;
                double detx=onenode[i].points[1].x-onenode[i].points[0].x;
                double degree=atan(dety/detx)*180/pi;  //弧度制
                //90-180
                if(detx<0 & dety>=0)
                {
                        degree+=180;
                }
                //180-270
                else if(detx<0 &dety<0)
                {
                        degree+=180;
                }
                //270-360
                else if(detx>=0 & dety<0)
                {
                        degree+=360;
                }
                angle.push_back(degree);
        }

        for(i=0;i<onenode.size();i++)
        {
                for(j=i+1;j<onenode.size();j++)
                {
                        //交换位置
                        if(angle[i]>angle[j])
                        {
                                swap(angle[i],angle[j]);  //方位角交换位置
                                swap(onenode[i],onenode[j]);
                        }
                }
        }
}

//Node_Arc，获取结点-边的关系，island提前存储岛状信息
void Node_Arc(VectorLine gen[],int info[],vector<node_arc> &nodearc,vector<arc> &island)
{
        int i,j,k,m,n;
        n=0;
        vector<node> Junction; //节点
        for(i=0;i<Length;i++)
        {
                for(j=0;j<info[i];j++)
                {
                        //当与一个点关联的边在3个以上时才能定义为结点，否则为节点
                        point center={gen[i].location[j][0],gen[i].location[j][1]};  //中心点位信息
                        if(!NotEquation(Junction,center))
                        {
                                continue;
                        }
                        vector<point> ahead;
                        vector<point> after;
                        Ahead_After(gen,info,center,ahead,after);  //寻找前继点，后继点
                        ahead.insert(ahead.end(),after.begin(),after.end());
                        node bridge={center,ahead};
                        Junction.push_back(bridge);
                }
        }

        for(i=0,k=0,m=0;i<Junction.size();i++)
        {
                //附加点个数在3及三个以上时认定为结点
                if(Junction[i].points.size()>=3)
                {
                        //vector<vector<arc>> sameid;
                        vector<arc> sameid;
                        //对该点的所有附加点进行遍历，寻找其对应的边
                        for(j=0;j<Junction[i].points.size();j++)
                        {
                                //构建边
                                //vector<arc> singlearc;     //一个附加点对应一条边
                                vector<point> newpoint;  //一条边由多个点组成
                                point bridge={Junction[i].centre.x,Junction[i].centre.y};  //起始点为该中心点
                                newpoint.push_back(bridge);

                                //arc bridge_1={newpoint};
                                //singlearc.push_back(bridge_1);  //边开始的点为该中心点
                                BuildArc(Junction,Junction[i].centre,Junction[i].points[j],newpoint);  //添加边的后续点
                                arc bridge_1={m,newpoint,false};
                                sameid.push_back(bridge_1);  //debug
                                m++;  //m为弧端编号
                        }
                        PositionAngle(sameid);   //排序，结果为按方位角从小到大的顺序边
                        node_arc bridge_2={k,sameid};  //同一ID,下有多条边
                        nodearc.push_back(bridge_2);  //对应第一个点为该结点的点
                        k++;
                }//endif 寻找节点
               
                //组成到的节点的特征在能够不经过节点的情况下回溯到自身，其所遍历的点组成了岛
                else
                {
                        //岛链
                        vector<point> chain;
                        //起始点为本身
                        chain.push_back(Junction[i].centre);

                        //所关联的点不是是结点，可能构成岛
                        BuildIsland(Junction,island,Junction[i].centre,Junction[i].points[0],chain);  //以第一个关联点作为开始<<Bug？
                        if(chain.size()!=0)
                        {
                                arc singleisland={n,chain,false};
                                island.push_back(singleisland);
                                n++;
                        }
                }
        }      
}

//判断两条边是否反向，反向返回true，否则返回false
bool Reversion(arc base,arc tocheck)
{
        int i;
        //如果两条弧端大小不同，则不可能相同
        if(base.points.size()!=tocheck.points.size())
        {
                return false;
        }
        else
        {
                for(i=0;i<base.points.size();i++)
                {
                        //相反元素不相同，其位置和为size()-1，直接返回
                        if((base.points[i].x!=tocheck.points[base.points.size()-1-i].x) | (base.points[i].y!=tocheck.points[base.points.size()-1-i].y))
                        {
                                return false;
                        }
                }
                return true;
        }
}

//判断两条边是否相等,相等返回true,否则返回false
bool Samearc(arc base,arc tocheck)
{
        int i;
        //如果两条弧端大小不同，则不可能相同
        if(base.points.size()!=tocheck.points.size())
        {
                return false;
        }
        else
        {
                for(i=0;i<base.points.size();i++)
                {
                        //相同位置的值不相同
                        if((base.points[i].x!=tocheck.points[base.points.size()-1-i].x) | (base.points[i].y!=tocheck.points[base.points.size()-1-i].y))
                        {
                                return false;
                        }
                }
                return true;
        }
}

//判断是否是最大边，是返回true,否则返回
bool Max(vector<node_arc> nodearc,arc ending)
{
        int i,j;
        for(i=0;i<nodearc.size();i++)
        {
                for(j=0;j<nodearc[i].index.size();j++)
                {
                        //找到该弧端结束的结点
                        if((ending.points[ending.points.size()-1].x==nodearc[i].index[0].points[0].x )
                                & (ending.points[ending.points.size()-1].y==nodearc[i].index[0].points[0].y))  //每个结点对应的关联的边的首个点就是该结点的位置
                        {
                                //当前弧端是结束结点的最大弧端
                                if(Samearc(ending,nodearc[i].index[nodearc[i].index.size()-1]))  //parameter type error?
                                {
                                        return true;
                                }
                        }
                }
        }
        return false;
}

//将弧端写入多边形框架下的vector<arc>
void Arcmeet(arc &towrite,vector<arc> &box)
{
        //写入
        box.push_back(towrite);
        //修改使用情况，？？？修改成功？
        towrite.used=true;
}

//寻找弧端位置，返回指针,ij[0]表示节点位置，ij[1]表示弧端在节点中的位置
int *Location(vector<node_arc> nodearc,int m,int n)
{
        int ij[2];
        int u,v;
        //寻找到结束点的位置，并修改i,j
        for(u=0;u<nodearc.size();u++)
        {
                if(nodearc[u].index[0].points[0].x==nodearc[m].index[n].points[nodearc[m].index[n].points.size()-1].x
                        & nodearc[u].index[0].points[0].y==nodearc[m].index[n].points[nodearc[m].index[n].points.size()-1].y)
                {
                        ij[0]=u;
                        break;
                }
        }
        for(v=0;v<nodearc[u].index.size();v++)
        {
                if(Reversion(nodearc[m].index[n],nodearc[u].index[v]))
                {
                        ij[1]=v;
                        break;
                }
        }
        return ij;
}

//判断某条边的反向边是否被使用过，使用过返回true,否则返回false
bool Usage(vector<node_arc> nodearc,int m,int n)
{
        int i,j;
        //对结点遍历
        for(i=0;i<nodearc.size();i++)
        {
                //对结点中每条边遍历
                for(j=0;j<nodearc[i].index.size();j++)
                {
                        //反向
                        if(Reversion(nodearc[i].index[j],nodearc[m].index[n]))
                        {
                                //使用过
                                if(nodearc[i].index[j].used)
                                {
                                        return true;       
                                }
                        }
                }
        }
        return false;
}

//判断某个结点是否全部使用，是返回true,否则返回false
bool Nodeuse(vector<node_arc> nodearc,int i,int j)
{
        int *temp=Location(nodearc,i,j);
        //对向外的弧端和向内的弧端都遍历
        for(int m=0;m<nodearc[i].index.size();m++)
        {
                if(nodearc[i].index[m].used==false)
                        return false;
                if(!Usage(nodearc,i,m))
                        return false;
        }
}

//判断所有结点是否都被使用，是返回true,否则返回false
bool Alluse(vector<node_arc> nodearc)
{
        for(int i=0;i<nodearc.size();i++)
        {
                for(int j=0;j<nodearc[i].index.size();j++)
                {
                        //存在没被使用过的
                        if(!nodearc[i].index[j].used)
                                return false;
                }
        }
        return true;
}

//若相关边未使用过，且反向边已使用过，则返回true,否则返回false
bool Priority2(vector<node_arc> nodearc,int i,int &j)
{
        for(j=1;j<nodearc[i].index.size();j++)
        {
                if(Usage(nodearc,i,j) & !nodearc[i].index[j].used)
                        return true;
        }
        return false;
}

//Polygon_Arc，获取多边形-边的关系
void Polygon_Arc(vector<node_arc> &nodearc,vector<polygon_arc> &polygonarc)
{
        int i,j,k,m,n,u,v;
        //按从小到大的顺序选择结点,i 结点编号，j对应结点的弧端编号，k多边形编号
        for(i=0,j=0,k=0;i<nodearc.size();)
        {
                //存储同一个多边形的多条边
                vector<arc> bridge;
                //如果全部使用过，则调至下个结点
number2:
                if(Alluse(nodearc))
                {
                        break;
                }
                if(Nodeuse(nodearc,i,j))
                {
                        i++;
                        goto number2;
                }
                //选择方位角最小的边，优先性最高
                int *modify=&j;
                if(nodearc[i].index[0].used==false) //方位角最小的边存在
                {
                        Arcmeet(nodearc[i].index[j],bridge);
                        int *temp=Location(nodearc,i,j);
                        i=temp[0],j=temp[1];
                        goto number3;
                }
                //对所有剩余点选择已使用过一次的边，优先性其次，应当将方位角最小的排除在外
                else if(Priority2(nodearc,i,*modify))
                {
                        Arcmeet(nodearc[i].index[*modify],bridge);
                        int *temp=Location(nodearc,i,*modify);
                        i=temp[0],j=temp[1];
                        goto number3;
                }
                //上述条件不符合，优先性最后
                else
                {
                        Arcmeet(nodearc[i].index[j],bridge);
                        int *temp=Location(nodearc,i,j);
                        i=temp[0],j=temp[1];
                        goto number3;
                }

number3://判断进入的边是否是Max
                        if(j==nodearc[i].index.size()-1)
                        {
                                Arcmeet(nodearc[i].index[0],bridge);
                                int *temp=Location(nodearc,i,0);
                                i=temp[0],j=temp[1];
                        }
                        //逆时针寻找
                        else
                        {
                                Arcmeet(nodearc[i].index[j+1],bridge);
                                int *temp=Location(nodearc,i,j+1);
                                i=temp[0],j=temp[1];
                        }

                        //判断是否回到起点
                        if((bridge[bridge.size()-1].points[bridge[bridge.size()-1].points.size()-1].x==bridge[0].points[0].x)
                                &&(bridge[bridge.size()-1].points[bridge[bridge.size()-1].points.size()-1].y==bridge[0].points[0].y))
                        {
                                //完成多边形的构建，结束本次构建
                                polygon_arc onepolygon={k,bridge};
                                polygonarc.push_back(onepolygon);
                                k++;//k为多边形编号
                                continue;
                        }
                        //继续进行选择
                        else
                        {
                                goto number3;
                        }//endif
        }//end circulation i  for every node
}//endfuction

int _tmain(int argc,char* argv[])
{
        number4:
        printf("请输入文件序号（1,2,3,以回车键结束）：\n");
        int number;
        string filename;
        scanf("%d",&number);
        switch(number){
        case 1:filename="PlyBuild_1_arc.gen";break;
        case 2:filename="PlyBuild_2_arc.gen";break;
        case 3:filename="PlyBuild_3_arc.gen";break;
        default:cout<<"illegal filenumber"<<endl;
        }

        VectorLine *Gen=(VectorLine *)malloc(sizeof(VectorLine)*Length);
        int *Info = (int *)malloc(sizeof(int)*Length);
        gen_reader(Gen,Info,filename);
        vector<node_arc> Nodearc;
        vector<arc> Island;
        Node_Arc(Gen,Info,Nodearc,Island);  //节点-边关系表OK

        vector<polygon_arc>Polygonarc;
        Polygon_Arc(Nodearc,Polygonarc);  //多边形-边关系表

        //输出
        printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n");
        printf("包含的多边形:\n");
        for(int i=0;i<Polygonarc.size();i++)
        {
                printf("%d:\n",Polygonarc[i].polygonid);
                for(int j=0;j<Polygonarc[i].index.size();j++)
                {
                        for(int k=0;k<Polygonarc[i].index[j].points.size();k++)
                        {
                                printf("%lf\t%lf\n",Polygonarc[i].index[j].points[k].x,Polygonarc[i].index[j].points[k].y);
                        }
                }
        }
        printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n");
        printf("包含的岛\n");
        for(int i=0;i<Island.size();i++)
        {
                printf("%d:\n",Island[i].id);
                for(int j=0;j<Island[i].points.size();j++)
                {
                        printf("%lf\t%lf\n",Island[i].points[j].x,Island[i].points[j].y);
                }
        }
        system("pause");
        return 0;
}