algorithm - O(nlogn) 分而治之算法计算矩形并集

Question

我知道这里有很多与我的问题相关的问题，但我仍然感到困惑。我对计算几何有点陌生，任何建议都会有所帮助。

问题:一组n矩形，其边平行于x轴或y轴，并且每个矩形的长度和高度都相同；已知每个矩形的四个角点的坐标，设计一个O(nlogn)时间的分而治之算法计算所有矩形的并集，并集表示这些矩形覆盖的面积之和。

这些矩形可能是不相交的、接触的或重叠的，并且有成千上万个。输出可以是任何形状(结果内部可能是空心的，如洋葱圈)，边界由一组点坐标定义。当我将它们分成两半时，我正在努力研究如何合并这两个子部分。 (我知道如何用扫描线/扫描平面法计算联合面积，但不知道如何用 DaC 来计算。)

例子:

Answer 1

让我们像众所周知的那样思考merge sort algorithm .调用我们的程序 UnionShape。假设我们有初始大小为 n(未排序)的 vector< Shape > 结构，因此我们可以将其除以一半并递归地对其应用 UnionShape，从而给出 lg n 层(假设为 k)。如果我们可以详细说明 Union 程序，使得在每个级别上我们都有 O(n) 的工作，我们将得到 O (n lg (n)) 的总数。

想法是，如果形状的角被排序，我们可以精心设计并集过程，使其花费 O(m) 时间，其中 m 是联合形状的角数。最初(最低 k 级 - 在 k 次递归调用之后)总数为 n/2^k，比如 2，矩形的角已经排序。我们有 2^k 个 Union 调用，每个调用有 n/2^k 个形状的角，总共 O(n)。当合并矩形时，我们支持结果形状的角的排序顺序。在下一个级别上，我们将进行 2^(k-1) 次调用，其中 n/2^(k-1) 个形状角(最大)等等 - 每个级别都给出 O(n) 比较，并且我们有 lg n 个级别, 所以我们总共有 O(n lgn)。

这就是您的重点，如果您以这种方式计算出数据结构和 Union 过程，您就完成了。