介紹求取平面上頂點集合凸包的Graham Scan和Andrew's Monotone Chain方法。基本原理是在頂點排序好后，初始化一棧，循環(huán)取出頂點集合中每個頂點元素，將其與棧頂兩元素進行判別，看是否符合凸包條件，循環(huán)結束后，棧中剩余元素即為所求。具體過程如下。

求凸包Graham Scan方法。它的大致過程是：?
???????找到最右下頂點P₀后，以各頂點與P₀X的夾角來排序所有的集合中頂點。實際工作中，可簡化角度計算工作，而通過前面章節(jié)介紹的isLeft()函數(shù)，來判斷頂點P₂是否處于線段P₀P₁左邊，從而判斷夾角的大小。設這些經過排序的頂點為P₀，P₁，…P_n-1；
????鄰接關系判斷圖?
?????
????
?????????將頂點排好序
??? 然后，建立一個棧，最開始時P₀，P₁進棧，對于剩下的頂點P₂，P₃，…P_n-1等依次取出，若棧頂?shù)拈_頭兩個頂點與新取出的頂點不滿足“左轉”（即isLeft()函數(shù)返回數(shù)值大于0）條件，則將棧頂?shù)牡谝粋€頂點出棧，繼續(xù)測試，直到滿足“左轉”條件后將新取出的頂點進棧；所有剩下的頂點P₂，P₃，…P_n-1處理完之后棧中剩下的頂點構成凸包。

需說明的是，此方法很難推進到三維空間。

參考代碼：

//主程序

Stack?? GrahamScan( )

