算法：创建最大高度的屋顶

我在一本书中发现了这个问题，并且正在拼命解决它。问题本身是：创建最大高度的屋顶（非平面屋顶）。墙壁可以呈90度角或平行。算法：创建最大高度的屋顶

我的方法：
我所有的边缘点。所以我可以使用扫描线方法。我会把所有的观点都分在x轴和y轴上。然后，我将通过我的所有要点列表，并以45°的角度画出一条线。我将检查是否有任何一条线与我已绘制的当前线相交。如果没有匹配，我将进入下一个点，并在墙上画另一条45°的线。现在，最后2条线相交的机会很高，所以我会在交叉点处做一个新点。
我的问题是会有很多特殊情况。有没有更简单的方法，我没有想过？还有其他更适合这类问题的算法吗？你对这种问题有什么想法？

例如：
这是想象屋顶的样子。 rooftop

来源

2013-11-04 Fabio Oesch

有一些明显的约束你的问题失踪声明：常数圆周？瓦片面积？我不认为在你的房子中弯曲会改变任何东西 - 你在一边保存的东西正是你在另一边添加的东西，所以你可以保持房子“直线”。（你可以看到这是真的，通过采取“下支”，分离它，并翻转它 - 现在将适合与另一件完全一致，并建立一个线性屋顶）。 – Floris

我不完全确定你的意思是“线性屋顶”，但我想创建的只是“斜屋顶”。我认为这不是我有多少区域。我想创造尽可能高的屋顶。 –

您的设计必须满足哪些限制条件。我想“给定尺寸（房子的覆盖面积），和屋顶的给定区域（>房子的面积）最大高度，否则您的解决方案的空间是无界如此。 - 你能澄清 – Floris

我不知道，如果这就是你的意思，但我的回答是针对具有最大偷看高度达到房顶，而不是最大平均高度。

最大值peek在这个问题中的高度是由最适合你的结构的平方决定的。

因此，要找到它，你只需要寻找最大方，可以适应和执行一个简单的金字塔高度计算。例如，如果您发现一个边缘为a的正方形，并且您正在建造与基座成45度角的屋顶，那么：Peek = sqrt(3)*a。找到最大平方不应该是一个复杂的任务：对于结构中的每个角落，沿着一条直线向每个方向（上，下，左，右）走，直到你离开结构（假设我们获得这些值up, down, left, right），可以从角落构建的最大平方是min{up, left}, min{up, right}, min{down, left}, min{down, right}之间的最大值。最大平方是从任何角落获得的最大值。

现在从具有最大价值的角落里建造金字塔。在结构的其他部分，你可以做任何你想做的事，因为它不会超过这个金字塔的高度。

来源

2013-11-04 16:36:06

我知道我的问题有很多的东西，缺少，但我已经找到了答案，这是非常simila回答你的答案。我也发现了我的意见。我会澄清确切的答案是什么。 –