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

Question

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

我知道我需要在栅栏的多边形的边缘构建角点。但是我不知道如何在电脑上写

Answer 1

一个普通的凸面船体将是你最小长度的栅栏。只需取一组描述建筑物角落的点(假设建筑物是多边形)，并围绕这些点构建一个凸壳。

一组点的Convex hull是一个经典的、基本的和研究得很好的计算几何问题。

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

Gift wrapping算法非常容易理解和实现。