как смоделировать прямоугольник, начиная с пересечения прямоугольника

Question

С учетом rectangle_A, пересекающего rectangle_B, в котором определено объединение, в котором указан прямоугольник, содержащий оба прямоугольника, я хочу определить координаты (не перекрывающихся) прямоугольников, необходимых для добавления к rectangle_A для создания объединения прямоугольника_A и rectangle_B:

Примечание: это только одна конфигурация набора решений для прямоугольников.белые прямоугольники выше могут быть настроены по-разному, если они не перекрываются.

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

Почему?При панорамировании в пользовательском интерфейсе я только хочу (i) обновить новые части холста (ii) отслеживать, что было нарисовано как прямоугольник (объединение rectangle_A и rectangle_B).

Answer 1

Если вас не интересует минимизация количества возвращаемых прямоугольников, вы можете упростить процесс мышления до такого, который всегда возвращает не более 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 содержится в в Б).

Answer 2

Извините, я не могу дать рабочее решение, но ...

Сначала я попытался бы нарисовать такие красивые изображения для каждого случая, который вы можете себе представить. Будет много случаев, когда вам нужно более двух прямоугольников или только один, верно?

Я думаю, что получить прямоугольник, содержащий другие, тривиально, но в настоящее время я не могу думать о том, как действовать дальше. :)

Редактировать: В настоящее время я думаю об алгоритме заливки, просто заполните свой больший прямоугольник. Но есть две проблемы с этим, которые я могу себе представить: как использовать вывод заливки, чтобы генерировать из него ректы? Будет ли это правильный путь, или есть линейное решение алгебры или что-то?

Answer 3

Скажем, мы представляем прямоугольники парой координатных пар 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