Создание дерева из списка прямоугольников

Question

Это может быть глупый вопрос, но сразу ничего не приходит в голову. Учитывая список R 2D прямоугольников (x, y, w, h), расположенных таким образом, что любой данный прямоугольник находится либо полностью внутри, либо полностью вне любого другого, каков наиболее эффективный способ определения сразу вмещающий прямоугольник p каждого прямоугольника в R? В настоящее время я сортирую R по y, затем x, затем просматриваю каждую пару (a, b) и проверяю, является ли a дочерним элементом b. Мало того, что это не очень эффективно, но это также не работает должным образом: я полагал, что, поскольку R уже отсортирован, последний найденный родитель должен быть немедленно включающим, но это, кажется, не выполняется. Что-то не так с моими рассуждениями? Если нет, я отправлю код.

Answer 1

1. Сортировать по (x+y).
2. Начиная с начала отсортированного списка, возьмите прямоугольник Q.
3. Вычислить (x+y+w+h) для этого прямоугольника.
4. Для каждого прямоугольника R в части списка, которая следует за прямоугольником Q и имеет x+y for R <= <code>(x+y+w+h) of Q, проверьте, находится ли R в пределах Q. Если это так, установите Q в качестве родителя для R, перезаписывая любого ранее установленного родителя.
5. Повторите для списка.