Décomposition de rectangles
Il y a quelques jours, j'ai été confronté à un problème que je devais résoudre en C# (j'ai d'ailleurs poster un message sur le forum pour voir si quelqu'un avait une idée). Le but est de pouvoir couper un morceau (un rectangle) d'un autre rectangle. Rien de mieux qu'une petite explication en image pour comprendre la situation :
Explication :
Sur l'image ci-contre, on veut supprimer le rectangle bleu du rouge. On prend donc l'intersection des deux (partie hachurée) et l'on supprime cette intersection au rectangle rouge. Le résultat final doit être:
Une collection de rectangles qui ne se recoupe plus (un bord ne peut pas appartenir à plusieurs rectangles).
La décomposition doit être minimal, c'est à dire que le résultat de la décomposition doit contenir le plus petit nombre de rectangle possible.
Le truc, c'est que dans certain cas, suivant la configuration des rectangles, on peut obtenir une intersection qui n'est pas un rectangle mais une ligne, voire même un point. Il faudra donc retirer au premier rectangle une ligne ou un point et non pas un rectangle. Voici des exemples où on devra retirer une ligne (premier et troisième cas) et un point (deuxième cas). Le résultat de la décomposition peut alors être un rectangle et/ou une ligne et/ou un point :
1) Retrait d'une ligne, décomposition: un rectangle et une ligne
2) Retrait d'un point, décomposition : un rectangle et une ligne
3) Retrait d'une ligne, décomposition : un rectangle et un point
Au début, je me suis dit que c'était assez complexe et j'ai donc commencé à dessiner tout les cas possible et croyez-moi sur parole, y'en a beaucoup ;-) Voici une partie des cas possible (ils ne sont pas tous là, il s'agit en fait seulement des cas où l'on supprime un rectangle et que le résultat est un rectangle) :
Puis au fur et à mesure que je codais chaque cas, j'ai constaté des similitudes. Finalement, après avoir longuement réfléchis (et accessoirement codé), j'ai réussi à faire une méthode assez simple qui est capable de découpe n'importe quelle configuration. J'ai crée une class Rectangle qui contient une méthode Cut, qui permet de retirer un Rectangle au rectangle courant, voici le prototype de cette méthode :
public List<Rectangle> Cut(Rectangle rectangle)
La méthode retourne donc une collection de rectangle après avoir découpé la partie souhaitée. La class complète se trouve dans le fichier .cs attaché; c'est pas très compliqué, mais c'est le genre de truc qui prend vite quelques heures et qui devient très compliqué si on commence à considérer chaque cas!
Pour terminé, voici un petit exemple d'utilisation de la class Rectangle:
1
2
3
4
5
6
7
8
9
10
11
12
|
// Create two rectangles
Rectangle r1 = new Rectangle(100, 200, 200, 300);
Rectangle r2 = new Rectangle(200, 100, 200, 300);
// Calculate the intersection
Rectangle intersection = r1.Intersect(r2);
if(intersection != null) // If there is an intersection
{
// Cut
List<Rectangle> rectangles = r1.Cut(intersection);
// ...
} |
Grâce à cette méthode, on peut également mettre en place un système itératif qui permet de décomposer plusieurs rectangles (c'est à dire que la surface de superposition peut appartenir à plusieurs rectangles).
Voilà, si un jour vous devez faire quelque chose de similaire et bien vous aurez une bonne partie de déjà fait 
Ce post vous a plu ? Ajoutez le dans vos favoris pour ne pas perdre de temps à le retrouver le jour où vous en aurez besoin :
