Учитывая список прямоугольников, как найти все прямоугольники, которые полностью содержатся в других?

Как вы подтвердили в комментариях под вопросом, вам необходимо определить и удалить поля, содержащиеся в одном другом поле. Если блок содержится в объединении других блоков, но ни один другой блок не содержит его, то его не следует удалять (например, в случае boxes = [[0, 0, 2, 4], [1, 1, 3, 3], [2, 0, 4, 4]], второй блок содержится в объединении первый и третий, но его не следует снимать).

Наивный (брутфорс) алгоритм для этой задачи очень прост. Вот псевдокод:

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

Очевидно, что сложность этого алгоритма O(n^2). Этот алгоритм очень легко реализовать и рекомендуется, если количество ящиков невелико (около 100-500 или даже 1000, если вам не нужна производительность в реальном времени для обработки видео).

Сложность быстрого алгоритма равна O(n log n), что, я считаю, также является минимальной теоретической сложностью для этой проблемы. Формально требуемый алгоритм принимает следующие входные данные и возвращает следующий результат:

Input: boxes[] - Array of n Rectangles, Tuples of (x1, y1, x2, y2), where 
                 (x1, y1) is coordinates of the left bottom corner, (x2, y2)
                 is the coordinates of the top right corner.
Output: inner_boxes[] - Array of Rectangles that should be removed.

Псевдокод быстрого алгоритма:

1) Allocate an Array events[] with the length 2*n, the elements of which are 
   Tuples (y, corresponding_box_index, event). 

2) For i in [0, 1, ..., n]:
     events[2 * i    ] = Tuple(boxes[i].y1, i, 'push')
     events[2 * i + 1] = Tuple(boxes[i].y2, i, 'pop')

3) Sort events[] by the ascending of y coordinate (from smaller to larger).
   If there are equal y coordinates, Then:
   - Tuples with 'pop' event are smaller thant Tuples with 'push' event.
   - If two Tuples has the same event, they are sorted by the ascending of
     the width of their corresponding boxes.

4) Create a Map cross_section_map[], that maps a Key (Value) x to a Tuple
   (corresponding_box_index, type), where type can be either 'left' or 'right'.
   Make sure that the 'insert' and 'erase' operation of this data structure 
   has the complexity O(log n), it is iterable, the elements are iterated in 
   an key-ascending manner, and you can search for a key in O(log n) time.

5) For step in [0, 1, ..., 2*n]:
     If events[step].event is 'push':
       - Let i = events[step].corresponding_box_index
       - Insert a map boxes[i].x1 -> (i, 'left') to cross_section_map[]
       - Insert a map boxes[i].x2 -> (i, 'right') to cross_section_map[]
       - Search for a 'right'-typed key with x value no less than boxes[i].x2
       - Iterate from that key until you found a key, which corresponds to
         a box that contains boxes[i], or the x1 coordinate of which is larger
         than the x1 coordinate of a newly added box. In the first case, add
         boxes[i] to inner_boxes[].
     If events[step].event is 'pop':
       - Let i = events[step].corresponding_box_index
       - Erase the elements with the keys boxes[i].x1 and boxes[i].x2

Теперь самая сложная часть - это шаг (4) этого алгоритма. Может показаться, что реализовать такую ​​структуру данных сложно. Однако в стандартной библиотеке C ++ есть замечательная готовая реализация, которая называется std::map . В O(log n) работают следующие операции поиска: std::map::lower_bound и _ 11_.

Этот алгоритм имеет среднюю сложность O(n log n), сложность наихудшего случая O(n^2), и, если количество ящиков и их размеры относительно малы по сравнению с размером изображения, сложность близка к O(n).