在桌子上随机放置卡片，计算覆盖的面积。

Question

这是一道面试题，面试已经结束。

假设有一叠矩形的卡片，将它们随机放置在一个比所有卡片尺寸总和大得多的矩形桌子上。一些卡片可能随机重叠。设计一种算法，能够计算出所有卡片覆盖的桌子面积，并分析算法的时间复杂度。每个卡片的每个顶点的坐标都已知。卡片可以以任何方式重叠。

我的想法:

按照垂直坐标降序排列卡片。

从上到下垂直扫描卡片，在扫描到卡片的边缘或顶点后，使用另一条扫描线继续扫描，直到达到另一条边缘，找到两条线之间的区域。最后，将位于两条线之间的所有区域相加并得到结果。

但是，如果区域是不规则的，如何计算两条线之间的区域是一个问题。

感谢您的帮助！

- user1002288

---

它们是否都朝着同一个方向（即卡片永远不会以不同的角度旋转）？ - Nim

计算卡片顶点的三角形，并计算这些三角形所占据的区域，考虑到重叠因素。 - Justin Pearce

它们为什么是三角形？它们可以与任何图案重叠。谢谢！ - user1002288

问题明确指出表格“比卡片的总大小要大得多”。因此，我认为问题只是要求您有效地“查找”重叠的卡片，然后使用任何代码计算它们的交集。（由于非常非常少的重叠卡片具有非常非常高的概率，所以后者可以慢一些）。 - Nemo

@user1002288 因为每个多边形都可以分解成三角形。只有当对 Nim 的问题的答案是它们可以旋转时，这才是相关的 - 否则，有更简单的解决方案。 - Nick Johnson

-1 表示没有澄清 Nim 的问题 - 非常重要。 - Tomas

Answer 1

这可以很容易地使用并集交集公式（A与B与C的大小= A + B + C-AB-AC-BC + ABC等）完成，但这将导致一个O(n!)算法。还有另一种更复杂的方法，其结果为O(n^2(log n)^2)。

---

将每张卡片及其面积存储在列表中作为多边形。将列表中的每个多边形与其他每个多边形进行比较。如果它们相交，则从列表中删除它们两个，并将它们的并集添加到列表中。继续直到没有多边形相交。将它们的面积相加以找到总面积。

这些多边形可以是凹多边形且具有空洞，因此计算它们的交集并不容易。然而，有算法（和库）可用于在O(k log k)中计算它，其中k是顶点数。由于顶点数可能达到n的数量级，因此计算交集的时间复杂度为O(n log n)。

将每个多边形与其他所有多边形进行比较的时间复杂度为O(n^2)。然而，我们可以使用O(n log n)的扫描算法来查找最近的多边形，从而使整个算法的时间复杂度为O((n log n)^2) = O(n^2 (log n)^2)。

- BlueRaja - Danny Pflughoeft

---

你的回答的第一部分是什么意思--容易怎么做？ - Colonel Panic

@Matt：对所有卡牌的区域面积求和；减去所有成对卡牌交集的面积；加上所有三张卡牌交集的面积；再减去四张卡牌交集的面积等。这些交集没有空洞，并且是凸形的，因此找到它们比更复杂的情况要容易得多。 - BlueRaja - Danny Pflughoeft

卡片是凸的。凸形状的交集也是凸的。明白了，谢谢。 - Colonel Panic

Answer 2

这几乎肯定不是面试官想要的答案，但我会提出这个方案，只是为了看看他们的反应:

假设所有卡片大小相同，严格为矩形，没有孔洞，但它们在X,Y方向上随机放置，并以θ角度随机定向。因此，每张卡牌都由三元组(x,y,theta)或四元组(四个角的位置)来描述。有了这些信息，我们可以很简单地进行蒙特卡罗分析。

只需在桌面表面随机生成若干点，并使用列表确定每个点是否被任何卡片覆盖。如果是，则保留它；如果不是，则将其丢弃。通过保留点数与总点数的比率来计算卡片的面积。

显然，您可以在O(n)时间内测试每个点，其中n是卡片数量。然而，我认为这里有一种巧妙的小技巧，我认为它能加快速度。您可以使用适当的网格大小(与卡片大小相关)对桌面进行网格化，并预处理卡片以确定它们可能存在于哪些网格中。(您可以过度估计，将卡片预处理为直径在对角线之间的圆形碟。)现在，用网格位置作为键构建哈希表，每个网格位置的内容是可能重叠该网格的任何可能卡片。(卡片将出现在多个网格中。)

现在，每次您需要包含或排除一个点时，您不需要检查每张卡片，而只需检查可能存在于该点网格位置的预处理卡片。

这种方法有很多优点:

- 您可以相当容易地将其更改为使用非矩形卡片，特别是如果它们是凸面的。 - 如果必须(在这种情况下，几何形状确实变得很麻烦)，您可能可以将其更改为使用不同大小或形状的卡片。 - 如果你在一家从事科学或工程工作的公司面试，他们会喜欢它。 - 它可以很好地并行化。 - 它太酷了!!

另一方面:

- 这是一种近似技术(但您可以以任何精度运行!) - 你处于预期运行时间的领域，而不是确定性运行时间的领域。 - 有人可能会问你关于蒙特卡罗的详细问题。 - 如果他们不熟悉蒙特卡罗，他们可能会认为你在胡说八道。

