Recherche de rectangles dans une grille à deux blocs

Appeler la largeur et la hauteur de l'entrée de la matrice de W et H, respectivement.

1. Exécuter cet ingénieux O(WH) algorithme pour déterminer le plus grand rectangle, mais au lieu de suivre seulement le plus grand rectangle, pour chaque (x, y) de l'emplacement d'enregistrement dans un W*H la matrice de la largeur et de la hauteur (l'un ou l'ensemble des) plus grands rectangles dont l'angle supérieur gauche est (x, y), la mise à jour de ces valeurs, comme vous allez.
2. Boucle au travers de cette matrice, l'ajout de chaque suffisamment grand rectangle dans max-heap commandé par zone (largeur * hauteur).
3. Lire les entrées de ce tas; ils seront produits dans la diminution de la zone de commande. Avec chaque entrée de lecture dont l'angle supérieur gauche est (x, y) et qui a la largeur w et de hauteur h, de marque chaque wh établissements inclus dans le rectangle comme "utilisé" dans un WH tableau de bits. Lors de la lecture des rectangles dans le tas, il nous faut rejeter toutes les rectangles qui contiennent "utilisé" des places pour éviter de produire chevauchement des rectangles. Il suffit de vérifier simplement la quatre bords de chaque candidat rectangle à l'encontre de la "utilisé" tableau, puisque le seul autre moyen que le candidat rectangle pourraient se chevaucher un autre rectangle serait si le dernier rectangle a été entièrement contenu par elle, ce qui est impossible en raison du fait que nous sommes la lecture des rectangles dans la diminution de la zone de commande.

Cette approche est "gourmand" dans la mesure où elle ne garantit pas de choisir la plus grande séquence de rectangles en général lorsqu'il y a plusieurs façons de se tailler une solide couleur de la région dans maximale des rectangles. (E. g. il pourrait être qu'il y a plusieurs rectangles dont l'angle supérieur gauche est à (10, 10) et qui ont une superficie de 16: 16x1, 8x2, en 4x4, en 2x8, 1x16. Dans ce cas, un choix peut produire de plus grosses rectangles "en aval", mais mon algorithme ne garantit pas à faire ce choix.) Si nécessaire, vous pouvez trouver l'ensemble optimal des séries de rectangles à l'aide de recul, bien que je soupçonne que cela pourrait être très lent dans le pire des cas.

La maximale du rectangle algorithme-je mentionner est conçu pour une seule couleur des rectangles, mais si vous ne pouvez pas s'adapter à votre multi-couleur de problème, vous pouvez simplement exécuter une fois pour chaque couleur avant de commencer l'étape 2.

Remarque: cela fonctionne sur l'hypothèse que vous essayez de trouver le plus grand k rectangles.

Nous savons que nous devons, dans le pire des cas, regardez chaque nœud de la grille au moins une fois. Cela signifie que notre meilleur des cas pire-cast est O(len*wid).

Votre force brute va être O(len*len*wid*wid) avec l'approche naïve de "Vérification pour les rectangles en un point est O(len*wid)et vous n'avez que O(len*wid) fois.

Il se peut que vous trouvez que cela n'est pas le cas, comme à chaque fois que vous trouvez un rectangle, vous avez un potentiel à réduire le problème de l'espace. Une approche par force brute de "vérifier chaque rectangle" je sens que va être la meilleure approche. Il y a des choses que vous pouvez faire pour l'accélérer.

Algorithme de base:

for(x = 1 .. wid) {
    for(y = 1 .. len) {
        Rectangle rect = biggestRectOriginatingAt(x,y);
        //process this rectangle for being added
    }
}

• Garder une trace de la plus grande k rectangles. Comme vous allez le long, vous pouvez rechercher le périmètre de l'endroit où admissible rectangle peut être.

  Rectangle biggestRectOriginatingAt(x,y) {
      area = areaOf(smallestEligibleRectangle); //if we want the biggest k rect's, this
                                                //returns the area of the kth biggest
                                                //known rectangle thus far
  
      for(i = 1 .. area) {
          tempwid = i
          templen = area /i
  
          tempx = x + tempwid
          tempy = y + templen
  
          checkForRectangle(x,y,tempx,tempy); //does x,y --> tempx,tempy form a rectangle?
      }
  
  }
  

Cela vous permet d'obtenir de gros gains de performance vers la fin de vos grosses recherches (si c'est une petite recherche, vous ne gagnez pas autant mais vous ne vous inquiétez pas parce que c'est une petite recherche!)

Également, cela ne fonctionne pas aussi bien pour les plus aléatoire distrobutions.

• Une autre optimisation est d'utiliser une peinture de remplissage algorithme pour trouver le plus grand consécutives domaines. C'est O(len*wid)ce qui est un faible coût. Cela vous permettra de rechercher les zones les plus probables pour un grand rectangle.

Notez qu'aucune de ces approches réduire le pire des cas. Mais, ils n'réduire le réel-monde s'attendait à temps de bon fonctionnement.