?

凸包 graham 算法

標(biāo)簽：?算法distancexpstructoutputinput 2011-09-08 12:30?8371人閱讀?評(píng)論(2)?收藏?舉報(bào) ?分類： c++?凸包?graham

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

向量：

1.向量的內(nèi)積（數(shù)量積，點(diǎn)乘）：

公式：a· b = |a| * |b| cos<a, b>＝a.x* b.y + b.x * a.y

2.向量的外積（向量積，差乘）：

公式：|c|= |a|*|b|*sin<a, b> = a.x * b.y - b.x * a.y

意義：

1).兩個(gè)向量和坐標(biāo)原點(diǎn)所圍成的面積（可正可負(fù)）。

2).值為正值表示向量a在向量b的順時(shí)針方向,反之,向量a在向量b的逆時(shí)針方向,相等時(shí),共線.

凸包:由平面上的最小點(diǎn)所圍成的多邊形,平面上任何其它的點(diǎn)都在這個(gè)多邊形內(nèi)部，這個(gè)多邊形就稱為

凸包。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? (圖1)?

graham算法：

第一步:選取x軸坐標(biāo)最小的點(diǎn),如果存在多個(gè)選y軸坐標(biāo)最小的點(diǎn).(如圖1,p0點(diǎn))

第二步:排序.從下到上掃描有其它點(diǎn).(如圖1)掃描的結(jié)果順序,p0, p4, p5, p7,?p9,p6, p8, p2,p3, p1.

數(shù)學(xué)公式向量的外積模公式:|c|(是模不是絕對(duì)值符號(hào))= |a|*|b|*sin<a, b> = a.x * b.y – b.x * a.y

|c|> 0:向量a在向量b的順時(shí)針方向,因?yàn)榇死c(diǎn)坐標(biāo)取x軸坐標(biāo)最小的點(diǎn),所以,向量a在向

量b的下方.(p0-p4線段在p0-p5的下方).

|c|= 0:共線時(shí),按照與原點(diǎn)距離由小到大的順序.

第三步:按照第二步得到的頂點(diǎn)順序進(jìn)行graham掃描.按照本例選取的原點(diǎn)方式,當(dāng)掃描到左拐(p0,p4, p5)時(shí)保留(p4),右拐(p9,p6, p8)時(shí)刪除頂點(diǎn)(p6),結(jié)果就是凸包的頂點(diǎn)集.(綠線掃描的順序，紅線為左拐點(diǎn)).共線時(shí),刪除距離較小的點(diǎn).

注意：右拐刪除結(jié)點(diǎn)時(shí),必須回溯與前面保留的點(diǎn)重新比較,因?yàn)閯h除一個(gè)點(diǎn)后先前拐點(diǎn)性質(zhì)會(huì)發(fā)生變化

例如:刪除p6后,(p7, p9, p8)?也是右拐了.

所謂的左拐/右拐就沿著邊界掃描后,其它的點(diǎn)是否在當(dāng)前點(diǎn)與下一點(diǎn)連線與原點(diǎn)的內(nèi)部.

例如:結(jié)果p7-p8是凸包的頂點(diǎn),p7-p8直線會(huì)把所有其它點(diǎn)擋在原點(diǎn)p0方向的一側(cè).

數(shù)學(xué)公式:

向量外積模公式

例:

p5– p4向量Xp0 – p4?向量>0, (p5–p4)在(p0–p4)的順時(shí)針方向,左拐

p8– p6向量Xp9 – p6向量<0, (p8–p6)在(p9–p6)的逆時(shí)針方向,右拐

也可以采用其它向量方式

例:

p4–p0向量Xp5–p0向量>0, (p4–p0)在(p5–p0)的順時(shí)針方向,左拐

p6–p9向量Xp8–p9向量<0, (p6–p9)在(p8–p9)的逆時(shí)針方向,右拐

示例程序:

p0:(1, -2)

p1:(1, 2)

p2:(5, 3)

p3:(4,5)

p4:(2, -4)

p5:(6, -6)

p6:(7, 0)

p7:(10, -3)

p8:(9, 4)

p9:(8, -1)

input:

10

1 -2

1 2

5 3

4 5

2 -4

6 -6

7 0

10-3

9 4

8 -1

output:

1 -2

2 -4

6 -6

10-3

9 4

4 5

1 2

源代碼:

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

#define MAX_NUMS 10

typedef struct
{
??? int x;
??? int y;
} veritice;

veritice?? vet[MAX_NUMS];
int?????????????????? n;
std::vector<veritice>? v;

inline int cross(const veritice& p0, const veritice& p1, const veritice& p2)
{
??? veritice u, v;

??? u.x = p1.x - p0.x, u.y = p1.y - p0.y;
??? v.x = p2.x - p0.x, v.y = p2.y - p0.y;

??? return v.x * u.y - u.x * v.y;
}

inline int distance(const veritice& p1, const veritice& p2)
{
??? return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
}

inline int graham_compare(const void* a, const void* b)
{
??? int result = cross(vet[0], *(veritice*)a, *(veritice*)b);

??? if(result)
??????? return result;

??? return distance(vet[0], *(veritice*)a) - distance(vet[0], *(veritice*)b);
}

inline void graham_scan()
{
??? v.push_back(vet[0]);
??? v.push_back(vet[1]);

??? for(int i = 2; i < n; i++)
??? {
??????? while( cross(v[v.size() - 1], v[v.size() - 2], vet[i]) <= 0)
??????????? v.pop_back();

??????? v.push_back(vet[i]);
??? }
}

int main()
{
??? std::ifstream in("case_in");
??? int index = 0;

??? in >> n;

??? for(int i = 0; i < n; i++)
??? {
??????? in >> vet[i].x >> vet[i].y;

??????? if(vet[0].x > vet[i].x || (vet[0].x == vet[i].x && vet[0].y > vet[i].y))
??????????? index = i;
??? }

??? in.close();
// 第一步
??? veritice temp;
??? temp.x?????? = vet[0].x,?????? temp.y?????? = vet[0].y;
??? vet[0].x???? = vet[index].x,?? vet[0].y???? = vet[index].y;
??? vet[index].x = temp.x,???????? vet[index].y = temp.y;

// 第二步
??? qsort(vet + 1, n - 1, sizeof(veritice), graham_compare);

//　第三步
??? graham_scan();

//? 輸出
??? for(unsigned int i = 0; i < v.size(); i++)
??????? std::cout << v[i].x << ' ' << v[i].y << std::endl;

??? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的写到usaco上的一题可能题解是凸包所以转来这篇文章看看的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。