drawing - 绘制任意凸形状，知道其边长

Question

我有一个值列表，它们是任意凸形（多边形）的边长。我怎样才能画出这个形状？什么算法可以帮助我完成这项任务？

例如，我有一个列表：2、5、2、3。绘图必须如下所示：

Answer 1

对此有一个相对简单（如果有些数学繁重）O(N log N) to O(N^2) (depending on implementation)基于递归几何/三角函数的解决方案。

1. 该概念从长度等于长度总和的线段开始。
2. 将该线段分成三角形（参见底部附近的相关信息）。
3. 根据需要递归地将三角形的每条边分成更多的三角形。

第 2 步，需要确保三角形的较小两条边长于较大的一条。

步骤 3，可以通过将一个三角形变成 2 个三角形来完成。

对于我将使用的输入和输出：输入：边列表输出：内角列表。

output[a]顶点的内角也是如此，无论是在边缘之前还是之后input[a]。

一个很好的参考位于此处。

• 方法＃1 gif，显示了那么多顶点的三角形。
• 方法#2 gif, P 是第 2 步中可能发生中断的示例。
• 方法#4 gif，这里的 P 可以被视为像 #3 中一样移出，注意在这种情况下，行长不会按比例缩放，实际上是未知的。请注意，只有 和 的顶点位置a1会a2改变。导致前后顶点的内角发生变化a1和a2。在这种情况下，a1,a2,a3,an,p。

至于确定内角。使用三角学和/或几何学。给定三角形的 3 条边，可以确定角度是多少。给定 2 个边和一个角度（或 1 个角度和 2 个边），可以确定缺少的边和角度。

当然，您可能必须小心在哪里打破边缘，以便形成三角形。

Answer 2

我将在这里引用我在 MathOverflow 上发布的答案：

如果最长边不长于所有其他边的长度之和，则边链可以闭合。

在您的示例中，最长边为 5，并且不超过 2+2+3=7。如果将长度为 5 的边替换为长度为 8 的边，则四个线段不能靠近凸多边形。每当您有超过 3 条边时，生成的凸多边形并不是唯一确定的：它的形状具有灵活性。

有关证明的指针，请参见上面引用的参考资料。