计算涵盖的卡片区域中随机放在桌上 [英] Compute the area covered by cards randomly put on a table

问题描述

这是一个面试问题，面试已经完成。

This is an interview question, the interview has been done.

鉴于矩形一副纸牌，把它们随机在矩形表，其尺寸比卡片大小的总和大得多。有些卡可以相互重叠随机。设计了一种算法，可以计算出区域中的表涵盖所有卡，也分析了该算法的时间复杂度。所有卡片每个顶点的所有坐标已知。该卡可以在任何图案重叠。

Given a deck of rectangular cards, put them randomly on a rectangular table whose size is much larger than the total sum of cards' size. Some cards may overlap with each other randomly. Design an algorithm that can calculate the area the table covered by all cards and also analyze the time complexity of the algorithm. All coordinates of each vertex of all cards are known. The cards can overlap in any patterns.

我的想法：

它的纵坐标降序排序卡。

Sort the cards by its vertical coordinate descending order.

竖直从顶端扫描卡底部达到卡的边缘或顶点后，继续扫描与另一扫描线，直到达到另一个边缘，并找到位于所述两条线之间的区域。最后，总结位于两条线之间的所有地区，并得到结果。

Scan the cards vertically from top to bottom after reaching an edge or vertices of a card, go on scanning with another scan line until it reached another edge, and find the area located between the two lines . Finally, sum all area located between two lines and get the result.

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

But, how to compute the area located between two lines is a problem if the area is irregular.

任何帮助是AP preciated。谢谢！

Any help is appreciated. thanks !

推荐答案

这可以很容易地进行使用的工会交集公式的（A工会乙联盟C = A + B + C的大小 - AB - 交流 - BC + ABC等）的，但是这将导致 O（N！）算法。还有的是，导致另一种更复杂的方式为O（n ^ 2（log n）的^ 2）。

This could be done easily using the union-intersection formula (size of A union B union C = A + B + C - AB - AC - BC + ABC, etc), but that would result in an O(n!) algorithm. There is another, more complicated way that results in O(n^2 (log n)^2).

每个存储卡作为一个多边形+它在列表区域。列表中的每个多边形比较每个其他多边形。如果他们相交，从列表中删除他们两人，并加入他们的工会到列表中。继续，直到没有任何多边形相交。总结他们的区域找到的总面积。

Store each card as a polygon + its area in a list. Compare each polygon in the list to every other polygon. If they intersect, remove them both from the list, and add their union to the list. Continue until no polygons intersect. Sum their areas to find the total area.

的多边形可以是凹部和具有孔，所以计算它们的交点是不容易的。但是，也有<一个href="ftp://ftp.geoinfo.tuwien.ac.at/frank/4756_Intersection_Nonconvex_Polygons_Using_Alternate_Hierarchical_Decomposition.pdf"相对=nofollow>算法的（和库）可用来计算它在 0（K数K），其中 K 是多少的顶点。由于顶点的数量可以是 N ，这意味着计算交集为O（n log n）的。

The polygons can be concave and have holes, so computing their intersection is not easy. However, there are algorithms (and libraries) available to compute it in O(k log k), where k is the number of vertices. Since the number of vertices can be on the order of n, this means computing the intersection is O(n log n).

每个多边形相较于其他所有多边形为O（n ^ 2）。但是，我们可以使用为O（n log n）的 扫算法找到最近的多边形来代替，使得整体算法 O（（N log n）的^ 2）=为O（n ^ 2（log n）的^ 2）。

Comparing every polygon to every other polygon is O(n^2). However, we can use an O(n log n) sweeping algorithm to find nearest polygons instead, making the overall algorithm O((n log n)^2) = O(n^2 (log n)^2).

这篇关于计算涵盖的卡片区域中随机放在桌上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！