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

Question

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

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

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

Answer 1

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

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

第二步证明

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

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