問題13 凸包計算

?

凸包計算問題：在平面上給定一組點，如何生成一個包含全部點的最小凸包。

凸包是滿足如下條件的多邊形：連接多邊形中任意兩點（包括邊界上的點）的直線段完全位于多邊形內(nèi)部（包括邊界）。最小是指：在保持凸多邊形性質(zhì)不變的前提下，若縮小該圖形，則給定的點中至少有一個位于外部。

?

凸包（Convex Hull）是一個計算幾何（圖形學(xué)）中的概念。

?

理解凸包算法需要解析幾何和計算幾何的數(shù)學(xué)知識。計算機(jī)不過是實現(xiàn)這些算法罷了。

?

本章首先介紹了一個蠻力算法，窮舉所有線段，判斷其余n-2是否在線段的同一個半平面中。

然后介紹一個效率較高的貪心算法，利用點的坐標(biāo)之間的關(guān)心，結(jié)合計算幾何的數(shù)學(xué)知識，然后用上，嘗試，糾錯，排序加棧等算計知識，提高極大提升求解效率。

?

?

【作者感受】

凸包計算在各種算法書中必有。是一個結(jié)合數(shù)學(xué)和算法設(shè)計兩類知識的代表性問題，非常能體現(xiàn)出計算機(jī)專業(yè)的特色。

?

凸包計算，在很多算法競賽中，都有題目。

當(dāng)然，圖形計算中有大量的問題需要用到凸包計算，凸包算法是計算幾何領(lǐng)域最早的成果之一。