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.
My idea:
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.
Any help is appreciated. thanks !
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.
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).
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).