我知道这里提出并回答了很多与我的问题相关的问题，但我仍然很困惑。我对计算几何有点陌生，任何建议都会有帮助。
问题:一组n个矩形，其边平行于x或y轴，并且每个矩形的长度和高度都相同；已知每个矩形的四个角点的坐标，设计一个O(nlogn)时间的分治算法来计算所有矩形的并集，并集表示这些矩形所覆盖的组合面积。
这些矩形可能是不相交的、接触的或重叠的，而且它们的数量有数千个。输出可以是任何形状(结果可以是内部空心的，如洋葱圈)，其边界由一组点坐标定义。当我将两个子部分分成两半时，我正在努力解决如何合并这两个子部分的问题。 (我知道如何用扫描线/扫描平面方法计算联合面积，但不知道如何用 DaC 来计算。)
示例:
最佳答案
让我们像众所周知的 merge sort algorithm 一样思考。调用我们的程序 UnionShape。假设我们有最初大小为 n(未排序)的向量< Shape > 结构，因此我们可以将其除以一半并递归地对其应用 UnionShape，从而给出 lg n 个级别(令其为 k)。如果我们可以详细说明 Union 过程，使得在每个级别上我们都有 O(n) 工作，我们将得到总共 O (n lg (n))。
想法是，如果形状的角点已排序，我们可以详细说明并集过程，使其花费 O(m) 时间，其中 m 是联合形状的角点数量。最初(最低 k 级 - 在 k 次递归调用之后)，总共有 n/2^k 个矩形，例如 2 个，其角点已排序。我们有 2^k 个联合调用，每个联合调用有 n/2^k 个形状角，总共 O(n)。当合并矩形时，我们支持结果形状的角的排序顺序。在下一个级别，我们将进行 2^(k-1) 次调用，其中包含 n/2^(k-1) 个形状角(最大)，依此类推 - 每个级别都会进行 O(n) 比较，并且我们有 lg n 个级别，所以我们总共会有 O(n lgn)。
这就是您的重点，如果您以这种方式计算出数据结构和 Union 过程，您就完成了。
关于algorithm - O(nlogn) 分治算法计算矩形并集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22310889/