Discussion :

[AlainM60]

Bonjour,

Je suis à la recherche d'un algorithme ou d'un code permettant de remplir un polygone avec des rectangles.
Je ne trouve rien pourtant je me doute que quelque chose doit exister. Peut être que je n'utilise pas les bons mots clés.

Merci pour votre aide.

[dinobogan]

Y-a-t-il d'autres contraintes comme par exemple un nombre maximum de rectangles ?
Tout le polygone doit-il être rempli ?
Et enfin, uniquement par curiosité : ça te servira à quoi ?

[AlainM60]

bonjour,
non pas de limitation sur le nombre de rectangle.
Oui le polygone doit etre rempli.
Je fait des analyses avec un instrument et sur des images je choisis une zone d'interet quelconque. L'instrument n'accepte que des zones rectangulaires a analyser.

[dinobogan]

Y-a-t-il des contraintes sur tes polygones, comme par exemple nombres maximum de côtés, convexe, concave... ?
Lorsque le polygone sera rempli de grands rectangles, les derniers rectangles ne contiendront que quelques pixels. Est-ce nécessaire de ne pas déborder du polygone ?
Un polygone est-il assez petit pour être modélisé par une patrice de pixel ? Car dans le cas contraire, il faudra ajouter une technique de parcours du polygone via une map à échelle réduite.

Je vois essentiellement 2 approches :

1. méthode algébrique, intersection de droites. Peut importe la taille du polygone.
2. méthode par remplissage d'une matrice de points. Le polygone doit être assez petit pour tenir en RAM. Ou alors il faut réduire l'échelle.

La méthode par remplissage me semble la plus rapide à mettre en place, et probablement la plus simple. Tout d'abord, créer une matrice rectangulaire des points. Mettre -1 lorsque le point est hors du polygone, 0 sinon.
Ensuite, trouver le centre du polygone. Ce point est le début du premier rectangle, le marquer à 1. Tu vas tenter de l'agrandir dans toutes les directions. Chaque fois que tu parviens à ajouter une ligne au rectangle, tu marques avec des 1. Lorsque tu ne peux plus agrandir, tu choisis un point à 0, tu le marques à 2 puis tu tentes d'agrandir le rectangle.
A chaque nouveau rectangle, tu incrémentes la valeur de 1.
Le point problématique qui reste à résoudre est la méthode d'agrandissement. En effet, si tu agrandis au maximum en largeur, tu vas très vite être bloqué pour l'agrandissement en hauteur. tu peux peut-être tenter de trouver des carrés au lieu de rectangle pour le début de l'algo. Au fur et a mesure que le découpage avance, il sera préférable d'utiliser des rectangles pour limiter ne nombre total de découpage.
Il va falloir expérimenter par toi-même.