gram.txt

点集凸包Gram扫描法 c++程序

#include <iostream>        //  求点集合的凸包的gram算法。n是顶点个数，x,y是顶点 

坐标。 

#include <fstream>         //  order 是按照顶点和左下脚的角度的排序后数组。 

#include <deque>           //  tu即是逆时针的凸包上的顶点。 

#include <math.h>          // 

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

                           // 2。三个以及以上的点。 

ifstream fin("gram.in");   // 3。已经考虑了边上有点的情况。 

  

#define NN 1000 

#define pi 3.1415827 

  

typedef struct Cseg{ 

        double x,y,tg; 

}Cseg; 

  

int n; 

double x[NN],y[NN]; 

deque <Cseg> order; 

deque <int> tu; 

Cseg seg1; 

deque <Cseg> ::iterator p1; 

deque <int> ::iterator p,q; 

  

void in(); 

void gram(); 

void makeorder(int s); 

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

double cross(double x1,double yy1,double x2,double yy2); 

void out(); 

  

int main() 

{ 

        in(); 

        gram(); 

        out(); 

        return 0; 

} 

void out() 

{ 

        int i; 

        for (i=0;i<tu.size();i++){ 

                cout<<order[tu].x<<" "<<order[tu].y<<endl; 

        } 

        cout<<tu.size()<<" Edges Polydgon"<<endl; 

        return; 

  

} 

void in() 

{ 

        int i; 

        fin>>n; 

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

                fin>>x>>y; 

        return; 

} 

void gram() 

{ 

        int i,mm; 

        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; 

        makeorder(mm); 

        seg1.x=x[mm]; 

        seg1.y=y[mm]; 

        tu.clear(); 

        tu.push_back(0); 

        tu.push_back(1); 

        tu.push_back(2); 

        for (i=3;i<order.size();i++){ 

                p=tu.end(); 

                seg1.x=order.x; 

                seg1.y=order.y; 

                p--; 

                q=p-1; 

                if 

(cross(order[*p].x-order[*q].x,order[*p].y-order[*q].y,order.x-order[* 

q].x,order.y-order[*q].y)>1e-9) 

                        tu.push_back(i); 

                else{ 

                        tu.pop_back(); 

                        i--; 

                        continue; 

                        //tu.push_back(i); 

                } 

        }//for 

        return; 

} 

void makeorder(int s) 

{ 

        int i; 

        double tg; 

        order.clear(); 

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

                if (i==s) continue; 

                tg=atan2(y-y[s],x-x[s]); 

                seg1.x=x; 

                seg1.y=y; 

                seg1.tg=tg; 

                p1=order.begin(); 

                while (p1!=order.end()){ 

                        if (fabs(tg-p1->tg)<1e-9){ 

                                if 

(dist(x[s],y[s],x,y)>dist(x[s],y[s],p1->x,p1->y)+1e-9) { 

                                        p1->x=x; 

                                        p1->y=y; 

                                } 

                                break; 

                        } 

                        else 

                                if (tg<p1->tg){ 

                                        order.insert(p1,seg1); 

                                        break; 

                                } 

                        p1++; 

                }//while 

                if (p1==order.end()) order.insert(p1,seg1); 

  

        }//for 

        seg1.x=x[s];seg1.y=y[s]; 

        order.insert(order.begin(),seg1); 

        //for (i=0;i<order.size();i++) 

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

%lf\n",i,order.x,order.y,order.tg*180/pi); 

  

        return; 

} 



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

{ 

  

        return (x1*yy2-x2*yy1); 

} 

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

{ 

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

  

}