Invertir un conjunto de rectángulos en un plano 2D

Question

Tengo un plano rectangular de dimensión entera. Dentro de este plano tengo un conjunto de rectángulos que no se intersecan (de dimensión entera y en coordenadas enteras).

Mi pregunta es ¿cómo puedo encontrar de manera eficiente la inversa de este conjunto; es decir, las partes del plano que no están contenidas en un sub-rectángulo. Naturalmente, esta colección de puntos forma un conjunto de rectángulos --- y es esto lo que me interesa.

Mi solución actual e ingenua usa una matriz booleana (el tamaño del plano) y funciona configurando un apunte i, j a 0 si está dentro de un sub-rectángulo y 1 de lo contrario. Luego repito a través de cada elemento de la matriz y si es 1 (libre) intento de 'crecer' un rectángulo hacia afuera desde el punto. La unicidad no es una preocupación (cualquier conjunto adecuado de rectángulos está bien).

¿Hay algún algoritmo que pueda resolver este problema de manera más efectiva? (Es decir, sin necesidad de recurrir a una matriz booleana.

Answer 1

sí, es bastante sencillo he respondido a una pregunta casi idéntica en SO antes, pero no han sido capaces de encontrar todavía

de todos modos, en esencia lo que puede hacer esto:.

• comience con una lista de salida que contenga un solo resultado rect igual a la área de interés (algunos cuadro delimitador arbitrario que define el área de interés y contiene todas las rectas de entrada)
• para cada entrada rect
  • si el rect entrada cruza cualquiera de las rectas en la lista de salida
    • eliminar el viejo rect de salida y generar hasta cuatro nuevos salida rectas que representan la diferencia entre la intersección y la salida original rect

Paso final opcional: iterar a través de la lista de salida buscando pares de rects que se puedan fusionar con un solo rect (es decir pares de rects que comparten un borde común se pueden combinar en un solo rect).

Answer 2

Sospecho que puede obtener un lugar ordenando los rectángulos mediante la coordenada y, y tomando un enfoque de línea de barrido. Puedo o no construir una implementación.

.

Answer 3

Esto es relativamente simple porque sus rectángulos no se entrecruzan. El objetivo es básicamente un conjunto de rectángulos que no se intersectan que cubren por completo el plano, algunos marcados como originales y otros marcados como "inversos".

Piense en términos de exploración descendente (o izquierda-derecha o lo que sea). Usted tiene una posición actual de "línea de marea". Determine cuál es la posición de la siguiente línea horizontal que encontrará que no está en la línea de marea. Esto te dará la altura de tu próxima línea de marea.

Entre estas líneas de marea, tiene una franja en la que cada línea vertical va de una línea de marea a la otra (y quizás más allá en ambas direcciones). Puede ordenar las posiciones horizontales de estas líneas verticales y usarlas para dividir la tira en rectángulos e identificarlas como si fueran (parte de) un rectángulo original o (parte de) un rectángulo inverso.

Avanza hasta el final, y obtienes (probablemente demasiados pequeños) rectángulos, y puedes elegir los que quieras. También tiene la opción (con cada paso) de combinar pequeños rectángulos de la tira actual con un conjunto de rectángulos potencialmente extensibles de antes.

Puede hacer lo mismo, incluso cuando sus rectángulos originales pueden cruzarse, pero es un poco más complicado.

Detalles deja como ejercicio para el lector ;-)

Answer 4

Usted debe echar un vistazo a los algoritmos que llenan el espacio. Esos algoritmos son tyring para llenar un espacio dado con algunas figuras geométricas. No debería ser difícil modificar dicho algoritmo para sus necesidades.

Tal algoritmo está comenzando desde cero (espacio vacío), por lo que primero debe completar sus datos internos con cuadros que ya tiene en el plano 2D. Luego dejas que el algoritmo haga el resto: llena el espacio restante con otros cuadros. Esos cuadros están haciendo una lista de los trozos de espacio invertido de tu avión.

Mantenga esas casillas en una lista y luego verifique si un punto está en el plano invertido es bastante fácil. Simplemente recorre su lista y realiza un control si el punto se encuentra dentro de la caja.

Aquí hay un site con un buch de algoritmos que podría ser útil.

Answer 5

¡Muy bien! Primera implementación! (Java), en base de @Paul's respuesta:

List<Rectangle> slice(Rectangle r, Rectangle mask) 
{ 
     List<Rectangle> rects = new ArrayList(); 

     mask = mask.intersection(r); 

     if(!mask.isEmpty()) 
     { 
       rects.add(new Rectangle(r.x, r.y, r.width, mask.y - r.y)); 
       rects.add(new Rectangle(r.x, mask.y + mask.height, r.width, (r.y + r.height) - (mask.y + mask.height))); 
       rects.add(new Rectangle(r.x, mask.y, mask.x - r.x, mask.height)); 
       rects.add(new Rectangle(mask.x + mask.width, mask.y, (r.x + r.width) - (mask.x + mask.width), mask.height)); 

       for (Iterator<Rectangle> iter = rects.iterator(); iter.hasNext();) 
         if(iter.next().isEmpty()) 
           iter.remove(); 
     } 
     else rects.add(r); 

     return rects; 
} 

List<Rectangle> inverse(Rectangle base, List<Rectangle> rects) 
{ 
     List<Rectangle> outputs = new ArrayList(); 
     outputs.add(base); 

     for(Rectangle r : rects) 
     { 
       List<Rectangle> newOutputs = new ArrayList(); 

       for(Rectangle output : outputs) 
       { 
         newOutputs.addAll(slice(output, r)); 
       } 

       outputs = newOutputs; 
     } 
     return outputs; 
} 

Posiblemente trabajo Ejemplo de implementación here