Discussion :

[Rastacouéne]

bonjour!
je voudrai savoir si, pour calculer une boite englobante, il y a d'autre solutions relative ou non au c pour calculer la boite englobante d'un triangle par exemple que de parcourir tous les points et de tester si il sont sup ou inf à un point de ref remis permpétuellement a jour?

( quel belle phrase... )

[pseudocode]

Vu que les coordonnées/dimensions de la boite englobantes dépendent des "n" points considérés, ca me parrait dur de faire un algo plus simple que o(n).

Enfin bon, ce n'est que mon avis.

[Rastacouéne]

je pense aussi
merci quand même

[souviron34]

si c'est pour ton problème exposé sur le forum C, c'est pour de la triangulation, c'est ça ?

il y aurait alors une solution : déterminer l'enveloppe, et passer uniquement à travers les points de l'enveloppe...

[Rastacouéne]

je ne peux pas, c'est pour un algorithme d'optimisation de lancer de rayon ( rendu réaliste) à l'aide d'une grille réguliére. pour ça il faut que j'ajoute toutes les boites englobantes des triangles dans ma grille à chauque rendu...d'où le besoin d'optimisation au maximum , don't sur ce calcul^^

[FrancisSourd]

Tu veux connaître le plus petit rectangle "parallèle aux axes" qui englobe "n" points?

Si c'est un polygone convexe, tu peux imaginer une dichotomie (en supposant que tes sommets sont donnés dans l'ordre (sinon il faut le faire en O(n log n) ce qui n'est pas terrible). Tu peux aussi avoir des structures spéciales pour des polygones (par exemple quad-tree), mais s'il faut contruire ces structures pour chaque polygone, cela ne vaut pas le coût. (C'est surtout utile, si tu peux remettre vite à jour ces structures).

Un dernier truc:
Calculer le min (ou le max) d'un tableau requiert n comparaisons. Mais, si on calcul simultanément le min et le max, on peut ne fait que 3n/2 comparaisons (au lieu de 2n). Algo: On compare v[i] et v[i+1]. Si v[i]<v[i+1], V[i] est candidat pour être min, on teste s'il améliore le min. On teste si v[i+1] améliore le max. Si v[i+1]>=v[i], on fait l'inverse. On augmente i de 2.

[ToTo13]

Bonjour,

avoir la boite englobante parallèle aux axes est un problème facile en O(n).

Si tu la veux orientée, tu peux démarrer avec la boite formée par les axes principaux.
Sinon, il te faudra calculer tous les diamètres de férêts pour avoir la boite orientée minimale.

Le problème n'est vraiment pas trivial en 3D...

[Rastacouéne]

merci pour vos solutions!