как моделировать прямоугольное объединение, запускающееся с прямоугольного пересечения
Данный rectangle_A, пересекающийся rectangle_B, который имеет объединение, определенное таким образом, что это - прямоугольник, содержащий оба прямоугольника, я хочу определить координаты (не накладывающийся) прямоугольники, требуемые добавить к rectangle_A для создания объединения rectangle_A и rectangle_B:
Примечание: это - всего одна конфигурация набора решения прямоугольников. белые прямоугольники выше могли быть настроены по-другому, пока они не накладываются.
Существует ли простой алгоритм для каждого случая прямоугольного пересечения? Я сделал первичную обработку, и я пропускаю некоторые углы. Очевидно не мой forté.
Почему? При панорамировании в UI я только хочу к обновлению (i), которое новые части холста (ii) отслеживают то, что было нарисовано как прямоугольник (объединение rectangle_A и rectangle_B).
3 ответа
Если вас не интересует минимизация количества возвращаемых прямоугольников, вы можете упростить мыслительный процесс до такого, который всегда возвращает не более 8 прямоугольников:
U
+----------+----+-------+
| | | |
| 1 | 2 | 3 |
+----------+----+-------+
| | | |
| 4 | A | 5 |
| | | |
+----------+----+-------+
| 6 | 7 | 8 |
+----------+----+-------+
U.x1 = min(A.x1,B.x1)
U.x2 = max(A.x2,B.x2)
U.y1 = min(A.y1,B.y1)
U.y2 = max(A.y2,B.y2)
R1.x1 = R4.x1 = R6.x1 = U.x1
R2.x1 = R7.x1 = R1.x2 = R4.x2 = R6.x2 = A.x1
R2.x2 = R7.x2 = R3.x1 = R5.x1 = R8.x1 = A.x2
R3.x2 = R5.x2 = R8.x2 = U.x2
R1.y1 = R2.y1 = R3.y1 = U.y1
R1.y2 = R2.y2 = R3.y2 = R4.y1 = R5.y1 = A.y1
R4.y2 = R5.y2 = R6.y1 = R7.y1 = R8.y1 = A.y2
R6.y2 = R7.y2 = R8.y2 = U.y2
При желании вы можете затем быстро проверить каждый прямоугольник, чтобы убедиться, что r.x1 == r.x2 || r.y1 == r.y2 (т.е. если у него нулевая площадь), и выбросьте его, если это так. В большинстве случаев таким образом можно выбросить более половины прямоугольников.
Например, в ваших трех примерах это решение вернет 3, 1 и 5 прямоугольников и вернет 0 в лучшем случае (когда B содержится в A) и 8 в худшем случае (когда A содержится в B).
Мне жаль, что я не могу дать рабочего решения, но ...
Сначала я бы попытался нарисовать такие красивые изображения для каждого случая, который вы можете себе представить. Будет много случаев, когда вам понадобится более двух прямоугольников или только один, верно?
Я думаю, что получить прямоугольник, содержащий остальные, тривиально, но в настоящее время я не могу придумать, что делать дальше. :)
Редактировать: В этот раз я думаю об алгоритме заливки, просто заполните свой больший прямоугольник. Но я могу себе представить две проблемы с этим: как использовать вывод заливки заливки, чтобы сгенерировать из него прямоугольники? Будет ли это правильный путь, или есть решение линейной алгебры или что-то в этом роде?
Допустим, мы представляем прямоугольники парой пар координат x,y: x1,y1 для левого верхнего угла и x2,y2 для левого нижнего угла. Предположим также, что координаты y увеличиваются вниз, а координаты x - слева направо.
Теперь предположим, что прямоугольник, образованный объединением A и B (в соответствии с вашим определением объединения) - это прямоугольник U.
Итак,
U.x1=min(A.x1,B.x1), U.y1=min(A.y1,B.y2) --- top-left corner, take the lowest values
U.x2=max(A.x2,B.x2), U.y2=max(A.y2,B.y2) --- bottom-right corner, take the highest values
Теперь, когда у нас есть больший прямоугольник U, мы можем использовать его для вычисления меньших прямоугольников справа и снизу, которые нужно добавить к A (левый/верхний прямоугольник), чтобы получился U. Назовем их Rt и Bot.
(На этот раз я предполагаю, что A - это левый верхний прямоугольник, если это не так, поменяйте местами A и B. Также предполагается, что макет похож на тот, что на вашем рисунке. Если это не так, вы можете легко адаптировать это).
Rt.x1=A.x2, Rt.y1=A.y1
Rt.x2=A.x2, Rt.y2=B.y2
Bot.x1=A.x1, Bot.y1=A.y2
Bot.x2=A.x2, Bot.y2=B.y2