python - Given a list of rectangles, how to find all rectangles that are fully contained within other ones? -

i've got computer vision algorithm puts bounding boxes around detected objects. bounding boxes list goes follows:

bounding_boxes = [[x, y, w, h], [x2, y2, w2, h2], ...] 

where x , y coordinates of top left corner, h , w height , width of box. however, i'm not interested in boxes contained within other larger boxes. what's efficient method detect those?

as confirmed in comments under question, need identify , remove boxes contains in single other box. if box contained in union of other boxes, no other single box contains it, should not removed (e.g. in case boxes = [[0, 0, 2, 4], [1, 1, 3, 3], [2, 0, 4, 4]], second box contained in union of first , third, should not removed).

---

the naive (brute-force) algorithm task simple. here pseudocode:

for in [0, 1, ..., n]:     j in [i+1, i+2, ..., n]:         check if box[i] contains in box[j] , otherwise. 

the complexity of algorithm o(n^2). algorithm easy implement , recommended if number of boxes small (around 100-500, or 1000 if don't need real-time performance video processing).

---

the complexity of fast algorithm o(n log n), believe minimal theoretical complexity problem. formally, required algorithm takes following input , returns following output:

input: boxes[] - array of n rectangles, tuples of (x1, y1, x2, y2),                   (x1, y1) coordinates of left bottom corner, (x2, y2)                  coordinates of top right corner. output: inner_boxes[] - array of rectangles should removed. 

the pseudocode fast algorithm:

1) allocate array events[] length 2*n, elements of     tuples (y, corresponding_box_index, event).   2) in [0, 1, ..., n]:      events[2 *    ] = tuple(boxes[i].y1, i, 'push')      events[2 * + 1] = tuple(boxes[i].y2, i, 'pop')  3) sort events[] ascending of y coordinate (from smaller larger).    if there equal y coordinates, then:    - tuples 'pop' event smaller thant tuples 'push' event.    - if 2 tuples has same event, sorted ascending of      width of corresponding boxes.  4) create map cross_section_map[], maps key (value) x tuple    (corresponding_box_index, type), type can either 'left' or 'right'.    make sure 'insert' , 'erase' operation of data structure     has complexity o(log n), iterable, elements iterated in     key-ascending manner, , can search key in o(log n) time.  5) step in [0, 1, ..., 2*n]:      if events[step].event 'push':        - let = events[step].corresponding_box_index        - insert map boxes[i].x1 -> (i, 'left') cross_section_map[]        - insert map boxes[i].x2 -> (i, 'right') cross_section_map[]        - search 'right'-typed key x value no less boxes[i].x2        - iterate key until found key, corresponds          box contains boxes[i], or x1 coordinate of larger          x1 coordinate of newly added box. in first case, add          boxes[i] inner_boxes[].      if events[step].event 'pop':        - let = events[step].corresponding_box_index        - erase elements keys boxes[i].x1 , boxes[i].x2 

now, tricky part step (4) of algorithm. may seem hard implement such data structure. however, there wonderful implementation out-of-the-box in c++ standard library, called std::map. search operations works in o(log n) std::map::lower_bound , std::map::upper_bound.

this algorithm has average complexity of o(n log n), worst-case complexity of o(n^2) and, if number of boxes , sizes relatively small comparing image size, complexity near o(n).