¿Cómo dibujar el contorno de un grupo de múltiples rectángulos?

Question

Necesito dibujar un polígono envolvente de un grupo de rectángulos colocados uno al lado del otro.

Pensemos en campos de texto que comparten al menos un borde (o parte de él) con al menos uno de los otros rectángulos.Puedo obtener las coordenadas de los puntos de los rectángulos, por lo que básicamente tengo todos los datos que necesito sobre ellos.

¿Puedes pensar en un algoritmo/procedimiento simple para dibujar un polígono (trayectorias rectas conectadas) alrededor de estos objetos?

Aquí hay una demostración de diferentes casos potenciales (A, B, C, etc...).En el ejemplo A también dibujé un polígono azul que es el camino que necesito dibujar, delineando el grupo de rectángulos.

He leído aquí sobre casco convexo y cosas así, pero en realidad parece un problema mucho más simple.Una solución (principio de) que se me ocurrió fue que los puntos que realmente necesito dibujar son solo aquellos que no son compartidos por ningún par de rectángulos, lo que significa que los puntos que son vértices de más de un rectángulo son redundantes.Lo que no pude descubrir fue el orden en el que necesito dibujar líneas de una a la siguiente.

Actualmente trabajo en el objetivo c, pero se agradecería cualquier otro lenguaje o algoritmo, incluido el pseudo.

¡Gracias!

Answer 1

IMHO debería ser así.Haga una lista de bordes y vea si algunos se superponen: esto debe ser simple si los rectángulos están alineados con el eje X, Y.Solo encuentra los bordes que tienen los vértexes en la misma X o Y y las otras coordenadas deben estar entre el medio.Después de esto, los bordes restantes deben formar el esquema.

Otro método para encontrar bordes comunes es romper todos los rectángulos a lo largo de cada eje X e Y donde tiene vértices.Esto debería verse como si estuvieras creciendo todas las líneas hasta el infinito.Después de esto, todos los bordes comunes tendrán vértices comunes y se pueden eliminar.

Answer 2

Tienes dos filas y tres diferentes. y-valores.Digamos y0 es la cima de la cosa, y2 es el extremo inferior, y y1 marca el medio entre ambas filas.
Cada fila tiene un valor x máximo y mínimo, digamos que la fila superior va desde x0_min a x0_max, y la fila inferior de x2_min a x2_max.Dados esos valores, simplemente dibujas alrededor de la cosa:

(x0_min,y0)->
(x0_max,y0)->
(x0_max,y1)->
(x2_max,y1)->
(x2_max,y2)->
(x2_min,y2)->
(x2_min,y1)->
(x0_min,y1)->
(x0_min,y0)