資源簡介
Graham掃描算法 ： 大體思路是將不是凸包頂點的點從點集中去掉。
找出S中具有最小y坐標的點p（通過選取最左邊的點打破平局）
根據點和p的連線 與 x軸正方向所成的角度，對S中的點進行排序（由小到大），并將p放在最前面。
從p點開始掃描排序后的S集合。如果這些點都在凸包上，則每三個相繼的點p1,p2,p3滿足以下性質：p3在向量<p1,p2>的左邊.如果出現相繼的三個點p1,p2,p3不滿足上述性質，則p2點一定不是凸包的頂點，應立即去除。
代碼片段和文件信息
/* 凸包問題：graham掃描算法實現
程序未對重復點做特殊化處理。在GCC-4.4.5?（ubuntu?10.04）測試成功
算法復雜度為O（n*log?n）?，時間的主要部分是排序。
lidachao?2011
*/
#include?
#include?
#include?
#include?
#include?
#include?
using?namespace?std;
#define?MAX?20?????????//給定的點的個數
//生成的點的在區域??[-RAND_max/2?RAND_max/2]X[-RAND_max/2?RAND_max/2]?內
#define?RAND_max?20??
typedef?struct?point{
float?xy;
float?angle;
}point;
/******隨機生成點，此處為簡單起見用整型數作為測試數據*****/
void?creatdata（?list?*?plist）{
srand（time（0））;
point?p1;
int?i;
for??（?i=0?;i
p1.x=float（r1）;p1.y=float（r2）;
plist->push_back（p1）;
}
}
/*****計算向量（x1y1）和（x2y2）的夾角余弦值*******/
float?vectors_cos（float?x1float?y1float?x2float?y2）{
return
評論
共有 條評論