查找包围所有三角形的最小面积平行四边形

Question

以下是问题说明。

1. 你已经拿到k号等边三角形的（有上 k一个上盖，可以说k=<15）。三角形可以重叠。

2. 现在，您必须找到一个包含所有三角形的平行四边形，并具有最小面积 。假定四个边的两个相对边是 ，与X轴或Y轴平行（这是您的选择）。

我的做法：

比方说，他们两个是平行于轴线Y。

然后，该组三角形 的最左点和最右点将位于平行四边形的两个相对边缘。现在我将绘制两条直线，它们穿过这些点并与轴线平行。

这样我发现两条边并不那么困难。 现在我卡住了，不知道如何找到其他两个。 我想了很多，但因为我无法做到我在这里发布它。 任何帮助将不胜感激!!!!!!!

Answer 1

围绕所有三角形顶点构建convex hull。

然后使用rotating calipers获得对平行线与它们之间的最小垂直距离（平行四边形的区域是由高度（这里水平）中所定义 - 它已经是固定的，并且通过垂直基线长度 - 选择最小值）