有了向量 我們就可以選取一個最外側(cè)的點(diǎn)了

利用向量 我們可以比較哪個點(diǎn)"更外側(cè)"

比如點(diǎn)K和點(diǎn)I 我們利用向量JK乘以向量JI得到一個數(shù) 這個數(shù)應(yīng)該是負(fù)數(shù) 說明I比K更外側(cè)

兩個向量的比較具有傳遞性 所以我們可以像N個數(shù)里取最大的數(shù)一樣取出最外側(cè)的

遍歷所有點(diǎn) 每個點(diǎn)都和現(xiàn)有最外側(cè)的點(diǎn)比較 得到新的最外側(cè)的點(diǎn)

至此兩個問題都得以解決 我們可以寫出滿足一般要求的卷包裹算法了

兩個問題如下：

1.怎么確定一個肯定在凸包上的點(diǎn)?

這個問題很好解決 取一個最左邊的也就是橫坐標(biāo)最小的點(diǎn)

如果有多個這樣的點(diǎn) 就取這些點(diǎn)里 縱坐標(biāo)最小的

這樣可以很好的處理共線的情況

2.如何確定下一個點(diǎn)(即最外側(cè)的點(diǎn))?

我們需要利用向量的叉積來解決這個問題

不過還遺留有一個問題 就是處理共線的問題

有時候我們需要凸包邊上的點(diǎn)也考慮到 有時候卻需要去掉這些點(diǎn)

我們通常稱在凸包頂點(diǎn)處的點(diǎn)為極點(diǎn)

如果我們只要求保留極點(diǎn)而去除在邊上的點(diǎn)

我們只需在取外側(cè)的點(diǎn)的時候 碰到共線的點(diǎn)取最遠(yuǎn)的

相反 如果我們要保留所有在邊上的點(diǎn)

我們只需要在共線的點(diǎn)中取最近的

這樣整個卷包裹法終于完成了