Bonjour les amis
je crée des polygones et je voudrais mettre en place un algo qui permettrait de savoir si ce dernier est convexe.
Comment pourrai-je m'y prendre ?
merci
Version imprimable
Bonjour les amis
je crée des polygones et je voudrais mettre en place un algo qui permettrait de savoir si ce dernier est convexe.
Comment pourrai-je m'y prendre ?
merci
un peu bourrinement, tu peux calculer l'enveloppe convexe des points en question (algorithme de Graham en n.logn par exemple), et ensuite qu'il s'agit bien du polygone considéré. Sinon, c'est que celui-ci ne peut être convexe.
:!: attention aux angles plats dans ton polygone, fais en sorte que ton algorithme d'enveloppe convexe ne 'saute' pas le point du milieu si 3 pts sont alignés, sinon tu pourras pas le comparer directement avec ton polygone.
perso, je testerais les angles pour chaque sommet, dès qu'un est rentrant il n'y a plus de convexité.
avec les produits scalaires et vectoriels cela devrait aller.
sauf s'ils sont tous rentrants :) sinon en effet, en tournant le long du polygone, n produits vectoriels de segments consécutifs et les composantes z doivent toutes avoir le même signe.Citation:
Envoyé par PINGOUIN_GEANT
Donne-moi un angle rentrant sur un polygone et je te trace un segment avec des points à l'extérieur du polygone.Citation:
Envoyé par Steki-kun
Rq: on peut espérer que le domaine à l'intérieur polygone vérifie la propriété mathématique suivante :
il se situe localement d'un seul côté de sa frontière.
c juste pour faire remarquer que fondamentalement, tu ne sais pas à priori dans quel sens va tourner ton polygone, donc angle rentrant (= angle entre 180 et 360 degrés par définition mathématique, qu'on sache de quoi on parle au moins) n'implique pas que le polygone n'est pas convexe. Le problème est de trouver, dans un même parcours, au moins un angle <= Pi et un angle plus grand. Ca c'est une CNS de convexité.
justement si, pour moi cela n'a pas de sens de définir un polygone et de ne pas savoir où est l'intérieur du polygone, comme ton contour sépare l'espace en 2 parties distinctes.Citation:
Envoyé par Steki-kun
Après il faut voir l'implémentation de nkd.
manque de pot, il se bien que le polygone, ce soit un tableau (voire une liste) de deux coordonnées à chaque fois, le plan se retrouvant alors orienté par l'ordre de tracé (supposons que c'est un tracé de polygone à la souris dans un paint sommaire par exemple), ce qui peut donner le polygone concave au lieu du convexe :) dans le doute j'ai préféré préciser, ça ne coûte rien
merci les amis pour vos contributions
en effet c'est un polygone tracé depuis la souris dont les sommets sont connus en xy et stockés dans un tableau. il y a bien un sens que je me donne pour le créer.
vu vos post je crois que j'ai une idée, celle de tester si tous les angles intérieurs ne sont pas rentrant et qu'ils sont tous <=180 °
je fait le test et je vous fait signe tout de suite
merci et A+
Même sans connaitre le sens de rotation de ton polygone il suffit de vérifier que tous les produits vectoriels Pi-1Pi^PiPi+1 ont même signe (c'est un produit vectoriel de 2 vecteurs, je ne sais pas comment écrire la formule autrement). Ce qui reviens à tester que dans un sens de parcours tous les angles sont soit obtus, soit concaves.Citation:
Envoyé par nkd
Bein non.... prend un losange aplati... il n'y a que 2 angles obtus...
Arg, grosse bétise de vocabulaire de ma part, je voulais parler de >=180°, ou <= à 180°. Mais le principe énoncé reste valable.Citation:
Envoyé par Nemerle
pourquoi "aplati" :!: :?:Citation:
Envoyé par Nemerle
c'est quand même exactement ce que j'ai écrit au-dessus (en remplacant obtus par rentrant), donc on chippote, on chippote, mais on en revient au même point =)Citation:
Envoyé par sovitec
J'avais lu ta contribution un peu trop en diagonale, tu as parfaitement raison. En fait je répondais surtout au dernier post de nkd.Citation:
Envoyé par Steki-kun
ha bah je te reproche rien, mais c'est marrant quand même comme on tourne en rond (c'est à ça que ca sert le résolu finalement :))Citation:
Envoyé par sovitec
Pour "forcer" l'image :wink:Citation:
Envoyé par Trap D