凸包問題是算法中經典的題目了，最近算法課講分治問題時提到了Convex Hull,算法導論的書上也花了篇幅討論了Convex Hull的求解，主要是Graham方法。

為了能更好地理解分治和Graham這兩種解法，我決定自己動手把代碼寫一遍。

然而，在寫之前，我發現我大一學的用行列式求解由三個點圍城的三角形面積已經忘得差不多了，現在補充一下：

利用這個計算結果來判斷點p3在p1p2直線的左側還是右側

下面是分治算法求解：

#include <iostream> #include <algorithm> #include <stdlib.h> #define N 100 using namespace std;int n=0; struct POINT {int x,y; }p[N],ans[N]; int visit[N],mark[N]; int Djudge(POINT a1,POINT a2,POINT a3) {int calculate=a1.x*a2.y+a3.x*a1.y-a3.x*a2.y-a2.x*a1.y-a1.x*a3.y;return calculate; } bool cmpxy(const POINT a,const POINT b) {if(a.x!=b.x)return a.x<b.x;elsereturn a.y<b.y; }/*在涉及到平面上點對問題時，經常會按照這種方法對點進行排序 這與后面的sort(p,p+n,cmpxy)經常一起使用，在最近我做的2D maximal finding problem時，也是 使用了這樣的排序對點對進行預處理。 */ void DealLeft(int first,int last) {int max=0,index=-1;int i=first;if(first<last){for(i=first+1;i<last;i++){int calcu=Djudge(p[first],p[i],p[last]);if(calcu==0)visit[i]=1;if(calcu>max){max=calcu;index=i;}}}else{for(i-1;i>last;i--){int calcu=Djudge(p[first],p[i],p[last]);if(calcu==0)visit[i]=1;if(calcu>max){max=calcu;index=i;}}}if(index!=-1){visit[index]=1;DealLeft(first,index);DealLeft(index,last);} } int main() {cout<<"Enter the number of the points: ";cin>>n;cout<<"Enter the points: ";for(int i=0;i<n;i++){cin>>p[i].x>>p[i].y;visit[i]=0;}visit[0]=1;visit[n-1]=1;sort(p,p+n,cmpxy);DealLeft(0,n-1);DealLeft(n-1,0);int t=0;for(int i=0;i<n;i++){if(visit[i]==1){ans[t].x==p[i].x;ans[t].y==p[i].y;t++;}} //順時針輸出mark[0]=mark[t-1]=1;for(int i=1;i<t-1;i++)mark[i]-0;cout<<ans[0].x<<" "<<ans[0].y<<endl;for(int i=1;i<t-1;i++){int d=Djudge(ans[0],ans[t-1],ans[i]);if(d>=0){cout<<ans[i].x<<" "<<ans[i].y<<endl;mark[i]=1;}}cout<<ans[t-1].x<<" "<<ans[t-1].y<<endl;for(int i=1;i<t;i++){if(mark[i]!=1){int d=Djudge(ans[0],ans[t-1],ans[i]);if(d<0){cout<<ans[i].x<<" "<<ans[i].y<<endl;}}}return 0; }

轉載于:https://www.cnblogs.com/CuteyThyme/p/10596679.html

總結

以上是生活随笔為你收集整理的寻找凸包 （Convex Hull）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。