graph - 長方形の周りに最小の長さの回路を取得する方法は?

Question

最後の大会で、私は建物のセットを与えられ、これらの建物の周りに最小の長さのフェンスを作成する必要がありました. フェンスは建物の角や壁に触れてもよいが、建物の上を通過してはならず、すべての建物が 1 つのエリアにある必要があります。

フェンスのポリゴンの端にあるコーナーを構築する必要があることはわかっています。しかし、私はそれをコンピュータ用に書く方法を知りませんでした

Answer 1

単純な凸包は、最小の長さのフェンスになります。建物の角を表す一連の点を取り (建物がポリゴンであると仮定)、これらの点の周りに凸包を構築します。

点集合の凸包は、古典的で基本的な非常によく研究された計算幾何学の問題です。

http://en.wikipedia.org/wiki/Convex_hull_algorithms

ギフトラッピングのアルゴリズムは、理解と実装が非常に簡単です。