Algorithme pour «guérir» plusieurs rectangles en un plus petit nombre de rectangles?

13

entrez la description de l'image ici

Disons que j'ai une grille de rectangles de formes et de couleurs différentes et que je veux réduire (raisonnablement proche de l'optimal est bien, optimal n'est pas nécessaire) le nombre de rectangles pour représenter la même disposition de couleurs.

L'image ci-dessus est un cas très simplifié et l'espace entre les rectangles est uniquement destiné à la visualisation - ils seraient en fait très serrés.

Quel est le nom d'une approche ou d'un algorithme (content de google) qui peut m'aider à le faire?

algorithm geometry space-partitioning xaxxon
la source
3
Pouvez-vous nous dire un peu d'où viennent ces rectangles? Ont-ils tendance à (grossièrement) s'aligner sur une grille sous-jacente, ou partager un bloc de construction commun, ou un plus petit rectangle "atomique"? Peuvent-ils être tournés? Cela ressemble au type de problème qui peut être très épineux dans le cas le plus général, mais peut devenir beaucoup plus facile si nous pouvons exploiter certaines contraintes ou points communs dans votre scénario particulier.
DMGregory
Il y a une grille sous-jacente de carrés (comme un damier) et chaque rectangle partage les frontières avec ces carrés sous-jacents. c'est-à-dire que vous pouvez utiliser un entier pour décrire le haut / bas / gauche / droite de chaque rectangle. Ils ne peuvent donc pas tourner dans des angles non divisibles de 90 degrés. De plus, la grille NxM est entièrement remplie de rectangles - il n'y a aucune position de grille découverte.
xaxxon
J'essaie juste d'éviter le cas qui ressemble à l'exemple ci-dessus (du point de vue de la coloration), mais il est composé d'une tonne de rectangles 1x1 et je traite chacun d'eux lorsque je peux gérer l'espace dans de nombreux moins d'appels.
xaxxon
Je suppose qu'une sorte de "commencez quelque part et continuez d'essayer des rectangles de plus en plus gros dans une dimension (par exemple verticalement) jusqu'à ce que vous atteigniez une bordure de couleur, puis augmentez l'autre dimension (horizontalement) jusqu'à ce que vous atteigniez une bordure. Ensuite, essayez d'abord horizontalement .Ensuite, essayez peut-être uniquement les carrés (en croissance en diagonale). Mais ne savez pas si la sélection de la plus grande des 3 possibilités ci-dessus est la bonne approche.
xaxxon
Est-il acceptable de diviser un rectangle existant, si cela aboutit à moins de rectangles à la fin? Ou l'algorithme ne devrait-il jamais fusionner? En outre, le nombre total est-il le seul critère, ou préférez-vous les formes plus carrées aux longs maigres maigres / grands rectangles qu'aux plus petits?
DMGregory

Réponses:

15

Tout d'abord, nous pouvons convertir vos rectangles source en cellules dans votre grille sous-jacente, pour rendre l'entrée plus uniforme. (Rastériser efficacement le problème)

Cela nous permettra de trouver des optimisations qui pourraient ne pas être évidentes lorsque vous travaillez directement avec les rectangles source - en particulier lorsqu'il s'agit de fractionner plusieurs rectangles source pour les recombiner différemment.

Exemple de conversion de rectangles en cellules de grille et inversement

Ensuite, nous pouvons trouver des régions connectées de la même couleur, en utilisant des algorithmes de recherche en profondeur en premier ou de remplissage par inondation. Nous pouvons considérer chaque région connectée (un polyomino ) isolément - rien de ce que nous faisons à une région différente n'a besoin d'influencer celle-ci.

En effet, nous voulons trouver un moyen de disséquer ce polyomino en rectangles (malheureusement, la plupart de la littérature que je peux trouver concerne le problème opposé: disséquer des rectangles en polyominos! Cela rend la recherche de pistes difficile ...)

Une méthode simple consiste à combiner des parcours horizontaux de carrés adjacents en longs rectangles maigres. Ensuite, nous pouvons comparer avec la ligne ci-dessus et combiner si nos débuts et fins de course correspondent - soit lorsque nous terminons chaque course / ligne, soit lorsque nous considérons que chaque cellule s'ajoute à la course actuelle.

Décomposition d'un polyomino en parcours horizontaux, puis fusion verticale

Je ne sais pas encore à quel point cette méthode est optimale. Il semble qu'il puisse rencontrer quelques problèmes lorsqu'une ligne qu'il n'a pas encore envisagée suggère une division différente de celle des lignes qu'il a vues jusqu'à présent:

Exemple de cas avec une solution à 3 rectangles, où la méthode ci-dessus trouve 4

Détecter quand une course / un rectangle est exactement couvert par des courses au-dessus et en dessous, puis le diviser et les fusionner résoudra ce cas particulier, mais je n'ai pas exploré à quel point le problème est général.

J'ai également examiné les méthodes permettant de parcourir le périmètre du polyomino et de couper à chaque fois que nous rencontrons un coin concave, mais cette approche me semble plus sujette aux erreurs. L'obtention de résultats optimaux semble nécessiter de hiérarchiser les coupes qui joignent deux coins concaves, et les formes contenant des creux nécessitent une manipulation spéciale, de sorte que la méthode de balayage des lignes semble avoir l'avantage de la simplicité.

Une autre méthode que je regarde est de prendre la première manche trouvée dans la rangée du haut et de l'étendre aussi loin que possible. Ensuite, faites la première course dans la rangée supérieure de ce qui reste ... Cela se déclenche cependant sur les formes en T inversé, donc ce n'est pas optimal non plus.

J'ai l'impression qu'il y a probablement un moyen d'utiliser la programmation dynamique pour trouver la répartition optimale, mais je ne l'ai pas encore trouvée.

DMGregory
la source
Merci pour la réponse géniale! cette solution semble assez rapide pour que je puisse l'exécuter dans plusieurs directions différentes et choisir celle qui semble la meilleure - horizontale gauche-> droite, horizontale droite-> gauche, puis verticale dans chaque sens également.
xaxxon
2
Le problème est que nous pouvons construire des formes qui induiront l'algorithme en erreur dans toutes les directions de balayage. Celles-ci pourraient ne pas apparaître en utilisation réelle, mais cela me dérange toujours. Je pense qu'il y a encore une solution simple ... Quelque chose comme noter à chaque manche, s'il y a des coins concaves au-dessus de lui à mi-course. Ensuite, si un cycle suivant se termine exactement à un tel point, nous revenons en arrière sur les parcours ci-dessus en les divisant verticalement. Je n'ai pas encore trié tous les détails.
DMGregory
1
De plus, je ne sais pas pourquoi l'étape de remplissage par inondation est nécessaire. Lorsque vous passez d'une position de grille à un long rectangle maigre, vous pouvez simplement parcourir toute la ligne ou la colonne de la grille (quelle que soit la façon dont vous allez) pour créer ces rectangles 1xN. Pas besoin de connaître le polyomino, non?
xaxxon
Vous avez raison, le remblayage n'est pas une étape nécessaire. Je l'ai inclus pour justifier de se concentrer sur une seule région colorée à la fois dans les étapes suivantes, mais vous pouvez facilement appliquer la méthode de balayage des lignes à plusieurs régions colorées entrelacées. La méthode basée sur le périmètre doit cependant travailler sur le périmètre d'une forme à la fois.
DMGregory