Algoritmo requerido para determinar si un rectángulo está completamente cubierto por otro conjunto de rectángulos

Question

Estoy buscando un algoritmo que determine si un nuevo rectángulo está completamente cubierto por un conjunto de rectángulos existentes. Otra forma de plantear la pregunta es si el nuevo rectángulo existe completamente con el área cubierta por los rectángulos existentes.

Parece que hay muchos algoritmos para determinar la superposición de rectángulo, etc., pero realmente no puedo encontrar nada que resuelva este problema exacto.

Los rectángulos se representarán utilizando las coordenadas x, y. Este problema se relaciona con el mapeo geográfico.

Editar - desde comentario publicado por el OP:

Los rectángulos están alineados en el eje X/Y

Answer 1

he hecho algo similar en el pasado. la idea era comparar el nuevo rectángulo con cada uno de los existentes (uno por uno)

si hay una intersección se descarta que (la parte de intersección), y añadir segmentos al descubierto a una matriz rectangular

siguiente, buscar la intersección entre los nuevos segmentos y otros rectángulos existentes (aún no verificados).

realiza el algoritmo descartando recursivamente las intersecciones, y dejando solo las partes descubiertas.

al final, si no hay rectángulos de la matriz, que tienen una superposición completa

si todavía hay algunos rectángulos de la matriz, la superposición no es completa ya que todavía hay algunas partes que quedan.

espero que esta ayuda

puedo tratar de encontrar el código de si esto es lo que busca. Creo que está en C#

Otra idea es convertir todos los rectángulos existentes en un polígono, y luego verificar si hay un nuevo rectángulo dentro del polígono, pero no recomendaría esto si no estás usando un lenguaje (o framework) que sabe cómo trabajar con polígonos.

Answer 2

Si todos los rectángulos tienen el mismo ángulo; entonces el siguiente me podría ser más eficiente y más fácil de programar:

Determine para cada coordenada y qué rectángulos cubren esa coordenada y (solo tiene que hacer esto para las coordenadas y en las que cambia la cubierta, es decir, que corresponden a la límite inferior de un rectángulo). Una vez que sepa eso, resuelva el problema para cada coordenada y (es decir, verifique si todos los valores x están cubiertos por los rectángulos que están "activos" para esa coordenada Y).

Editar: Creo que esto es O (n^2 log (n)^2) la complejidad, como dos tipos son todo el trabajo duro que tiene que hacer

Answer 3

Si rectángulos están alineados Eso es fácil:

Digamos que tiene el rectángulo A0 y quiere saber si está completamente cubierto por (B1, B2, B3 ...) = B

A := (A0) 
while P := pop B 
    for R in A 
    if P fully covers R: 
     remove R from A 
    else if P and R does overlap: 
     remove R from A 
     break R in subrentangles S := (S1, S2, S3,...) following the intersections \ 
                with P edges 
     push S into A 
if A is empty: 
    say B covers A0 
else: 
    say B does not fully cover A0 

Answer 4

R-tree puede ser útil. si hubiera rectángulos girados, puede encerrarlos en rectángulos delimitadores.

Answer 5

Prueba este

Fuente Rectángulo: X0, Y0, anchura, altura

// Básicamente comparando los bordes

if (((X0> = xi) & & (X0 + anchura < Xi =)) & & ((Y0> = Yi) & & (Y0 + alto < = Yi)) {// consideran el rectángulo } else { // descartar }

Answer 6

aquí es mi código, como usted pidió: (partes descubiertas retornos)

el primer método "Resta" de 2 rectángulos.

el segundo método resta una lista de rectángulos del rectángulo base.

en su lista de casos contiene rectángulos existentes y el nuevo es la base

para comprobar si hay una intersección completa la lista devuelta desde el segundo método no debería tener elementos.

public static List<Rectangle> SubtractRectangles(Rectangle baseRect, Rectangle splitterRect) 
    { 
     List<Rectangle> newRectaglesList = new List<Rectangle>(); 

     Rectangle intersection = Rectangle.Intersect(baseRect, splitterRect); 
     if (!intersection.IsEmpty) 
     { 
      Rectangle topRect = new Rectangle(baseRect.Left, baseRect.Top, baseRect.Width, (intersection.Top - baseRect.Top)); 
      Rectangle bottomRect = new Rectangle(baseRect.Left, intersection.Bottom, baseRect.Width, (baseRect.Bottom - intersection.Bottom)); 

      if ((topRect != intersection) && (topRect.Height != 0)) 
      { 
       newRectaglesList.Add(topRect); 
      } 

      if ((bottomRect != intersection) && (bottomRect.Height != 0)) 
      { 
       newRectaglesList.Add(bottomRect); 
      } 
     } 
     else 
     { 
      newRectaglesList.Add(baseRect); 
     } 

     return newRectaglesList; 
    } 

    public static List<Rectangle> SubtractRectangles(Rectangle baseRect, List<Rectangle> splitterRectList) 
    { 
     List<Rectangle> fragmentsList = new List<Rectangle>(); 
     fragmentsList.Add(baseRect); 

     foreach (Rectangle splitter in splitterRectList) 
     { 
      List<Rectangle> toAddList = new List<Rectangle>(); 

      foreach (Rectangle fragment in fragmentsList) 
      { 
       List<Rectangle> newFragmentsList = SubtractRectangles(fragment, splitter); 
       toAddList.AddRange(newFragmentsList); 
      } 

      if (toAddList.Count != 0) 
      { 
       fragmentsList.Clear(); 
       fragmentsList.AddRange(toAddList); 
      } 
     } 

     return fragmentsList; 
    } 

Answer 7

Puede usar el algoritmo que se usa para calcular el área de unión de los rectángulos. Como quiera verificar si el rectángulo a está cubierto por los rectángulos B = {b_1, b_2, ...,}.

Primero calcula el área de unión de rectángulos en B, obtenemos el área_1 como valor.

Luego calcula el área de unión de rectángulos en B + {a}, obtenemos area_2 como valor.
Si area_1 == area_2, entonces está seguro de que el rectángulo a está cubierto por los rectángulos B. De lo contrario, la respuesta es falsa.

Así que el problema principal es cómo calcular el área de unión de rectángulos. Este problema puede resolverse mediante un excelente algoritmo existente. Este algoritmo se puede presentar brevemente como el primero en discretizar el valor de los puntos de los rectángulos y luego usar el árbol de segmentación para acelerar el cálculo de las áreas de cada bloque.