这是一道面试题，面试已经做过了。
给定一副矩形卡片，将它们随机放在一张长方形桌子上，桌子的尺寸远大于卡片尺寸的总和。有些卡片可能会随机重叠。设计一个算法，可以计算所有卡片覆盖桌子的面积，并分析算法的时间复杂度。所有卡片每个顶点的所有坐标都是已知的。卡片可以以任何图案重叠。
My idea:
按垂直坐标降序对卡片进行排序。
从上到下垂直扫描卡片，到达卡片的一个边缘或顶点后，用另一条扫描线继续扫描，直到到达另一个边缘，找到位于两条线之间的区域。最后，将两条线之间的所有面积相加并得到结果。
但是，如果两条线之间的面积不规则，如何计算该面积是一个问题。
任何帮助表示赞赏。谢谢 ！
这可以使用以下方法轻松完成并交公式 https://web.archive.org/web/20171214094328/http://mathforum.org/library/drmath/view/52438.html （A 联合 B 联合 C 的大小 = A + B + C - AB - AC - BC + ABC 等），但这会导致O(n!)算法。还有另一种更复杂的方式会导致O(n^2 (log n)^2).
将每张卡片存储为多边形+其面积在列表中。将列表中的每个多边形与其他每个多边形进行比较。如果它们相交，请将它们从列表中删除，并将它们的并集添加到列表中。继续直到没有多边形相交。将它们的面积相加即可得出总面积。
多边形可能是凹的并且有孔，因此计算它们的交集并不容易。然而，有算法 ftp://ftp.geoinfo.tuwien.ac.at/frank/4756_Intersection_Nonconvex_Polygons_Using_Alternate_Hierarchical_Decomposition.pdf (and 图书馆 http://www.cs.man.ac.uk/%7Etoby/gpc/)可用于计算它O(k log k), where k是顶点数。由于顶点的数量可以是n，这意味着计算交集是O(n log n).
将每个多边形与其他每个多边形进行比较是O(n^2)。然而，我们可以使用一个O(n log n) 扫描算法 https://en.wikipedia.org/wiki/Sweep_line_algorithm而是找到最近的多边形，使整体算法O((n log n)^2) = O(n^2 (log n)^2).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
