algorithm - 将三角形放在一条线上，最小化最大距离

Question

我需要将三角形（不同形状）放置在一条直线上，放置的第一个三角形和最后一个三角形之间的距离尽可能低。三角形只允许一个角接触线，但需要放在线的顶部，不允许穿过线。

我可以旋转三角形，但不能改变它们的大小或形状。

我尝试将三角形围绕线的一个点放置成圆形，直到达到 180° 并重复该过程，但我认为这不是一个非常有效的算法。

标签： algorithmlinepacking

Answer 1

首先，旋转三角形，使最短的尺寸是水平的（以最短的边为底）。在此之后，您将拥有最少的总长度。

其次，按右下角的角度对三角形进行排序并按顺序收集它们。在此之后，它们将不会相交。

第二步证明

   B          D
   |\        /|
   | \      / |
   |  \    /  |
   |   \  /   |
   |____\/____|
   A    C     E

对于已排序的三角形 ACB < CED。CED + CDE + DCE = 180 -> DCE < 180 - CED ACB < CED 和 DCE < 180 - CED -> ACE + DCE < 180，因此三角形不会重叠。