编程求凸包点集

#include "stdafx.h"
#include <stack>
#include <queue>
using namespace std;
class point{
public:
    double x;
    double y;
    double z;
    bool operator ==(point& p){
        if(x=p.x&&y==p.y&&z==p.z)
            return true;
        else
            return false;
    }
    double angle;
};



class line{
public:
    line(point p1,point p2);
    bool isSame(line& p);
    point p1;
    point p2;
};

line::line(point p1,point p2){
    this->p1=p1;
    this->p2=p2;
}

bool line::isSame(line& l){
    if(l.p1==p1&&l.p2==p2||l.p1==p2&&l.p2==p1)
        return true;
    else 
        return false;
}

class triangle{
public:
    triangle(line l,point p){
        x=p;
        y=l.p1;
        z=l.p2;
    }
    point x;
    point y;
    point z;
};


struct allpoint{
    int num;
    point* ps;
}ap,bp;

struct alltriangle{
    int num;
    triangle* ts;
}at;

void  init_points(){
    ifstream f("point.txt");
    int sum;
    f>>sum;
    point *ps=(point*)malloc(sizeof(point)*sum);
    for(int i=0;i<sum;i++){
        f>>ps[i].x>>ps[i].y>>ps[i].z;
    }
    f.close();
    ap.ps=ps;
    ap.num=sum;
}

void min_left_y_point(){
    point min=ap.ps[0];
    int flag=0;
    for(int i=1;i<ap.num;i++){
        if(ap.ps[i].y<min.y||ap.ps[i].y==min.y&&ap.ps[i].x<=min.x){
            min=ap.ps[i];
            flag=i;
        }
    }
    point temp;
    temp=ap.ps[0];
    ap.ps[0]=min;
    ap.ps[flag]=temp;
    for(int i=0;i<ap.num;i++){
        if(ap.ps[i].x-ap.ps[0].x!=0&&ap.ps[i].y!=ap.ps[0].y)
            ap.ps[i].angle=(ap.ps[i].y-ap.ps[0].y)/(ap.ps[i].x-ap.ps[0].x);
        else{
            if(ap.ps[i].y==ap.ps[0].y)
                ap.ps[i].angle=0;
            else
                ap.ps[i].angle=DBL_MAX;
        }
    }
}

int partition(point *p,int m,int n){
    int i=m;
    point temp;
    for(int j=m+1;j<=n;j++){
        if(p[j].angle<p[m].angle){
            i++;
            temp=p[i];
            p[i]=p[j];
            p[j]=temp;
        }

    }
    temp=p[m];
    p[m]=p[i];
    p[i]=temp;
    return i;
}

void quick_sort(point *p,int m,int n){
    if(n>m){
        int i=partition(p,m,n);
        quick_sort(p,m,i-1);
        quick_sort(p,i+1,n);
    }
}

void print(allpoint ap){
    for(int i=0;i<ap.num;i++)
        cout<<ap.ps[i].x<<" "<<ap.ps[i].y<<" "<<ap.ps[i].z<<" "<<ap.ps[i].angle<<endl;
}

void angle_sort(){
    point *positive=(point*)malloc(sizeof(point)*ap.num);
    point *negative=(point*)malloc(sizeof(point)*ap.num);
    int p=0,n=0;
    for(int i=1;i<ap.num;i++){
        if(ap.ps[i].angle>=0){
            positive[p]=ap.ps[i];
            p++;
        }
        else{
            negative[n]=ap.ps[i];
            n++;
        }
    }
    quick_sort(positive,0,p-1);
    quick_sort(negative,0,n-1);
    for(int i=0;i<p;i++){
        ap.ps[i+1]=positive[i];
    }
    for(int i=p+1;i<n+p+1;i++){
        ap.ps[i]=negative[i-p];
    }
}

double distance(point p){
    return pow(p.x-ap.ps[0].x,2)+pow(p.y-ap.ps[0].y,2);
}

queue<point> qq;

void delete_same_point(){
    bp.ps=(point*)malloc(sizeof(point)*ap.num);
    bp.num=0;
    int k=1,i=1,j=2;
    for(j=2;j<ap.num;j++){
        if(ap.ps[i].angle!=ap.ps[j].angle){
            bp.ps[k]=ap.ps[i];
            k++;
            i=j;
        }
        else
            if(distance(ap.ps[i])<distance(ap.ps[j])){
                qq.push(ap.ps[i]);
                i=j;
            }
            else{
                qq.push(ap.ps[j]);
            }
    }
    
    bp.ps[k]=ap.ps[i];
    k++;
    
    bp.ps[0]=ap.ps[0];
    bp.num=k;
}

stack <point> ss;

point next_top(){
    point p,q;
    p=ss.top();
    ss.pop();
    q=ss.top();
    ss.push(p);
    return q;
}

bool line_Left(point p1,point p2,point p){
    double s=(p2.x-p.x)*(p.y-p1.y)+(p2.y-p.y)*(p1.x-p.x);
    if(s>0)
        return true;
    else
        return false;
}

void create_Hull(){
    ss.push(bp.ps[0]);
    ss.push(bp.ps[1]);
    ss.push(bp.ps[2]);
    for(int i=3;i<=bp.num-1;i++){
        while(!line_Left(next_top(),ss.top(),bp.ps[i])){
            qq.push(ss.top());
            ss.pop();}
        ss.push(bp.ps[i]);
    }
    
}

void free_mem(){
    free(ap.ps);
    free(bp.ps);
}

void print(){
    cout<<endl;
    while(!ss.empty()){
        point p=ss.top();
        cout<<"("<<p.x<<","<<p.y<<" )"<<endl;
        ss.pop();
    }

    cout<<endl;
    while(!qq.empty()){
        point p=qq.front();
        cout<<"("<<p.x<<","<<p.y<<" )"<<endl;
        qq.pop();
    }
}
//ss用于存放凸包点集，qq用于存放剩余的所有点集；
int _tmain(int argc, _TCHAR* argv[])
{
    init_points();
    min_left_y_point();
    angle_sort();
    delete_same_point();
    create_Hull();
    print(ap);
    cout<<endl;
    print(bp);
    print();
    free_mem();
    getchar();
    return 0;
}