jarris.txt

点集凸包( 收缩法)Jarris步进法

#include <iostream>     //给定点集合，求包罗所有点的最小凸包。(Jarris步进法) 

  

#include <fstream>      //n 为总点数，x,y是坐标。             (即收缩法) 

#include <deque>        //tx,ty是求出的逆时针凸包坐标。 

#include <math.h>       //坐标以0起始。 

                        //使用条件： 1。点可以任意给，可重复。 

using namespace std;    // 2。三个以及以上的点。 

                        // 3。已经考虑了边上有点的情况。 

ifstream fin("maxconvexpolygon.in"); 

void out(); 

void go(); 

double mytan(double y,double x); 

void in(); 

double dist (double x1,double y1,double x2,double y2); 

#define NN 1000 

#define pi 3.1415927 

int n,flag[NN]; 

double x[NN],y[NN]; 

deque <double> tx,ty; 

int main() 

{ 

    in(); 

    go(); 

    out(); 

    return 0; 

} 

void out() 

{ 

    int i; 

    for (i=0;i<tx.size();i++) 

        cout<<tx<<" "<<ty<<endl; 

    cout<<tx.size()<<" Edges Convex Polygon."<<endl; 

    return; 

} 

void go() 

{ 

    int i,j,k,mm; 

    double nk1,nk2,flag2; 

    memset(flag,0,sizeof(flag)); 

    mm=0; 

    for (i=1;i<n;i++) 

        if (y[mm]>y+1e-9) mm=i; 

        else if (fabs(y[mm]-y)<1e-9 && x[mm]>x+1e-9) mm=i; 

    tx.clear(); 

    ty.clear(); 

    tx.push_back(x[mm]); 

    ty.push_back(y[mm]); 

    flag[mm]=1; 

    nk1=-1.0; 

    j=mm; 

    for(;;){ 

        flag2=0; 

        for (i=0;i<n;i++){ 

            double tg,yyy,xxx; 

            yyy=y-y[j]; 

            xxx=x-x[j]; 

            tg=mytan(yyy,xxx); 

            //  printf ("i=%d  tg=%lf  xx=%lf 

yy=%lf\n",i,tg*180/pi,xxx,yyy); 

            if ( (tg>nk1+1e-9&& (!flag2||nk2>tg+1e-9)) 

                || 

            (flag2 && fabs(tg-nk2)<1e-9&& 

dist(x[j],y[j],x[k],y[k])+1e-9<dist(x[j],y[ 

j],x,y)) )  { 

                nk2=tg; 

                k=i; 

                flag2=1; 

            } 

        } 

        nk1=nk2; 

        if (fabs(x[k]-x[mm])<1e-9 && fabs(y[k]-y[mm])<1e-9) return; 

        tx.push_back(x[k]); 

        ty.push_back(y[k]); 

        j=k; 

    } 

    return ; 

} 

double dist (double x1,double yy1,double x2,double yy2) 

{ 

    return pow((x1-x2)*(x1-x2)+(yy1-yy2)*(yy1-yy2),0.5); 

} 

double mytan(double y,double x) 

{ 

    double red; 

    double red; 

    if (fabs(x)<1e-9 && fabs(y)<1e-9) return -100.0; 

    red=atan2(y,x); 

    if (red<0) red=red+2*pi; 

    return red; 

} 

void in() 

{ 

    int i; 

    double xx,yy; 

    fin>>n; 

    for (i=0;i<n;i++){ 

        fin>>xx>>yy; 

        x=xx; 

        y=yy; 

    } 

    return ; 

}