如何獲得矩形周圍的最小長度電路？

Question

在最後的比賽中，我被賦予了一套建築物，並且我需要在這些建築物周圍創建最小長度的圍欄。護欄可能會觸及建築物的角落，牆壁，但不得越過建築物，所有建築物都必須位於同一區域。

我知道我需要在圍欄的多邊形邊緣構建拐角。但我不知道如何爲電腦編寫它

Answer 1

一個普通的凸包將成爲你的最小長度的圍欄。只需採取一組描述建築物角落的點（假設您的建築物是多邊形）並圍繞這些點構建凸包。

Convex hull對於一組點而言，這是一個經典的，基本的，並且研​​究得非常好的計算幾何問題。

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

Gift wrapping算法是非常容易理解和執行。