这是一道面试题，面试过了。
给定一副长方形卡片，将它们随机放在一张长方形 table 上， table 的大小远大于卡片大小的总和。有些卡片可能会随机重叠。设计一个算法，计算出所有卡片覆盖的 table 面积，并分析算法的时间复杂度。所有卡片的每个顶点的所有坐标都是已知的。卡片可以以任何模式重叠。
我的想法:
按垂直坐标降序对卡片进行排序。
到达卡片的边或顶点后，从上到下垂直扫描卡片，用另一条扫描线继续扫描，直到到达另一条边，找到两条线之间的区域。最后，将位于两条线之间的所有区域相加并得到结果。
但是，如果面积不规则，如何计算位于两条线之间的面积是一个问题。
感谢任何帮助。谢谢!
最佳答案
这可以使用 union-intersection formula 轻松完成(A union B union C 的大小 = A + B + C - AB - AC - BC + ABC 等)，但这会导致 O(n!) 算法。还有另一种更复杂的方法会导致 O(n^2 (log n)^2)。
将每张卡片存储为一个多边形+它在列表中的面积。将列表中的每个多边形与其他每个多边形进行比较。如果它们相交，则将它们都从列表中删除，并将它们的并集添加到列表中。继续直到没有多边形相交。将它们的面积相加得到总面积。
多边形可以是凹的并且有孔，因此计算它们的交点并不容易。但是，有algorithms (和 libraries ) 可用于在 O(k log k) 中计算它，其中 k 是顶点数。由于顶点的数量可以是 n 的数量级，这意味着计算交集是 O(n log n)。
将每个多边形与其他每个多边形进行比较是 O(n^2)。但是，我们可以使用 O(n log n) sweeping algorithm而是找到最近的多边形，使整个算法 O((n log n)^2) = O(n^2 (log n)^2)。
关于algorithm - 计算随机放在 table 上的卡片所覆盖的区域，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9910459/