1.點(diǎn)集排序

為了得到加入新點(diǎn)的順序 Graham掃描法的第一步是對(duì)點(diǎn)集排序

排序是對(duì)雜亂的點(diǎn)集進(jìn)行了梳理 這也是這種算法能夠得到更高效率的根本原因

排序的方法也有兩種 極角坐標(biāo)排序(極角序) 和 直角坐標(biāo)排序(水平序)

前者好理解一些 但是在實(shí)現(xiàn)的時(shí)候 后者更方便

先說極角序 為了極角排序 我們先得得到一個(gè)參考點(diǎn)

一般的 我們?nèi)∽钭筮?橫坐標(biāo)最小)的點(diǎn)作為參考點(diǎn) 如果有多個(gè)這樣的點(diǎn)就取最下面的(縱坐標(biāo)最小)

看這樣一個(gè)例子 這是一個(gè)任意給出的平面點(diǎn)集:

參考點(diǎn)的定義:在橫坐標(biāo)最小的情況下取縱坐標(biāo)最小的點(diǎn)

所以所有的點(diǎn)只能在這個(gè)黃色的半平面中 而且正上方為閉(可取得) 正下方為開(不可取)

這就決定了參考點(diǎn)的性質(zhì):點(diǎn)集中任意兩點(diǎn)和參考點(diǎn)所成的到角為銳角

這樣我們?nèi)〉脜⒖键c(diǎn) 然后再考慮極角排序

極角排序以參考點(diǎn)為極角坐標(biāo)系原點(diǎn) 各個(gè)點(diǎn)的極角為關(guān)鍵字

由于上面我們得到的參考點(diǎn)的性質(zhì) 我們可以設(shè)所有點(diǎn)的極角均在(-90,90]之間

排序完成后應(yīng)該是這樣的:

比較極角我們?nèi)匀豢梢岳?strong>向量的叉積

同樣由于參考點(diǎn)的性質(zhì) 所有向量之間的到角都是在180度以內(nèi) 不會(huì)產(chǎn)生錯(cuò)誤