{

??? Stack?? top;

??? int i;

??? Point p1, p2;?

??? top = NULL;

??? top = Push ( &P[0], top );

??? top = Push ( &P[1], top );??????????????????? //初始化棧

??? i = 2;

??? while ( i < n )????????????????????????? //對所有的排序后頂點循環(huán)

??? {

??????? if( !top->next) printf("Error"n");?? //棧中沒有第二個元素，報出錯信息

??????? p1 = top->next->p;

??????? p2 = top->p;???????????????????????? //取出棧頂?shù)膬蓚€元素

??????? if ( isLeft( p1->v , p2->v, P[i].v ) )//判斷是否左轉

??????? {

??????????? top = Push ( &P[i], top );?????? //壓棧

??????????? i++;???????????????????????????????? //頂點計數(shù)器增加

??????? }

??????? else???

??????????? top = Pop( top );??????????????? //退棧

??? }

??? return top;????????????????????????????? //棧中剩下的元素即為構成凸包的頂點

}

//開始準備工作中尋找所有頂點中右下角頂點

int?? FindLowest( void )

{

??? int i;

??? int m = 0;?

??? for ( i = 1; i < n; i++ )??????????????? ??? //對所有頂點循環(huán)

??????? if ( (P[i].v[Y] <?P[m].v[Y]) ||

??????????? ((P[i].v[Y] == P[m].v[Y]) && (P[i].v[X] > P[m].v[X])) )

??????????? m = i;

??? return m;??????????????????????????????? //返回右下角最低點索引

}

求凸包Andrew's Monotone Chain方法。

首先，依X軸和Y軸數(shù)值順序排列所有頂點。?
??????? ????
?????? 以最左(當X軸數(shù)值相同的時候，以Y軸數(shù)值最下和最上取頂點)至最右邊的頂點(當X軸數(shù)值相同的時候，以Y軸數(shù)值最下和最上取頂點)連線，構成L_up，L_low等線段，將頂點集合分成上下兩部分，分別使用類似于上面介紹的Graham Scan方法尋求子凸包，最后合并形成一個凸包（注意連接處頂點的重復存儲）。

?????? 參考代碼：

//???? 輸入經過排序的頂點數(shù)組 P[]，n為數(shù)組中頂點個數(shù)

//???? 輸出: 凸包的頂點集合 H[]

//??? 返回: H[]中的頂點個數(shù)

int CDEMAlgorithm::chainHull_2D( Point* P, int n, Point* H )

{

??? // 輸出的數(shù)組H[]被用作一個棧

??? int??? bot=0, top=(-1);?// 指示棧底和棧頂

??? int??? i;???????????????

???

??? int minmin = 0, minmax; // 得到X軸最小情況下Y軸分別最小和最大頂點的索引

??? double xmin = P[0].x;

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

??????? if (P[i].x != xmin) break;?? //頂點已經排好序，搜索開始階段的X軸最小值

??? minmax = i-1;??????????? //記錄X軸最小情況下Y軸最大頂點的索引

??? if (minmax == n-1) {?????? // 如果出現(xiàn)極端情況，即所有頂點X軸數(shù)值都最小

??????? H[++top] = P[minmin];

??????? if (P[minmax].y != P[minmin].y) // 如果兩頂點的Y軸數(shù)值不等，則可構成線段

??????????? H[++top] = P[minmax];

??????? H[++top] = P[minmin];?????????? // 將這兩個頂點增加到輸出的數(shù)組中

??????? return top+1;??????????????????? //返回輸出的數(shù)組中的頂點個數(shù)

??? }

??? int maxmin, maxmax = n-1; // 得到X軸數(shù)值最大情況下??? Y軸數(shù)值分別最小和最大的頂點索引

??? double xmax = P[n-1].x;

??? for (i=n-2; i>=0; i--)?????? ??? //從頂點的原始數(shù)組中反向循環(huán)，因為頂點已排好序

??????? if (P[i].x != xmax) break;

??? maxmin = i+1;??????????????????? //記錄X軸數(shù)值最大情況下Y軸數(shù)值最小的頂點索引

??? H[++top] = P[minmin]; // 開始計算下半部分凸包，首先將X軸和Y軸數(shù)值都最小的頂點壓入棧

??? i = minmax;????????? //從X軸數(shù)值最小情況下Y軸數(shù)值最大的頂點開始計數(shù)

??? while (++i <= maxmin)

??? {

??????? // 以X軸和Y軸數(shù)值最小頂點連接X軸最大和Y軸數(shù)值最小頂點建立低線

??????? if (isLeft( P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)

??????????? continue;??? // 由于此頂點位于這根低線之上，所以忽略，繼續(xù)下次循環(huán)

??????? while (top > 0)?// top是從最開始的-1計數(shù)，所以大于0的話，表明棧中至少有2個元素

??????? {

??????????? if (isLeft( H[top-1], H[top], P[i]) > 0)

???????????????? break;???????? //表明P[i]頂點是需要的凸包中新頂點，結束循環(huán)

??????????? else

???????????????? top--;???????? //將棧頂元素出棧，繼續(xù)循環(huán)

??????? }

??????? H[++top] = P[i];?????? // 將頂點P[i]壓入棧

??? }

??? // 下面，計算上半部分的凸包頂點集合

??? if (maxmax != maxmin)????? // 如果X軸數(shù)值最大情況下Y軸有不同頂點存在

??????? H[++top] = P[maxmax];?// 將X軸數(shù)值與Y軸數(shù)值最大的頂點壓入棧

??? bot = top;???????????????? // 記住準備增加元素到棧前已經存在的元素個數(shù)

??? i = maxmin;????????? //從X軸數(shù)值最大情況下Y軸數(shù)值最小的頂點開始計數(shù)

??? while (--i >= minmax)

??? {

??????? // 以X軸和Y軸數(shù)值最大頂點連接X軸最小和Y軸數(shù)值最大頂點建立高線

??????? if (isLeft( P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)

??????????? continue;???????? // 由于此頂點位于這根高線之下，所以忽略，繼續(xù)下次循環(huán)

??????? while (top > bot)?? // top還是比開始記住的bot大，表明棧中至少有2個元素

??????? {

??????? ??? if (isLeft( H[top-1], H[top], P[i]) > 0)

???????????????? break;???????? //表明P[i]頂點是需要的凸包中新頂點，結束循環(huán)

??????????? else

???????????????? top--;???????? ?//將棧頂元素出棧，繼續(xù)循環(huán)

??????? }

??????? H[++top] = P[i];?????? // 將頂點P[i]壓入棧

??? }

??? if (minmax != minmin)??????? //如果X軸數(shù)值最小情況下Y軸有不同頂點存在

??????? H[++top] = P[minmin];?// 把這最后一個頂點壓入棧

??? return top+1;??????????????? //返回輸出的凸包數(shù)組中的頂點個數(shù)

}

轉載于:https://www.cnblogs.com/wuhanhoutao/archive/2008/03/19/1112650.html

總結

以上是生活随笔為你收集整理的计算点、线、面等元素之间的交点、交线、封闭区域面积和闭合集(续7)的全部內容，希望文章能夠幫你解決所遇到的問題。

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