Version imprimable
Bonjour
J'ai un grand rectangle à afficher dans lequel je dois enlever 2 ou 3 rectangles (qui ne peuvent pas sortir du rectangle initial mais peuvent venir jusqu'au bord). J'aimerais donc afficher l'ensemble des rectangles qui constituent cette soustraction des 2 ou 3 rectangles du premier.
Existe-t-il un algorithme pour ça et, si possible une implémentation (idéalement en C, mais bon...)?
Merci
David
vous voulez dire que vous voulez le résultat de la soustraction sous forme d'un ensemble de rectangles ?Citation:
Envoyé par zedrummer
est ce que ces rectangles peuvent se superposer ?
Oui c'est ça, je veux un ensemble de rectangles.
Non il ne faut d'overlapping.
Bonjour zedrummer,
Voici ma proposition de solution. Il y a sûrement plus performant, mais elle me semble relativement simple.
- Diviser l'espace selon des abscisses et ordonnées correspondantes à toutes les côtés de rectangle respectivement verticaux et horizontaux
- Créer un tableau indiquant si oui ou non chaque cellule subdivisée est occupée par un rectangle à soustraire (en rouge).
- On crée les rectangles du résultat
- Si on ne cherche pas à avoir le minimum de rectangle en résultat, on peut considérer un rectangle pour chaque cellule non occupée (en bleu)
- Si on veut limiter le nombre de rectangle, il faut fusionner les cellules non occupées. Un algorithme "glouton" devrait faire l'affaire, ie on prend un rectangle non occupé, et on cherche à l'étendre au maximum dans les 4 directions successivement. A noter que cela ne donnera pas nécessairement le nombre minimal de rectangles, mais c'est à toi de voir selon ton besoin.
Pièce jointe 638186
@zedrummer
Commençons par le cas le plus simple : on a un rectangle (100,200) par exemple, et on enlève un carré (10,10) qui touche un des 4 coins.
On voit que la surface restante peut être écrite comme somme de 2 rectangles, de 2 façons différentes. Ou elle peut aussi être écrite comme somme de 3 rectangles, d'une façon assez logique.
Tu n'as pas du tout évoqué dans ton message qu'il y avait plusieurs solutions.
Si on prend le dessin proposé par AbsoluteLogic, on constate (sauf erreur de ma part) qu'on peut trouver 9 rectangles qui vont convenir et qu'il y a plusieurs solutions qui aboutissent à 9 rectangles, mais qu'il n'y a aucune solution avec 8 rectangles.
Est-ce que tu veux une solution optimale (9 rectangles), ou bien une solution avec 10 ou 12 rectangles te convient ?
Il y a une solution avec 12 rectangles qui est très facile à obtenir : on garde TOUTES les lignes pointillées horizontales du dessin, et on supprime les lignes pointillées verticales.
Pourquoi c'est à 'nous' de poser ces questions ? Pourquoi tu n'as pas précisé tout ça dans ton premier message ?
Déjà merci à vous de prendre sur votre temps.
Désolé s'il n'y avait pas toutes les réponses dans mes premiers messages, mais effectivement, la seule info qui manquait était qu'il ne faut pas d'overlapping.
Après qu'il y ait 9 ou 12 rectangles, ce n'est pas très grave, je dessine avec OpenGL, ça ne fera aucune différence. Je n'avais donc pas considéré ça comme une indication importante, désolé.
Je vais bien étudier votre réponse commune, merci bien.
David
Bonjour,
Bien que je pense que ce n'est pas très important ici, en général on utilise des rectangles semi ouverts du genre [xmin, xmax[, [ymin, ymax[ (i.e. les bords droits et bas n'appartiennent pas au rectangle). Ainsi les opérations restent cohérentes. Par exemple si on retire un rectangle à droite d'un autre, le semi ouvert à droite laisse bien le nouveau bord gauche dans le résultat.
D'autre semi-ouverts sont possibles mais celui-là est utilisé par les environnements graphiques.
Un autre avantage réside dans le fait mineur que la largeur en pixels devient simplement Xmax-Xmin (et réciproquement pour la hauteur).
Salutations
