Discussion :

[görgh]

Bonjour,

Ouf je viens de me farcir les 50 pages du forum pour trouver une réponse ou au moins une piste à ma question mais sans succès...

Voilà, plusieurs rectangles sont placés les uns sur les autres et ont chacun un indice de superposition. Je souhaiterais vérifier quel rectangles sont mal placés.
Le chiffre le plus petit correspond à un objet fragile et doit être placé au-dessus d'un rectangle possédant un chiffre plus élevé.

Je pensais définir un tableau à deux dimensions représentant mon conteneur dans lequel l'indice correspondrait à la position en pixel de mon rectangle.
Je cherche un algorithme performant pour m'indiquer les zones en erreur

Exemple :

002222
002222
111333
111333

signifie que j'ai en bas à droite un rectangle L3xH2 d'indice 1 qui est mal placé car le rectangle L4xH4 d'indice 2 est en chevauchement au-dessus mais celui-ci est bien placé par rapport au rectangle L3xH2 d'indice 3

Je ne sais pas si je suis bien clair

Je pensais vérifier colonne par colonne si le chiffre est croissant (ou décroissant selon l'ordre de recherche) mais j'ai peur que ce test soit plus long qu'un algo existant.

Merci d'avance pour votre aide

[PRomu@ld]

En fait, l'exemple que tu nous donnes ne me pose pas de problème en fait ...

002222
002222
111333
111333

On peut décomposer ça en trois rectangles comme ceci :

000000
000000
000333
000333

002222
002222
000000
000000

000000
000000
111000
111000

Il te faut absolument d'autres informations (comme la taille de tes boîtes), ensuite, est-ce qu'une boite supérieure est obligatoirement plus petite que celle qui est dessous ?

[alex_pi]

En fait, l'exemple que tu nous donnes ne me pose pas de problème en fait ...

Je pense que "au dessus" signifie bien "au dessus", au sens de la verticale de ton écran. Auquel cas, il y a bien problème

Voilà, plusieurs rectangles sont placés les uns sur les autres et ont chacun un indice de superposition. Je souhaiterais vérifier quel rectangles sont mal placés.

Si t'es rectangles sont stockés comme tu nous les affiches, je ne penses pas que tu feras vraiment mieux que parcourir colones par colones si c'est un problème de décision (problème / pas problème), en mémorisant pendant le parcours d'une colone la valeur minimale rencontrée.

en revanche, si tu dois exhiber tous les rectangle à problème, il y a sans doute mieux à faire !

[PRomu@ld]

Oups, désolé, j'avais pris le problème vu de dessus .

En fait, dans ce cas, la recherche va se faire colonne par colonne, donc pour n colonnes de hauteur h, l'algo est en theta(nm). Tu peux accélérer les calculs dans la pratique en connaissant deux choses : la valeur du vide (dès que tu as un vide tu passes à la colonne suivante), et la hauteur de tes boites (ça te permet de parcourir plus rapidement), l'algo est en O(nm) mais dans la pratique ça va plus vite que dans la recherche bête et méchante.

[Jedai]

Euh, si on connait les caractéristiques de chaque rectangle, n'y a-t-il pas nettement plus rapide que de faire un tableau et de vérifier chaque colonne ? Après tout si on les coordonnées de deux rectangles r1 et r2 pour savoir si l'un est au-dessus de l'autre, il suffit de voir si x1 < x2 + l2 et x1 + l1 > x2, n'est ce pas, ensuite on peut déterminer lequel est au-dessus simplement en comparant y1 et y2. Même si on fait ça bêtement (il y a sans doute moyen de mieux faire, rien qu'en triant par y, on peut descendre à O(n*log(n))), ça ne fait jamais que du O(n²) (où n est le nombre de rectangle, pas celui des colonnes), et sauf cas très particulier je doute que la complexité réelle soit supérieure à la méthode par colonne.

Ou y a-t-il quelque chose qui m'échappe ?

--
Jedaï

[pseudocode]

Je cherche un algorithme performant pour m'indiquer les zones en erreur
(...)
Je pensais vérifier colonne par colonne si le chiffre est croissant (ou décroissant selon l'ordre de recherche) mais j'ai peur que ce test soit plus long qu'un algo existant.

Sans autre informations que le tableau final avec le n° des rectangles, je ne crois pas qu'on puisse faire mieux que ta methode de verification colonne par colonne.

[görgh]

PRomu@ld > je pensait représenter la taille des boites de la façon suivante : valeur de l'indice = 1 unité (dont mon cas 1 unité = 1 pixel)

Donc quand dans mon exemple je dit 111 celà signifie une longueur de 3x1 unités (je vous l'avais dit que je n'était pas clair )

pseudocode > Peux-tu m'indiquer les informations manquantes que je pourrais vous communiquer ?
> La valeur du vide est égale à 0.

alex_pi > en effet je dois signaler tous les rectangles posants problèmes sachant que 3 rectangles d'indice 1 peuvent être les uns sur les autres (on additionne pas le poids c'est vraiment un indice) par exemple 3 rectangles L3xH2 d'indice 1 peuvent être sur un rectangle d'indice 2 mais pas l'inverse

111
111
111
111
111
111
222

Pour info j'était déjà une vraie quiche en math à l'époque du lycée et sans la pratique j'en ch.. un peu

[PRomu@ld]

Quel est la taille de ton container ?

100 * 100 , plus ?

[görgh]

Ca serait plutôt au moins du 600x800 voir plus...

Sachant également que l'utilisateur peut déplacer les rectangles environnants et que le contrôle doit être effectué à chaque déplacement une meilleure solution ne serait-elle pas de mémoriser le ou les rectangles en contact au dessus dans une liste et vérifier l'indice ? Sachant que j'ai déjà une méthode pour tester les collisions avec l'API IntersectRect qui boucle sur tous les rectangles de la zone. Je sais que ce n'est pas la meilleure méthode mais ça me semblait la meilleure quand j'ai commencer ce projet car j'utilise des objets de la VCL pour dessiner (pour divers raisons).

Il faut que je trouve un bon algo pour déterminer l'objet immédiatement supérieur et non tous ceux au dessus.

[PRomu@ld]

En fait, tu peux faire une recherche exhaustive lors d'une première passe de façon à déterminer les contacts. Ensuite, il suffit de tester l'ensemble des pixels de la boîte qui vient d'être déplacé. L'opération va se faire en O(p) où p est le périmètre de la boîte qui vient d'être déplacé.

Au pire, étant donné que ton conteneur n'est pas très grand, tu peux même utiliser la méthode brute ça ne coûte rien (au regard de la vitesse des processeurs actuels).