Discussion :

[jeroman]

Bonsoir,

Dans le cadre d'un projet personnel, je recherche des idées d'algorithme (assez optimisé de préférence) permettant de calculer l'aire d'une union de rectangles qui se chevauchent. Une idée m'est venue à l'esprit mais je suppose qu'elle est catastrophique en matière d'optimisation.
Il s'agirait d'ajouter les rectangles au fur et à mesure et, à chacune de ces étapes, de les découper en sous-rectangles au niveau des chevauchements de telle manière à pouvoir supprimer les éventuels doublons par la suite.
A la fin, l'aire totale serait tout simplement égale à la somme des aires de tous les sous-rectangles.

Illustration avec l'image jointe. Au départ, il y a un rectangle rouge, auquel j'ajoute un autre, de couleur verte, qui le chevauche partiellement. Je les divise en sous-rectangles, numérotés ici de 1 à 4 rouges et de 1 à 4 verts. Au niveau du chevauchement, deux sous-rectangles (le 4 rouge et le 1 vert) font doublon. L'un des deux est donc supprimé.
Par la suite, éventuellement, je réunis les sous-rectangles restants en groupes de rectangles (accolés les uns aux autres mais qui ne se chevauchent pas) afin d'alléger la liste de sous-rectangles.

Pour chaque nouveau rectangle ajouté, l'opération est renouvelée.

Que pensez-vous de l'idée ? Est-ce qu'il existe mieux, plus optimisé et pas trop compliqué à mettre en oeuvre ? Merci !