Discussion :

[touftouf57]

Bonjour à tous,

Je recherche un algorithme me permettant d'obtenir l'enveloppe convexe d'un polygone. Je précise que je ne recherche pas l'algo d'une enveloppe convexe d'un nuage de points.
Je m'étais tourné vers l'idée de regarder si le point i est rentrant dans le polygone dans ce cas il ne doit pas être pris en compte dans l'enveloppe convexe.
Après quelques cassages de tête, je n'arrive pas à mes fins. Quelqu'un aurait-il un algo à me proposer?

Merci

[ToTo13]

A l'extrémité de chaque arête de ton polygone il y a des points, donc tu peux justement te ramener à un nuage de points.
Donc pourquoi ne pas le faire ?

[touftouf57]

Tout simplement parce que cela m'est demandé ainsi.

Je suppose que c'est pour avoir un algo avec une meilleure complexité que O(n^2).

Maintenant si tu me proposes un algo optimal pour exécuter cette tache, je suis preneur.

Merci

[ToTo13]

Les algorithmes de calcules d'enveloppe convexe sont en O(N log N). Le plus simple à implémenter est (à mon avis) la Marche de Graham.