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.
Partager