Tal*_*lon 5 java algorithm geometry grahams-scan
我正在尝试计算矩形联合的周长，其中我有左下角和右上角的点。每个矩形都位于 x 轴上（每个矩形的左下角是 (x, 0)）。我一直在研究这样做的不同方法，似乎 Sweep-Line 算法是最好的方法。我也看过格雷厄姆扫描。我的目标是 O(n log n) 算法。老实说，虽然我对如何进行迷失了方向，但我希望这里的某个人可以尽最大努力为我简化它，并尝试帮助我准确了解如何实现这一目标。
我从我所做的研究中收集到的一些东西：
我们需要对点进行排序（我不确定我们对它们进行排序的标准）。
我们将分而治之（以实现 O（log n））。
我们需要计算交点（最好的方法是什么？）
我们需要某种数据结构来保存点（也许是二叉树？）
我最终会在 Java 中实现这个算法。
该算法是大量繁琐的案例分析。不是超级复杂，但很难完全正确。
假设所有矩形按左下角和右上角（x0，y0，x1，y1）存储在数组A中。因此，我们可以将矩形的任何边表示为一对 (e, i)，其中 e \in {L, R, T, B} 表示左、右、上、下边，i 表示 A[i]。将所有对 (L, i) 放入起始列表 S 中，并在 A[i].x0 上对其进行排序。
我们还需要一条扫描线 C，它是顶部边缘的三元组 (T, i, d) 和底部边缘的三元组 (B, i, d) 的 BST。这里 i 是矩形索引，d 是整数深度，如下所述。BST 的关键是边的 y 坐标。最初它是空的。
请注意，您可以随时按顺序遍历 C 并确定扫描线的哪些部分被矩形隐藏，哪些部分未被矩形隐藏。通过保持深度计数器（最初为零）来做到这一点。从最小y到最大，当遇到底边时，计数器加1。当您看到顶部边缘时，递减 1。对于计数器为零的区域，扫描线可见。否则它会被矩形隐藏。
现在你实际上并没有完成整个遍历。相反，您可以通过逐步保持深度来提高效率。C 中每个三元组的 d 元素是其上方区域的深度。（C 中第一条边下方的区域的深度始终为 0。）
最后我们需要一个输出寄存器 P。它存储一组折线（边的双向链表对此很方便）并允许以下形式的查询“给我所有端点 y 坐标落在 [y0.. y1]。算法的一个属性是，这些多段线始终有两条水平边缘与扫描线交叉作为其末端，所有其他边缘都在扫描线的左侧。此外，没有两条多段线相交。它们是输出的片段多边形“正在建设中”。请注意，输出多边形可能并不简单，由多个“环”和“洞”组成。另一个 BST 可以用于 P。它最初也是空的。
现在算法大致如下所示。我不会剥夺弄清楚细节的所有乐趣。
while there are still edges in S
Let V = leftmost vertical edge taken from S
Determine Vv, the intersection of V with the visible parts of C
if V is of the form (L, i) // a left edge
Update P with Vv (polylines may be added or joined)
add (R, i) to S
add (T, i) and (B, i) to C, incrementing depths as needed
else // V is of the form (R, i) // a right edge
Update P with Vv (polylines may be removed or joined)
remove (T, i) and (B, i) from C, decrementing depths as needed
当 P 更新时，您将生成复杂的多边形。最右边的边缘应该关闭最后一个循环。
最后，请注意重合的边缘可能会产生一些棘手的特殊情况。当您遇到这些问题时，请再次发帖，我们可以讨论。
排序的运行时间当然是 O(n log n)，但更新扫描线的成本取决于有多少多边形可以重叠：退化情况为 O(n)，整个计算为 O(n^2) 。
祝你好运。我已经实现了这个算法（几年前）和其他一些类似的算法。它们是严格逻辑案例分析的巨大练习。非常令人沮丧，但当你获胜时也会有回报。