算法:创建具有最大高度的屋顶

Question

我在一本书中发现了这个问题，并且正在拼命地尝试解决它。问题本身是:创建一个具有最大高度的屋顶(非平屋顶)。墙壁要么成 90 度角，要么平行。

我的方法:
我有所有的边缘点。所以我可以使用扫描线方法。我将在 x 轴上排序所有点，然后在 y 轴上排序。然后我将遍历我的整个点列表并绘制一条与墙壁成 45° 角的线。我将检查是否有任何线与我已经绘制的当前线相交。如果没有匹配项，我将转到下一个点并绘制另一条与墙壁呈 45° 角的线。现在最后两条线相交的可能性很高，所以我将在交点处创建一个新点。
我遇到的问题是会有很多特殊情况。有没有我没有想到的更简单的方法？还有其他更适合此类问题的算法吗？对于这种问题，你有什么想法？

例子:
这就是想象中屋顶的样子。

Answer 1

我不确定这是否是您的意思，但我的回答旨在实现屋顶的最大窥视 高度，而不是最大平均 高度。

此问题中的最大peek 高度由适合您的结构的最大正方形决定。

所以要找到它，您只需要寻找可以容纳的最大正方形并执行简单的金字塔高度计算。例如，如果您找到了一个边为 a 的正方形，并且您正在构建与您提到的底部成 45 度角的屋顶，那么:Peek = sqrt(3) *a.

找到最大平方应该不是一个复杂的任务:对于结构中的每个角，在一条直线上向每个方向(上、下、左、右)走，直到你走出结构(假设我们得到这些值 up, down, left, right), 可以从角构造的最大正方形是 min{up, left}, min{up, right} 之间的最大值， min{down, left}, min{down, right}.最大平方是从任意一个角得到的最大值。

现在构建一个金字塔，从具有最大值的角开始。在结构的其余部分，您可以随心所欲，因为它不会超过这个金字塔的高度。