graph - 如何在矩形周围获得最短长度的电路？

Question

在上次比赛中，我得到了一组建筑物，我需要在这些建筑物周围创建长度最短的围栏。栅栏可以接触建筑物的角落、墙壁，但不能越过建筑物，所有建筑物都必须在一个区域内。

我知道我需要构建位于围栏多边形边缘的角落。但是我不知道如何为计算机编写它

Answer 1

一个普通的凸包将是你最短的栅栏。只需取一组描述建筑物角落的点（假设您的建筑物是多边形）并围绕这些点构建一个凸包。

一组点的凸包是一个经典的、基本的和经过充分研究的计算几何问题。

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

礼品包装算法非常容易理解和实现。