我希望能为这个想法贡献一份力量，但遗憾的是，我从一篇论文中学到了这个想法，该论文基于蛋白质中原子的位置和大小计算表面积。(基本上是相同的想法，除了现在我们有一个三维空间中的3D网格，并且卡片确实是圆盘。我们会遍历每个原子，在其表面生成大量点，并查看它们是否是其他原子的内部。) 编辑： 我想到原始问题规定总表面积远大于总卡片面积。在这种情况下，适当的网格大小意味着大多数网格必须为空闲状态。一旦建立了哈希表，您还可以预处理网格位置，并完全消除这些位置，仅在可能被占用的网格位置内生成点。(基本上，在每个潜在遮挡的网格位置上执行单个MC估计。)

- Novak

---

非常聪明。我喜欢它比需要分解多边形的解决方案更简单，只要你愿意容忍近似。 - Nick Johnson

Answer 3

这里有一个不完美但实用的想法。您可以设计一个算法，其精度度量epsilon（eps）取决于此。想象一下，您将空间分成大小为eps x eps的正方形。现在，您想要计算位于卡片内的正方形数量。假设卡片数量为n，卡片边长为h和w。

以下是一种朴素的方法：

S = {} // Hashset
for every card:
   for x in [min x value of card, max x value of card] step eps:
       for y in [min y value of card, max y value of card] step eps:
           if (x, y) is in the card:
               S.add((x, y))
return size(S) * eps * eps

该算法的时间复杂度为O(n*(S/eps)^2)，误差受到强烈限制，因为其上限值为(2*S*n*eps)，因此相对误差最多为(2*eps*n/S)。

举例来说，为了保证误差小于1%，您需要选择eps小于S/(200n)，而该算法运行大约需要200^2*n^3步。

- aelguindy

---

这不是基本的射线投射吗？ - Stefano Borini

@StefanoBorini 我不知道什么是射线投射，但如果我描述的内容还没有被实现（或者已经有了一个名字），那我会感到惊讶的 :-). - aelguindy

你可以将表面分成许多小单元，从每个单元中心发射一条虚拟光线，并检查是否与物体相交。这是制作光线追踪图像的一种技术（至少是最基本的技术）。 - Stefano Borini

这并不是光线投射，而是“数值积分”或者“通过点计数估算面积”。但可以说它也可以被称为光线投射。 - High Performance Mark

很多图形技术与数值积分技术密切相关，这是其中之一。当您以这种方式使用网格点时，我认为通常称为求积技术。当您使用随机点时，它就是蒙特卡罗。在高维空间中，蒙特卡罗将具有更好的收敛性能。 - Novak

Answer 4

假设有n张单位面积的卡片。让T表示桌子的面积。对于离散化问题，预期覆盖的面积将为：

$ T(1-({{T-1}\over{T}})^n) $

- Colonel Panic

---

这不是一个关于期望值的概率问题 - 他在询问如何高效地计算一定数量的卡片所覆盖的实际面积。 - BlueRaja - Danny Pflughoeft

我喜欢这种方法，比其他提议简单得多。楼主也可以尝试蒙特卡洛方法。 - Victor Sorokin

Answer 5

T = 桌子的总面积。

C = 卡片可以覆盖的总面积（一张卡片的面积乘以卡片数量）。

V = 卡片重叠的总面积（V = 重叠）

要计算的面积 = T - (C - V)

应该有一种有效的方法来分析卡片所占用的空间，以便快速识别重叠和非重叠情况。识别这些情况，消除所有重叠区域，问题就解决了。

时间复杂度将考虑按顺序逐个检查每张卡片，并将其与其余卡片进行比较（卡片2已经针对卡片1进行了检查），这使得它成为n！，不好...但这就是“应该”的地方。必须有一种有效的方法来从考虑中删除所有不重叠的卡片，对卡片进行排序，以便明显地确定它们是否可能重叠其他/先前的卡片，并且可能识别或分组潜在重叠的卡片。

有趣的问题。

- Philip Kelley

---

计算“重叠卡片的总面积”是不可行的，因为超过两张卡片可以重叠在同一空间。例如，想象所有卡片都在完全相同的位置 - 那么“重叠卡片的总面积”等于一个卡片的面积！此外，您的公式明显是不正确的 - 想象T非常大，那么T - (C - V)可能比C还要大！！ - BlueRaja - Danny Pflughoeft

+1：这基本上是正确的，除了它计算的是未覆盖的面积而不是覆盖的面积（一个微不足道的问题）。V需要被正确解释，所以如果两张卡片重叠，就要减去这个重叠区域的面积一次，然后如果第三张卡片恰好覆盖这个重叠区域，就要再减去重叠区域的面积一次，以此类推。也就是说，如果所有卡片都堆叠在一起，C=52A，V=51A，或者一个卡片的面积，这是正确的。 - tom10

这就是为什么你要（痛苦地）逐张卡片地进行。 “第一”（或最低）张卡片覆盖一个区域，而所有后续（堆叠的）卡片在它们重叠的区域内不会覆盖该区域。 - Philip Kelley