计算随机放在桌子上的卡所覆盖的区域

Question

这是一个面试问题,面试已经完成.

给定一副长方形卡片,将它们随机放在一张矩形桌子上,这张桌子的大小远大于卡片大小的总和.有些卡片可能会随机重叠.设计一种算法,可以计算所有卡覆盖的表面积,并分析算法的时间复杂度.所有卡的每个顶点的所有坐标都是已知的.卡可以任何模式重叠.

我的想法:

按垂直坐标降序对卡片进行排序.

到达卡片的边缘或顶点后,从上到下垂直扫描卡片,继续扫描另一条扫描线,直至到达另一条边缘,然后找到位于两条线条之间的区域.最后,对位于两条线之间的所有区域求和并得到结果.

但是,如果区域不规则,如何计算位于两条线之间的区域是一个问题.

任何帮助表示赞赏.谢谢 !

Answer 1

这可以使用union-intersection公式 (A union B union 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).

Answer 2

这几乎肯定不是你的采访者所期待的,但我提议只是看看他们回答的内容:

我假设所有的卡都是相同的尺寸,并且严格是矩形的,没有孔,但是它们是随机放置在X,Y意义上,并且在θ意义上随机定向.因此,每张卡的特点是三重(x,y,theta),当然你也有四角的位置.有了这些信息,我们可以相当简单地进行蒙特卡罗分析.

只需在表面上随机生成多个点,并通过使用列表确定每个点是否被任何卡覆盖.如果是,请保留; 如果没有,扔掉它.通过保持点数与总点数的比率计算卡片的面积.

显然,你可以测试O(n)中的每个点,其中n是卡的数量.然而,我认为这里有一种灵巧的小技术,我认为会加快速度.您可以使用适当的网格尺寸(与卡的大小相关)将桌面网格化,并对卡片进行预处理,以确定它们可能位于哪些网格中.(您可以通过预处理卡片来高估)好像它们是圆形磁盘,直径在相对的角之间.)现在建立一个哈希表,其中键作为网格位置,每个键的内容都是可能与该网格重叠的卡.(卡片将出现在多个网格中.)

现在,每当您需要包含或排除一个点时,您不需要检查每张卡,而只需检查可能位于您的点的网格位置的预处理卡.

这个方法有很多要说的:

• 您可以非常轻松地将其更改为使用非矩形卡,特别是如果它们是凸的
• 您可以更改它以使用不同尺寸或形状的卡,如果必须(在这种情况下,几何结构真的很烦人)
• 如果你在一个从事科学或工程工作的地方进行面试,他们会喜欢它
• 它非常平行
• 这是太酷了!

另一方面:

• 这是一种近似技术(但你可以运行任何你喜欢的精度!)
• 你处于预期运行时间,而不是确定性运行时
• 有人可能会问你关于蒙特卡洛的详细问题
• 如果他们不熟悉蒙特卡洛,他们可能会认为你正在制造东西

我希望我可以赞成这个想法,但是,我从一张纸上选择它,根据蛋白质中原子的位置和大小计算蛋白质的表面积.(同样基本的想法,除了现在我们在3空间中有一个3D网格,卡片确实是磁盘.我们将通过并为每个原子在其表面上生成一堆点,看看它们是否存在内部到任何其他原子.)

编辑: 我发现原始问题规定总表区域远大于总卡区域.在这种情况下,适当的网格大小意味着大多数网格必须未被占用.一旦构建了哈希表,您还可以预处理网格位置,并完全消除这些位置,仅在可能占用的网格位置内生成点.(基本上,对每个可能被遮挡的网格位置执行单独的MC估计.)