Discussion :

[sebcap26]

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.

[saturn1]

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

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

[sebcap26]

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.

[saturn1]

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.

[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 :

  Sélectionner tout - Visualiser dans une fenêtre à part

  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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[sebcap26]

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.

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 :

  Sélectionner tout - Visualiser dans une fenêtre à part

  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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.