Algorithme pour trouver le moins rectangles pour couvrir un ensemble de rectangles, sans chevauchement
j'ai un ensemble de rectangles et je voudrais à "réduire" le jeu alors que j'ai le plus petit nombre de rectangles pour décrire la même région que le jeu original. Si possible, j'aimerais qu'elle aussi être rapide, mais je suis plus préoccupé par obtenir le nombre de rectangles aussi bas que possible. J'ai une approche qui fonctionne la plupart du temps.
actuellement, je commence en haut à gauche le plus rectangle et voir si je peux l'étendre à droite et en bas tout en gardant un rectangle. Je le fais jusqu'à ce qu'il ne puisse plus s'étendre, supprimer et diviser tous les rectangles qui se croisent, et ajouter le rectangle élargi de nouveau dans la liste. Puis je commence le processus à nouveau avec le prochain rectangle en haut à gauche, et ainsi de suite. Mais dans certains cas, il ne fonctionne pas. Exemple:
avec cet ensemble de trois rectangles, la bonne solution se terminerait par deux rectangles, comme ceci:
Cependant, en dans ce cas, mon algorithme commence par traiter le rectangle bleu. Cela s'étend vers le bas et divise le rectangle jaune (correctement). Mais ensuite, quand le reste du rectangle jaune est traité, au lieu de s'étendre vers le bas, il se dilate d'abord à droite et reprend la partie qui était auparavant séparée. Puis le dernier rectangle est traité et il ne peut pas s'étendre à droite ou vers le bas, de sorte que l'ensemble original de rectangles est gauche. Je peux modifier l'algorithme pour étendre d'abord vers le bas et ensuite vers la droite. Que cela résoudrait ce cas, mais cela causerait le même problème dans un scénario similaire qui a été retourné.
Edit: juste pour clarifier, l'ensemble original de rectangles ne se chevauchent pas et ne doivent pas être connectés. Et si un sous-ensemble de rectangles sont connectés, le polygone qui les couvre complètement peut avoir des trous en elle.
2 réponses
malgré le titre de votre question, je pense que vous êtes en fait à la recherche du minimum dissection dans les rectangles d'un polygone rectiligne. (Les liens de Jason sont environ minimum couvre par rectangles, ce qui est tout à fait un problème différent.)
David Eppstein examine ce problème dans la section 3 de son 2010 article de sondage graphique-Solutions théoriques à la géométrie computationnelle Problèmes , et il donne un résumé agréable dans cette réponse sur mathoverflow.net :
l'idée est de trouver le nombre maximum d'axes disjoints-diagonales parallèles qui ont deux sommets concaves comme points terminaux, se divisent le long de ceux-ci, puis forment une Division de plus pour chaque vertex concave restant. Pour trouver le nombre maximum d'axes disjoints-diagonales parallèles, formez le graphe d'intersection des diagonales; ce graphe est bipartite donc son jeu indépendant maximum peut être trouvé dans le temps polynomial par des techniques de correspondance de graphe.
voici mon gloss sur cette description admirablement laconique, en utilisant la figure 2 de L'article D'Eppstein. Supposons que nous ayons un polygone rectiligne, peut-être avec des trous.
lorsque le polygone est disséqué en rectangles, chacun des sommets concaves doit être rencontré par au moins un bord de la dissection. Si nous obtenons la dissection minimum si le plus grand nombre de ces arêtes font double usage, c'est-à-dire qu'elles relient deux des sommets concaves.
dessinons donc les diagonales axis-parallèles entre deux sommets concaves qui sont entièrement contenus à l'intérieur du polygone. (L ‘ "axe parallèle" signifie "horizontale ou à la verticale" par-ci, un diagonale d'un polygone est une ligne reliant les deux sommets adjacents. Nous voulons utiliser comme bon nombre de ces les lignes que possible dans la dissection tant qu'ils ne se coupent.
(s'il n'y a pas de diagonales axiales parallèles, la dissection est triviale-il suffit de faire une coupe à partir de chaque sommet concave. Ou s'il n'y a pas d'intersections entre les diagonales axis-parallèles alors nous les utilisons toutes, plus une coupe de chaque vertex concave restant. Sinon, lisez la suite.)
Le intersection graphique d'un ensemble de segments de ligne a un noeud pour chaque segment de ligne, et un bord joint deux noeuds si les lignes se croisent. Voici le graphique d'intersection pour les diagonales axis-parallèles:
c'est bipartite avec les diagonales verticales dans une partie, et les diagonales horizontales dans l'autre partie. Maintenant, nous voulons choisir autant de diagonales que possible tant qu'elles ne se croisent pas. Cela correspond à trouver le ensemble indépendant maximum dans le graphique d'intersection.
trouver l'ensemble indépendant maximum dans un graphe général est un problème NP-hard, mais dans le cas particulier d'un graphe bipartite, théorème de König montre qu'il est équivalent au problème de trouver un maximum d'appariement, qui peut être résolu en temps polynomial, par exemple par le Hopcroft–algorithme Karp . Un graphique donné peut avoir plusieurs maximum de couplages, mais l'un d'eux va faire, comme ils ont tous la même taille. Dans l'exemple, tous les couples maximum ont trois paires de Sommets, par exemple {(2, 4), (6, 3), (7, 8)}:
(les Autres maximum couplages dans ce graphique inclure {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; et {(1, 3), (2, 4), (7, 8)}.)
pour obtenir d'un maximum correspondant à la minimum vertex couverture , appliquer la preuve du théorème de König . Dans la correspondance indiqué ci-dessus, la gauche est L = {1, 2, 6, 7}, le droit est R = {3, 4, 5, 8}, et l'ensemble des sommets inégalés dans L est U = {1}. Il n'y a qu'un seul chemin alternatif à partir de U , à savoir 1-3-6, de sorte que l'ensemble des sommets dans les chemins alternatifs est Z = {1, 3, 6} et la couverture de vertex minimum est donc K = ( l \ Z ) ( R փ Z ) = {2, 3, 7}, montré en rouge ci-dessous, avec le maximum indépendant fixé en vert:
traduisant ceci en Problème de dissection, cela signifie que nous pouvons utiliser cinq diagonales axis-parallèles en la dissection:
enfin, faire une coupe à partir de chaque sommet concave restant pour compléter la dissection:
Voici quelques articles académiques de discuter des solutions à ce problème;
algorithme D'Approximation du temps linéaire pour la couverture rectangulaire Minimum (Ceci est pour couvrir les polygones donc c'est un cas plus général que ce que vous avez présenté ici).
Optimum Rectangle Covers for Convex Rectinlinear Polygons (celui-ci est plus dans le sens de votre problème spécifique)
, Vous pouvez aussi essayer de ici pour une bibliographie de plus de papiers sur ce sujet.