algorithm - 三角形的天际线算法

Question

我正在尝试编写一种算法来查找三角形的上包络线(天际线)。 通过跟随你可以看到矩形的天际线:

我有一个合并矩形的两条天际线(L 和 R)的算法，如下所示:

• 用 (x1, x2, h) 表示每个矩形，其中 h 是高度，x2-x1 是宽度
• 用一对 (x, h) 的列表表示每条天际线
• 对于 i= min(L[ 1].x, R[ 1].x) 到 max(L[L[L].x 的大小, R[R[R].x 的大小) 选择 max(L[i] .h, R[i].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 值处检测另一条天际线的高度(如果另一个skyline也有一个点在相同的x值，它是一个简单的y值比较，否则你必须插值前后点的y值)。

完成之后，您应该拥有正确的组合天际线。