我在一本书中发现了这个问题，并正在拼命地解决它。问题本身是：创建一个具有最大高度的屋顶（非平屋顶）。墙壁要么成 90 度角，要么平行。
我的方法：
我有所有的边缘点。所以我可以使用扫描线方法。我将在 x 轴上排序所有点，然后在 y 轴上排序。然后，我将遍历我的整个点列表，并在墙壁上画一条 45° 的线。我将检查是否有任何线与我已经绘制的当前线相交。如果没有匹配，我将转到下一个点并绘制另一条与墙壁成 45° 的线。现在最后两条线相交的机会很高，所以我将在相交点创建一个新点。
我的问题是会有很多特殊情况。有没有我没有想到的更简单的方法？还有其他更适合此类问题的算法吗？你对这类问题有什么想法？
示例：
这就是想象屋顶的样子。
我不确定这是否是您的意思，但我的回答旨在实现具有最大窥视高度的屋顶，而不是最大平均高度。
此问题中的最大窥视高度由可以适合您的结构的最大平方确定。
所以要找到它，你只需要寻找可以适应的最大平方并执行简单的金字塔高度计算。例如，如果您发现一个边为 的正方形a，并且您正在建造与您提到的底部成 45 度角的屋顶，那么：Peek = sqrt(3)*a。
找到最大平方不应该是一项复杂的任务：对于结构中的每个角落，沿着直线沿着每个方向（上、下、左、右）走，直到走出结构（假设我们获得了这些值up, down, left, right） ，可以从一个角构造的最大平方是 之间的最大值min{up, left}, min{up, right}, min{down, left}, min{down, right}。最大平方是从任意角得到的最大值。
现在从具有最大值的角落构建一个金字塔。在结构的其余部分，你可以做任何你想做的事情，因为它不会超过这个金字塔的高度。
许多人批评我如何问我的问题，即缺少某些东西，而且确实缺少输入。因此，作为输入，我有一组点示例：
(0, 0) (6, 0) (6, -2) (8, -2) (8, 8) (-2, 8) (-2, 3 ) (0, 3)
以正确的顺序排列。
接下来我要做的就是像我在图 1 中那样放置点。在我的例子中，我把它们放在了右下角。现在需要查看哪些点在形状中，哪些点不在形状中。这可以通过将您制作的点与建筑物的水平线和垂直线相交来轻松找到。如果你找到一个奇数，你就知道关键在表格中。否则我们删除它。
毕竟，我们试图从找到的每个点（红线）中找到我们可以创建的最大矩形。我们现在唯一缺少的是我们在右下角矩形上创建一个新点，并在左上角创建另一个矩形（黄线）。正如在我的示例中所见，我们在此示例中通过使用矩形的较小边找到了最大的正方形。这除以 2 将为我们提供表格的最大高度。
如果您需要更多澄清，请随时问我。