Блог пользователя DollarAkshay

Find area of region where k rectangles intersect?
Автор DollarAkshay, история, 5 лет назад, По-английски

Given a list rectangles [R1, R2, R3] defined by their lower left and upper right [(x1, y1), (x2, y2)] coordinates, and a value k.

Is there an optimal way to find area where k rectangles overlap?

For example:

R1: [(1, 1), (5, 5)]
R2: [(4, 4), (7, 6)]
R3: [(3, 3), (8, 7)]

rectangles = [R1, R2, R3]
k = 2

The area which is overlapped by two rectangles is 8.

Source : https://stackoverflow.com/questions/57192928/given-n-rectangles-coordinates-find-area-of-region-where-k-rectangles-intersect/

Grid Image

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If the coordinates are small enough (say, |x|, |y| <= 5000) you can use lazy update in RSQ 2D table. So, if you have N rectangles, X = width of board, Y = height of board, the complexity is O(1) for each lazy update, and the actual updating takes O(X*Y) so total complexity is O(N+X*Y) and then you count how many cells have value = K. If you need solution for bigger X and Y you should try with sweep line, but don't really know how.

→ Ответить