c语言凸包算法,基于C语言的凸包算法实现
基于C語言的凸包算法實(shí)現(xiàn)
非計(jì)算機(jī)專業(yè)，代碼有些的不好的地方，大佬輕噴^ _ ^
根據(jù)要求，需要使用C語言實(shí)現(xiàn)凸包算法——Graham掃描法，本文將從算法理解、實(shí)現(xiàn)思路、遇到的問題及其解決方案三個方面來闡述實(shí)現(xiàn)過程。
算法理解
凸包算法Graham掃描法，在不考慮排序算法的時間復(fù)雜度情況下，算法核心程序的時間復(fù)雜度為 O ( n l o g n ) O(n log n)O(nlogn)，其主要算法思想如下：
首先是預(yù)處理過程，獲得一組隨機(jī)點(diǎn)集，選取位于二維空間中左下角的點(diǎn)，即在縱坐標(biāo)(y)最小情況下橫坐標(biāo)(x)為最小的點(diǎn)P 0 P_0P0? 。以該點(diǎn)位極坐標(biāo)原點(diǎn)計(jì)算其余各點(diǎn)的極角θ \thetaθ，并根據(jù)極角大小進(jìn)行升序排序，若極角相同則按極徑大小按升序排列。由此得到一組按照極角排序的點(diǎn)集 { P 0 , P 1 , . . . , P n } \left\{P_0,P_1,...,P_n\right\}{P0?,P1?,...,Pn?}(如下圖所示)。
完成預(yù)處理之后即Graham算法的核心步驟，主要通過棧的方式來實(shí)現(xiàn)凸包點(diǎn)的計(jì)算。首先將P 0 , P 1 P_0,P_1P0?,P1?兩點(diǎn)壓棧，他們必然屬于凸包上的點(diǎn)。然后進(jìn)入迭代過程，以棧頂元素A [ t o p ] A[top]A[top]和次棧頂元素 A [ t o p ? 1 ] A[top-1]A[top?1]構(gòu)成的向量a ? \vec{a}a為基準(zhǔn)計(jì)算其與當(dāng)前P k P_kPk?點(diǎn)與棧頂元素A [ t o p ] A[top]A[top]構(gòu)成的向量b ? \vec{b}b的叉積 ，若結(jié)果為正(零)則 b ? \vec{b}b 位于 a ? \vec{a}a 的逆時針方向(共線)，P k P_kPk?進(jìn)棧 ，若結(jié)果為負(fù)則 b ? \vec{b}b 位于 a ? \vec{a}a 的順時針方向， A [ t o p ] A[top]A[top]出棧， P k P_kPk?進(jìn)棧，直至掃描至最后一個點(diǎn)，將 P 0 P_0P0? 再次進(jìn)棧是凸包閉合。
由于要求順時針輸出凸包頂點(diǎn)，則將棧中元素從棧頂向棧底依次輸出即可。
實(shí)現(xiàn)思路及過程
根據(jù)Graham掃描法的算法理解，將程序?qū)崿F(xiàn)分為了隨機(jī)點(diǎn)坐標(biāo)初始化、極角計(jì)算及排序、Graham核心算法和結(jié)果輸出四個模塊共計(jì)8個函數(shù)進(jìn)行編碼實(shí)現(xiàn)。
結(jié)構(gòu)體定義
// 點(diǎn)坐標(biāo)
typedef struct POINT {
int x;
int y;
}Point;
坐標(biāo)初始化
首先構(gòu)造存儲點(diǎn)坐標(biāo)的結(jié)構(gòu)體Point，該結(jié)構(gòu)體中僅包含橫坐標(biāo)x和縱坐標(biāo)y。根據(jù)要求需要隨機(jī)生成100個點(diǎn)，使用宏定義點(diǎn)集大小(SIZE)為100。使用庫下的rand()函數(shù)以當(dāng)前系統(tǒng)時間為種子生成 0 ≤ x < 50 , 0 ≤ y < 50 0\le x<50,0\le y<500≤x<50,0≤y<50 的點(diǎn)，并依次存入大小為SIZE的Point的類型的一維數(shù)組中。
void InitPoint(Point* p) {
int i;
srand(time(0));
for (i = 0; i < SIZE; i++) {
(p + i)->x = (int)(rand() % 50);
(p + i)->y = (int)(rand() % 50);
}
}
極角計(jì)算及排序
首先選取點(diǎn)集中位于左下角的點(diǎn)，采用的方法為先找出縱坐標(biāo) 最小的坐標(biāo)點(diǎn)(集)，然后在其中找出橫坐標(biāo) 最小的坐標(biāo)點(diǎn)，記錄該點(diǎn)位于原始點(diǎn)集的位置，將其與第一個點(diǎn)進(jìn)行交換。接著使用庫下的atan()函數(shù)計(jì)算各點(diǎn)的極角，并將其記錄在double類型大小為SIZE的一維數(shù)組angle中，令極坐標(biāo)原點(diǎn)的極角： a n g l e [ 0 ] = 0 angle[0] = 0angle[0]=0。使用冒泡排序算法對極角進(jìn)行排序，同時改變點(diǎn)集中各點(diǎn)的順序。在排序是要考慮當(dāng)極角相同時按極徑從小到大排序。
Graham核心算法
根據(jù)算法分析結(jié)果，定義一個Point類型的一維數(shù)組作為棧空間，定義棧頂定位變量top，用于標(biāo)記棧頂元素在棧中的位置，定義臨時變量temp_point用記錄當(dāng)前掃描到的坐標(biāo)點(diǎn)，定義叉積計(jì)算函數(shù)，返回值為布爾類型。當(dāng)叉積為非負(fù)時返回true，否則返回false。判斷temp_point和棧頂元素，次頂元素三個點(diǎn)組成的兩個向量的方向，若叉積返回值為正，則將temp_point進(jìn)棧，否則將當(dāng)前棧頂元素出棧，繼續(xù)判斷現(xiàn)在的棧頂元素和次頂元素與temp_point三個點(diǎn)的向量叉積……
得到包含所有凸包頂點(diǎn)的棧數(shù)組，最后將 點(diǎn)進(jìn)棧形成封閉凸包，在形成封閉凸包前需要對 以及當(dāng)前棧頂和次頂元素進(jìn)行判斷是否符合凸包結(jié)構(gòu)，若符合則將 進(jìn)棧，反之將當(dāng)前棧頂元素出棧，重復(fù)判斷步驟直至符合為止。
int myGraham(Point* p, Point* p_stack) {
int top = -1; //棧頂指針
int p_index = 0; //點(diǎn)索引
Point temp_point;
top++; p_stack[top] = p[0]; p_index++; //push
top++; p_stack[top] = p[1]; p_index++; //push
while (p_index < SIZE) {
temp_point = p[p_index];
if (X(p_stack[top - 1], p_stack[top], temp_point))
{
top++; p_stack[top] = temp_point;//push
}
else {
top--;//pop
continue;
}
p_index++;
}
while (TRUE) {
if (!X(p_stack[top - 1], p_stack[top], p[0])) {
top--;
}
else {
break;
}
}
top++; p_stack[top] = p[0];
return top;
}
結(jié)果輸出
為了使結(jié)果更直觀，定義了一個輸出函數(shù)，能夠輸出凸包頂點(diǎn)坐標(biāo)，并在二維坐標(biāo)中，顯示點(diǎn)。
運(yùn)行結(jié)果
來源：oschina
鏈接：https://my.oschina.net/u/4355012/blog/4274913
總結(jié)
以上是生活随笔為你收集整理的c语言凸包算法,基于C语言的凸包算法实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Android Studio ---
- 下一篇： deepin linux安装微信,Ubu