Algorithme requis pour déterminer si un rectangle est complètement couvert par un autre ensemble de rectangles

Question

Je cherche un algorithme qui déterminera si un nouveau rectangle est complètement couvert par un ensemble de rectangles existants. Une autre façon de poser la question, est-ce que le nouveau rectangle existe complètement avec la surface couverte par les rectangles existants?

Il semble y avoir beaucoup d'algorithmes pour déterminer le chevauchement rectangle et ainsi de suite, mais je ne peux pas vraiment trouver quelque chose qui résout ce problème exact.

Les rectangles seront représentés en utilisant les coordonnées x, y. Ce problème concerne la cartographie géographique.

Modifier - de commentaire publié par l'OP:

Les rectangles sont alignés sur l'axe X/Y

Answer 1

J'ai fait quelque chose de similaire dans le passé. l'idée était de comparer le nouveau rectangle avec chacun des existant (un par un)

s'il y a une intersection jetez-(la partie recoupé), et ajouter des segments non couverts à un tableau rectangulaire

suivant, recherche d'intersection entre les nouveaux segments et d'autres rectangles existants (non cochés).

l'algorithme rejette récursivement les intersections et ne laisse que les parties non couvertes.

à la fin, s'il n'y a pas des rectangles dans le tableau, vous avez un chevauchement complet

s'il y a encore quelques rectangles dans le tableau, le chevauchement n'est pas plein car il y a encore certaines parties gauche.

Espérons que cela aide

Je peux essayer de trouver mon code si c'est ce que vous recherchez. Je pense que c'est en C#

une autre idée est de convertir tous les rectangles existants en un polygone, puis de vérifier si le nouveau rectangle est à l'intérieur du polygone, mais je ne le recommanderais pas si vous n'utilisez pas de langage (ou de cadre) qui sait comment travailler avec des polygones.

Answer 2

Si les rectangles ont tous le même angle; alors la suite pourrait être plus efficace et facile à programmer:

Déterminez pour chaque coordonnée y les rectangles qui couvrent cette coordonnée y (il vous suffit de le faire pour les coordonnées y auxquelles le revêtement change, c'est-à-dire qui correspondent à la partie supérieure ou limite inférieure d'un rectangle). Une fois que vous le savez, résolvez le problème pour chaque coordonnée y (c'est-à-dire vérifiez si toutes les valeurs x sont couvertes par les rectangles qui sont "actifs" pour cette coordonnée Y).

Edit: Je pense que c'est O (n^2 log (n)^2) la complexité, comme deux sortes sont tout le travail que vous devez faire

Answer 3

Si rectangles sont alignés qui est facile:

Disons que vous avez le rectangle A0 et que vous voulez savoir s'il est entièrement couvert par (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 peut être utile. S'il existe des rectangles pivotés, vous pouvez les encadrer dans des rectangles de délimitation.

Answer 5

Essayez cette

Source Rectangle: X0, Y0, largeur, hauteur

// Fondamentalement comparant les bords

if (((X0> = xi) & & (X0 + largeur < = Xi)) & & ((Y0> = Yi) & & (Y0 + hauteur < = Yi)) {// considérons le rectangle } else { // jeter }

Answer 6

voici mon code, comme vous avez demandé:

la première méthode "Soustrait" (retours de pièces non couvertes) de 2 rectangles. La seconde méthode soustrait une liste de rectangles du rectangle de base.

dans votre liste de cas contient des rectangles existants, et la nouvelle est la base

pour vérifier s'il y a une intersection complète la liste renvoyée de la deuxième méthode ne devrait pas avoir d'éléments.

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

Vous pouvez utiliser l'algorithme utilisé pour calculer la zone d'union des rectangles. Comme vous voulez vérifier si le rectangle a est couvert par des rectangles B = {b_1, b_2, ...,}.

D'abord, vous calculez la zone d'union des rectangles dans B, nous obtenons area_1 comme valeur.

Ensuite, vous calculez la zone d'union des rectangles dans B + {a}, nous obtenons area_2 comme valeur.
Donc, si area_1 == area_2, alors vous êtes sûr que le rectangle a est couvert par des rectangles B. Sinon, la réponse est fausse.

Donc, le problème principal est de savoir comment calculer la surface d'union des rectangles. Ce problème peut être résolu par l'excellent algorithme existant. Cet algorithme peut être brièvement introduit en tant que premier pour discrétiser la valeur des points de rectangles, puis en utilisant l'arbre de segmentation pour accélérer le calcul des zones de chaque bloc.