三角形的天际线算法

Question

我正试图写一个算法来找到三角形的上包络(天际线)。通过以下操作，您可以看到矩形的天际线：

​

我有一个合并两个矩形的天际线(L和R)的算法如下：

width

• represent
• 通过(x1，x2，h)表示每个矩形，其中h是高度，x2-x1是由一对(x，h)
• ( i= min(L1.x，R1.x)到max(Lsize of L.x，Rsize of R.x)的列表表示的，其中h是高度，x2-x1代表天际线，选择max(L，Ri.h)

)。

现在，我的问题是如何表示三角形，以及如何合并两个三角形的天际线。

任何想法都将不胜感激。

Answer 1

在下面，我假设三角形的基线在底部。我也假设所有的三角形都是这样的，上面的角在基线之上(也就是说，如果你从上角直下，你就进入三角形，而不是外面)。然而，我并不是假设只有对称三角形是允许的。

实际上，三角形的合并会给出一个天际线，其中简单的点与线相连。因此，三角形天际线的表示可以是一个有序的点列表(x_i，y_i)，其限制条件是y_0 =0，y_N =0，其中N是最后一点的索引。然后，用三元素列表( x_0，0)、(x_1、h)、(x2,0)表示单个三角形，其中x_0和x_2是左、右端点(三角形达到0的两个点)，x_1表示上角的水平位置，h表示高度。

例如，两条天际线的合并如下：

步骤1:对于天际线1中的每个线段(x_i，y_i)-(x_{i+1}，y_{i+1})和每个线段(x_j，y_j)-(x_{j+1}，y_{j+1})计算它们是否相交，如果相交，其中(这意味着求解一个简单的两个线性方程组)。将交点收集到一个新的列表中，即交叉口。现在您有三个要点列表: skyline1、skyline2和交叉点。因为所有的交叉口都是天际线的一部分，所以把它作为新天际线的基础。(特例是两条天际线在某一间隔上一致，但在这种间隔内，合并的天际线与每一个单独的天际线相同，所以只需使用这些间隔的起点和终点作为交点)

现在，对于每一对交点(也就是第一个交点的左边和最后一个交叉口的右边)，总是有一条天际线在另一条上面(除非他们同意，但你选择哪一条并不重要)。将从该天际线到组合天际线的间隔中的点数添加到合并的天际线中。您只需选择一个天际线的任意点(除非交点也是一个天际线点，不应该选择一个)，然后检测另一个天际线在其x值处的高度(如果另一个天际线也有一个点位于相同的x值，则这是y值的简单比较，否则必须插值前面和后面的点)。

这样做后，你应该有正确的组合天际线。