Это может быть глупый вопрос, но сразу ничего не приходит в голову. Учитывая список R 2Д прямоугольников (x, y, w, h), расположенных таким образом, что любой данный прямоугольник либо полностью внутри или полностью вне любого другого, что наиболее эффективный способ определить сразу ограничивающий прямоугольник p каждого прямоугольника в R? В настоящее время я сортирую R по y, затем x, затем пройдите через каждую пару (, b) и проверьте, является ли a дитя b. Мало того, что это не очень эффективно, но оно также не работает правильно: я понял, что с R уже отсортирован, последний найденный родитель должен быть сразу же заключенным, но это, похоже, не выполняется. Что-то не так с моими рассуждениями? Если нет, я отправлю код.Создание дерева из списка прямоугольников
2
A
ответ
2
- Сортировка по
(x+y). - Начиная с начала отсортированного списка, возьмите прямоугольник Q.
- Вычислить
(x+y+w+h)для этого прямоугольника. - Для каждого прямоугольника R в части списка, следующего за прямоугольником Q, и имеет
x+y for R< =(x+y+w+h) of Q, проверьте, находится ли R в пределах Q. Если это так, задайте Q как родительский элемент R, перезапишите любой ранее установленный родительский элемент. - Повторите этот список.
+0
Это работает! Большое спасибо. Оказывается, моя реализация была на самом деле не за горами. –
Каков ваш фактический вопрос? Я думаю, что я знаю, о чем вы говорите, но я не могу определить, что именно вы хотите, чтобы ваш код делал с вашим списком прямоугольников. Это то, что вы хотите, чтобы ваш код определял иерархию ваших прямоугольников. Если да, то как вы будете его повторять (в данных)? –