cómo simular una unión rectangular comenzando con una intersección de rectángulo

Question

Dado rectangle_A intersectando rectangle_B, que tiene una unión definida de modo que es el rectángulo que contiene ambos rectángulos, quiero determinar las coordenadas de los rectángulos (no superpuestos) necesarios para agregar a rectangle_A para crear la unión de rectangle_A y rectangle_B:

Nota: esta es solo una configuración del conjunto de soluciones de rectángulos. los rectángulos blancos de arriba podrían configurarse de manera diferente, siempre que no se superpongan.

¿Hay un algoritmo simple para cada caso de intersección de rectángulo? He hecho un primer pase y echo de menos algunas curvas. Evidentemente no es mi forté.

¿Por qué? Al hacer panorámicas en una interfaz de usuario, solo quiero (i) actualizar las partes nuevas del lienzo (ii) realizar un seguimiento de lo que se ha pintado como un rectángulo (la unión de rectangle_A y rectangle_B).

Answer 1

Si no tienen que ver con reducir al mínimo el número de rectángulos de regresar, se puede simplificar el proceso de pensamiento a uno que siempre devuelve no más de 8 rectángulos:

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 

Si quisiera, podría entonces comprobar rápidamente cada rectángulo para ver si r.x1 == r.x2 || r.y1 == r.y2 (es decir, si tiene área cero), y tírelo si es así. En la mayoría de los casos, más de la mitad de los rectángulos pueden desecharse de esta manera.

Por ejemplo, en los tres ejemplos, esta solución devolvería 3, 1 y 5 rectángulos, y devolvería 0 en el mejor de los casos (cuando B está en A) y 8 en el peor de los casos (cuando A es contenido en B).

Answer 2

Supongamos que representamos los rectángulos por un par de pares de coordenadas x, y: x1, y1 para la esquina superior izquierda y x2, y2 para la esquina inferior izquierda. Supongamos también que la coordenada y aumenta hacia abajo y las coordenadas x aumentan de izquierda a derecha.

Ahora, supongamos que el rectángulo formado por la unión de A y B (según su definición de la unión) es el rectángulo es U.

Así,

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 

Ahora que tenemos el mayor rectángulo U, podemos usar eso para calcular los rectángulos más pequeños derecho e inferior que se deben agregar a A (el rectángulo izquierdo/superior) para hacerlo U. Vamos a llamarlos Rt y Bot.

(Esta vez asumo que A es el rectángulo superior izquierdo, si no es un intercambio A y B. También suponiendo que el diseño sea similar al de su imagen. Si ese no es el caso, puede adaptar esto fácilmente).

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 

Answer 3

Lo siento no puedo dar una solución de trabajo, pero ...

Al principio me gustaría tratar de sacar este tipo de imágenes agradables para todos los casos en los que puede imaginar. Habrá un montón de casos, donde necesita más de 2 rectángulos, o solo uno, ¿verdad?

Creo que obtener el rect que contiene los otros es trivial, pero en este momento no puedo pensar en cómo proceder. :)

Editar: En este momento estoy pensando en un algoritmo de llenado de inundación, simplemente complete su rect mayor. Pero hay dos problemas con esto que puedo imaginar: ¿Cómo usar la salida de llenado de inundación para generar rectas a partir de ella? ¿Será la manera correcta, o hay una solución de álgebra lineal o algo así?