我正在尝试写一个算法来找到三角形的上包络(天际线)。
通过以下操作,您可以看到矩形的天际线:
我有一个合并矩形的两个天际线(L和R)的算法,如下所示:
用(x1,x2,h)表示每个矩形,其中h是高度,x2-x1是宽度
用一个成对的列表表示每个天际线(x,h)
对于i=min(L[1].x,R[1].x)到max(L[L].x,R[R].x的大小)选择max(L[i].h,R[i].h)
现在,我的问题是如何表示三角形,以及如何合并两个三角形的天际线
任何想法都会很感激的
最佳答案
在下面我假设三角形的基线在底部。我还假设所有三角形的上角都在基线之上(即,如果你从上角一直往下走,你会进入三角形的内部,而不是外部)但是我不认为只有对称三角形是允许的。
实际上,三角形的合并会产生一个简单的点与线相连的天际线因此,三角形天际线的表示可以是点(x_i,y_i)的有序列表,其限制条件是y_i=0和y_n=0,其中n是最后一个点的索引。单个三角形将由三个元素列表(x_0,0),(x_1,h),(x2,0)表示,其中x_0和x_2是左端点和右端点(三角形达到0的两点),x_1表示上角的水平位置,h表示高度。
例如,两个天际线的合并可以如下进行:
第1步:对于每条线段(x_i,y_i)--(x_i+1},y_i+1}),从天际线1到每条线段(x_j,y_j)--(x_j+1},y_j+1}),计算它们是否相交,如果相交,则在哪里(这意味着解一个简单的两个线性方程组)。将交点收集到一个新列表中,即交点。现在有三个点列表:skyline1、skyline2和交点。由于所有交叉口都将是天际线的一部分,因此请将其用作新天际线的基础。(一种特殊情况是两个天际线在一段时间内一致,但在这样的时间间隔内,组合的天际线无论如何都与每个单独的天际线相同,因此只需使用这些时间间隔的起点和终点作为交点)
现在,对于每对交叉点(以及第一个交叉点的左侧和最后一个交叉点的右侧),始终只有一个天际线位于另一个天际线之上(除非他们同意,但之后你选择哪一个并不重要)在从该天际线到组合天际线的间隔中添加点只需选择一个天际线的任意点(如果交叉点也是天际线点,则不应选择该点)并在其X值处检测另一个天际线的高度(如果另一个天际线也有一个位于同一X值处的点,则是对Y值的简单比较,否则必须插入前面和后面点的y值)。
这样做之后,你应该有正确的组合天际线。
关于algorithm - 三角形的天际线算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/8375194/