Remplissage d'une surface en un minimum de rectangles

Bonjour,

Voilà quelques semaines maintenant que je me casse la tête sur un problème qui a priori ne doit pas être très compliqué. Je pense qu'il doit exister des algorithmes répondant à mon besoin, mais je n'ai rien trouvé. J'ai donc commencé à développer ma propre solution (qui n'est certainement pas optimisée au maximum, mais qui répond correctement au besoin). Le problème c'est que c'est un peu "bricolage" comme solution et que j'ai régulièrement des cas de figure qui ne fonctionnent pas.

Bon, fini de parler, je passe au problème en lui même.

J'ai une surface rectangulaire en 2D que je veux remplir à l'aide de rectangles, en tenant compte de certaines contraintes, à savoir des carrés qui ne doivent pas être remplis.
La surface est découpée en "tuiles", c'est à dire des carrés toujours de même dimensions (qu'on appellera des carrés de 1 "unité"). Les carrés ne devant pas être remplis ("trous") font systématiquement 1 unité de côté.

Je cherche une fonction qui prendrait en entrée deux paramètres :
- La taille de la surface (vecteur (x, y) d'entiers positifs non nuls)
- La liste des trous (liste de vecteurs (x, y) d'entiers positifs)

L'idée serait qu'en sortie, j'aie une liste de rectangles (constitués de deux vecteurs, soit p1 + taille, soit p1 + p2).

Par exemple, si j'ai la surface suivante (X = plein, O = trou) :
XXXXXXXXXX
XXXOXXXXXX
XXXXXXXOXX
XXXXOXXXXX
Qui correspondrait donc aux deux paramètres d'entrée (les coordonnées commencent par 0, l'origine étant en haut à gauche) :
- Taille = (10, 4)
- Trous = [(3, 1), (7, 2), (4, 3)]

En sortie, je souhaite avoir un résultat de ce type :
XXXXXXXXXX
XXXOXXXXXX
XXXXXXXOXX
XXXXOXXXXX
Donc la liste de rectangles suivante :
- Position = (0, 0) / Taille = (3, 4)
- Position = (3, 0) / Taille = (1, 1)
- Position = (4, 0) / Taille = (6, 2)
- Position = (3, 2) / Taille = (1, 2)
- Position = (4, 2) / Taille = (1, 1)
- Position = (5, 2) / Taille = (2, 2)
- Position = (7, 3) / Taille = (1, 1)
- Position = (8, 2) / Taille = (2, 2)


Plus concrètement, je développe un jeu en WebGL, et j'ai un "mur" d'une taille donnée et avec des ouvertures définies (toujours d'une taille pré-définie) pour insérer des fenêtres, portes, couloirs ... Je souhaite dessiner le mur en question de manière optimisée et en un minimum de triangles. Je veux éviter, pour un mur d'une taille de 10x10 par exemple, de me retrouver avec 100 carrés (200 triangles) à dessiner (ce qui serait le plus simple, mais pas satisfaisant) si je peux le faire en 4.

Savez vous si un tel algorithme existe déjà et quel est son nom ? D'autres pistes ou idées ?

Merci,

Cordialement.

Salut, moi j'essaierai de partir qu'avec des rectangles unités et tant que je peux je les fusionne.
Ca ne donnera pas la solution optimale mais ca sera rapide:aie:

Sinon tu brutesforces sur la fusion pour avoir la solution optimale mais il doit y avoir des techniques plus intelligentes.

Merci pour ta réponse.

C'est effectivement ce que j'ai déjà tenté, mais j'ai régulièrement des cas de figure qui ne fonctionnent pas correctement (trous qui sont remplis, espaces à remplir qui sont laissés vides). C'est pour ca que je me disais qu'il y a sans doute déjà des solutions plus fiables pour réaliser ca.

Je ne suis pas spécialement attaché à trouver LA solution optimale, juste une solution qui réduise grandement le nombre de rectangles.

Citation:

---

mais j'ai régulièrement des cas de figure qui ne fonctionnent pas correctement (trous qui sont remplis, espaces à remplir qui sont laissés vides).

---

C'est que tu dois faire une erreur dans ton code.
Poste le code si ce n'est pas trop lourd.

Bonjour. À partir de l'idée de saturn, j'ai peut-être quelque chose qui peut t'être utile. On part sur un système d'enchère : chaque carré unité va enchérir sur ses voisins en investissant une somme qui est proportionnelle à la taille qu'il atteindrait s'il fusionnait avec ces unités. Une fois ce pré-traitement fait, on résout les enchères.

La solution obtenue ne sera pas la meilleure, mais elle sera bonne (optimum local).

ABCDEFGH
I_JKLMNO
PQRS_TUV
WXYZ1234

ÉTAPE 1, ENCHÈRES :

• A peut s'étendre vers la droite ou vers le bas, mais pas les deux à la fois :
  enchère(A,B,8) (parce que le rectangle A...H fait huit unités)
  enchère(A,C,8)
  ...
  enchère(A,H,8)
  enchère(A,I,4) (parce que le rectangle A...W fait quatre unités)
  ...
  enchère(A,W,4)
  
• I peut s'étendre en haut et en bas :
  enchère(I, A, 4) ... enchère (I, W, 4)
  
• P :
  enchère(P, A|I, 4)
  enchère(P, Q|R|S|W|X|Y|Z, 8)
  
• etc.

ÉTAPE 2, RÉSOLUTION :

• L'unité A est payée 8 par les unités B à H ; 4 par les unités I à W. On est donc tenté de fusionner (A…H) mais F G et H sont payés 12 par MNOTUV234. Ainsi, on fusionne ABCDE pour 5 points.
  
• L'unité F est déjà traitée ; aucune des unités FGHMNOTUV234 n'est mieux payée que 12 ; on fusionne ce rectangle. Voici où on en est :
  Code:

  ---

  1 2 3 4

  ABCDEFGH I_JKLMNO PQRS_TUV WXYZ1234

  ---

• L'unité I est payée 4 par A, P et W (alors que P et W ne peuvent plus que faire 3 vec I) mais P et W sont achetées 8 par PQRSWXYZ. Elle va donc rester seule.
  
• L'unité J récupère K et L
  
• PQRSWXYZ sont fusionnés
  
• 1 reste seul.

Résultat :

Code:

---

1 2 3 4

ABCDEFGH I_JKLMNO PQRS_TUV WXYZ1234

---

Comme annoncé, ce n'est pas forcément la meilleur solution, mais j'espère qu'elle te sortira du pétrin. Il est possible de l'améliorer en relançant les enchères à la fin de chaque fusion ; j'imagine que l'ordre dans lequel on traite les unités dans l'étape de résolution influe sur le résultat final.

Bon courage.

Citation:

---

Envoyé par saturn1

C'est que tu dois faire une erreur dans ton code.
Poste le code si ce n'est pas trop lourd.

---

Merci, mais j'ai déjà corrigé les bugs dont je parlais, le problème c'est que j'en ait régulièrement et qu'il y a peut être une solution plus fiable. Si j'en retrouve, je veux bien poster mon code, mais le problème n'est pas tant la correction d'un bug , c'est plutôt la fiabilité de l'ensemble.

Dans mon code, j'itère tout simplement en x et y, et je fusionne les carrés adjacents autant que possible durant ce parcours.

Citation:

---

Envoyé par prgasp77

Bonjour. À partir de l'idée de saturn, j'ai peut-être quelque chose qui peut t'être utile. On part sur un système d'enchère : chaque carré unité va enchérir sur ses voisins en investissant une somme qui est proportionnelle à la taille qu'il atteindrait s'il fusionnait avec ces unités. Une fois ce pré-traitement fait, on résout les enchères.

La solution obtenue ne sera pas la meilleure, mais elle sera bonne (optimum local).

ABCDEFGH
I_JKLMNO
PQRS_TUV
WXYZ1234

ÉTAPE 1, ENCHÈRES :

• A peut s'étendre vers la droite ou vers le bas, mais pas les deux à la fois :
  enchère(A,B,8) (parce que le rectangle A...H fait huit unités)
  enchère(A,C,8)
  ...
  enchère(A,H,8)
  enchère(A,I,4) (parce que le rectangle A...W fait quatre unités)
  ...
  enchère(A,W,4)
  
• I peut s'étendre en haut et en bas :
  enchère(I, A, 4) ... enchère (I, W, 4)
  
• P :
  enchère(P, A|I, 4)
  enchère(P, Q|R|S|W|X|Y|Z, 8)
  
• etc.

ÉTAPE 2, RÉSOLUTION :

• L'unité A est payée 8 par les unités B à H ; 4 par les unités I à W. On est donc tenté de fusionner (A…H) mais F G et H sont payés 12 par MNOTUV234. Ainsi, on fusionne ABCDE pour 5 points.
  
• L'unité F est déjà traitée ; aucune des unités FGHMNOTUV234 n'est mieux payée que 12 ; on fusionne ce rectangle. Voici où on en est :
  Code:

  ---

  1 2 3 4

  ABCDEFGH I_JKLMNO PQRS_TUV WXYZ1234

  ---

• L'unité I est payée 4 par A, P et W (alors que P et W ne peuvent plus que faire 3 vec I) mais P et W sont achetées 8 par PQRSWXYZ. Elle va donc rester seule.
  
• L'unité J récupère K et L
  
• PQRSWXYZ sont fusionnés
  
• 1 reste seul.

Résultat :

Code:

---

1 2 3 4

ABCDEFGH I_JKLMNO PQRS_TUV WXYZ1234

---

Comme annoncé, ce n'est pas forcément la meilleur solution, mais j'espère qu'elle te sortira du pétrin. Il est possible de l'améliorer en relançant les enchères à la fin de chaque fusion ; j'imagine que l'ordre dans lequel on traite les unités dans l'étape de résolution influe sur le résultat final.

Bon courage.

---

Merci, c'est intéréssant comme procédé. Ca pourrait effectivement donner une solution plus optimisée (dans son résultat) que ce que je fais actuellement. Par contre j'ai peur que le traitement en devienne beaucoup plus lourd.

Citation:

---

Envoyé par sebcap26

Par contre j'ai peur que le traitement en devienne beaucoup plus lourd.

---

On parle de quel ordre de grandeur pour le nombre de cellules-unité ?

Citation:

---

Envoyé par prgasp77

On parle de quel ordre de grandeur pour le nombre de cellules-unité ?

---

- Il y aura un ensemble de batiments. J'estime à une dizaine très grand maximum le nombre de batiments visibles en même temps, mais la plupart du temps il n'y en aura qu'un ou deux visibles.
- Les batiments seront constitués de pièces. Le nombre nombre de pièces par batiment dépendra du joueur puisque c'est un jeu axé sur la construction. Il pourra aller théoriquement jusqu'a l'infini. Dans la pratique, je table sur un nombre pouvant largement dépasser la centaine pour les plus gros joueurs. En moyenne, on peut tabler sur une cinquantaine.
- Chaque pièce aura 4 murs sur lesquels s'appliquera l'algorithme en question. Au niveau de la taille des pièces, ce sera également théoriquement infini, mais dans la pratique on ne devrait pas beaucoup voir de taille supérieure à 5 unités au cube (25 unités par mur). En moyenne, on peut partir sur une taille de 2 unités au cube, donc 4 unités par mur.

On peut donc partir sur un maximum de 10*100*4*25 = 100 000 unités si on part sur 100 pièces par batiment (ce sera plus a mon avis).
En moyenne, on aura 2*50*4*4 = 1600.

Entre nos deux algorithmes, le mien est probablement plus rapide a s'éxecuter, mais le tien peut potentiellement réduire beaucoup plus le nombre de rectangles.
C'est assez difficile de juger le gain des deux côtés : est-ce qu'il vaut mieux allonger les temps de chargement mais rendre l'ensemble peut être plus fluide (sans pouvoir connaître précisément la différence de "rendement" des deux algorithmes) ?

Je suis un peu fatigué, je ne vois pas le rapport entre l'algo et la description de ton jeu. Tu m'as perdu au moment où j'ai lu « unité au cube ».

Autre méthode, tu pars d'un rectangle plein et tu "ajoutes" un trou. Ca segmente le rectangle en 8 régions (au max) que l'on peut facilement refusionner en rectangles.

Et on recommence en ajoutant un autre trou dans l'un des rectangles...

XXXXXXXXXX    XXXXXXXXXX    1112333333    1112888888
XXXXXXXXXX    XXXOXXXXXX    444O555555	  111O888888
XXXXXXXXXX    XXXXXXXXXX    6667888888	  1117888888
XXXXXXXXXX    XXXXXXXXXX    6667888888	  1117888888

Bonjour,

Dans la littérature tu as des articles intéressants comme celui de David Eppstein Graph-Theoretic Solutions to Computational Geometry Problems, notamment la partie 3 "Partition into rectangles" qui discute de la partition d'un polygone orthogonal (deux arrêtes disjointes quelconques sont soit parallèles soit orthogonales) en un nombre minimum de rectangle, le polygone pouvant comporter des trous de la forme d'un polygone orthogonal : ce qui est ton cas de figure, sauf si tu peux avoir des trous adjacents auquel cas il faudra les fusionner ...
Bonne lecture :)