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 !

[dev_ggy]

Bonjour,

Il n'y a pas de mauvaise méthode et chaque méthode est optimale pour un type de contrainte. Il m'est difficile de juger de la qualité de ta méthode ne connaissant pas mieux tes contraintes. D'autres idées que la tienne me viennent en tête. Pourquoi ne pas modéliser ton espace par une matrice comme on le ferait pour une image et compter les points ou deux, trois carrés se recoupent à l'aide d'un compteur*? Mais, peut-être que ton espace est trop grand et que tu ne peux pas le discrétiser. Autre solution, les méthodes de Monté Carlos avec des points au "hasard" ou selon des marches aléatoires. Mais peut-être que cette méthode est trop générale. À toi de définir tes contraintes et tes données en entrée pour tes carrés et leurs recoupements pour déterminer s’il est mieux que tu ressoudes directement le problème par le calcul. Soit par une méthode proche des éléments finis ou bien proches du calcul stochastique. À toi de voir.

Cordialement.

[bretus]

Bonjour,

Je prendrais à peu près le même que toi, mais avec une approche globale pour pouvoir optimiser le découpage :
- Découper les rectangles en fonction des verticales (on doit pouvoir optimiser ça avec une sweep line en triant les rectangles en fonction de leur xMin).
- Découper le résultat ensuite suivant les horizontales
- Supprimer les doublons. Une fois les rectangles découpés suivant les horizontales et les verticales, il suffit d'assurer l'unicité sur le couple (xMin,xMax),, il faut supprimer les rectangles inclus dans d'autres (rectangle dans un rectangle, sans intersection).

Sans chercher des optimisations particulières, je calculerais brutalement l'union des polygones, puis l'aire du polygone. Ça peut d'ailleurs servir de référence pour ta méthode dédiées aux rectangles (Voir CGAL).

[jeroman]

Merci pour vos réponses. Je pense que je vais me diriger vers la méthode sweep line. C'est plutôt simple à mettre en oeuvre.