une ligne et un polygone convexe

Bonjour à tous !

Je me trouve devant un problème assez compliqué à résoudre. J'ai un polygone convexe, de la forme d'un T, affiché à l'écran (il représente le contour extérieur d'un circuit).

J'aimerais ensuite tracer au clic-par-clic le contour intérieur.

Tout fonctionne à merveille, à chaque fois qu'on clique, le prog trace une ligne entre l'avant-dernier et le dernier clic, et on peut pas cliquer à l'exterieur du T.

Le problème, c'est que j'arrive pas à tester si la ligne sort quand même du T (ben oui, même si les 2 points sont à l'intérieur, suivant comment, une partie de la ligne peut passer par dehors).

J'ai tenté en vain de trouver une methode de Polygon qui pourrais m'aider, mais certainement que vous avez de meilleures idées que moi, et je les attends avec impatiente ;) merci !

Je soupçonne quand ce moment il doit avoir un devoir sur le sujet, où que tu sois la même personne à qui j'ai déjà répondu sur un autre forum. Quoiqu'il en soit, voici ce que j'ai déjà répondu :

Tout d'abord un polygone en forme de T n'est pas convexe, car justement tu as un problème de segment, sinon tu n'en aurais pas.
Ensuite, il te suffit de couper ton T en 2 zones :

Code:


---------------------------------
| | * | |
---------------------------------
| + |
| + |
| + |
| + |
-------




Je ne sais pas si c'est clair, , mais j'ai essayer de dessiner la barre horizontal et la bare vertical avec une partie commune (lrur intersection. Il te suffit alors de savoir si tes deux points appartient à la même zone.



Et un autre message :

Bon j'imagine que tu travaille en discret, c'est à dire des coordonées entiéres, tu peux essayer par récurence. Je m'explique :

Je te l'écrit en Java

1) Soit public boolean aLInterieur(int x,int y) qui renvoie vrai si le point est à l'intérieur de ton polygone.

2)
public boolean contientSegment(int x1,int y1,int x2,int y2)
{
// Si le point 1 n'est pas à l'extérieur du polygone, le segment n'est pas contenu
if(!aLInterieur(x1,y1))
return false;
// Si le point 2 n'est pas à l'extérieur du polygone, le segment n'est pas contenu
if(!aLInterieur(x2,y2))
return false;
On prend le point milieu
int mx=(x1+x2)/2;
int my=(y1+y2)/2;
//Si le point au milieu n'est pas dans le polygone, alors, le segment sort
if(!aLInterieur(mx,my))
return false;
//Si le point du milieu est le point1 ou le point 2, alors c'est bon
if(((mx==x1)&&(my==y1))||((mx==x2)&&(my==y2)))
return true;
// Si le segement (x1,y1)->(xm,ym) sort du polygone, alors on sort
if(!contientSegment(x1,y1,xm,ym))
return false;
//Sinon le problème revient à savoir si le segment (xm,ym)->(x2,y2) est à l'intérieur
return contientSegment(xm,ym,x2,y2);
}


Et encore :

Désolé, je vois que tu ne connais pas trés bien Java.
En fait, dés que le prog rencontre un return, il calcul éventuellement la valeur (pour true et false, il n'a rien à faire), il la renvoie et arréte l'execution de la méthode.
Donc c'est bien le return false ou true, qui dit c'est fini de boucler, je connais la réponse.
Pour ton utilisation, oui c'est quelque chose comme çà qu'il faut faire.
La méthode ne va boucler à l'infini, puisque l'on traivaille dans un espace discret. Donc le milieu n'est pas vraiment le milieu au sens mathématique pur.
En fait le traitement peux etre résumer ainsi :

les extrémité sont à l'intérieur ? ---NON--> le segement est dehors
|
oui
|
\ /
le milieu est a l'intérieur ? ---NON--> le segment est dehors
|
oui
|
\ /
L'écart entre les extrémités est plus d'un pixel (Ce qui revient à voir si le milieu est l'une des extrémité (n'oublies pas qu'ici 3/2 = 1 et pas 1.5)) ? ---NON---> le segment est à l'intérieur
|
oui
|
\/
Au moins un des demi dégments est dehors ? ----NON---> le segement est à l'intérieur
|
oui
|
\/
le segment est dehors

C'est plus clair ainsi ?

Ps : J'y pense, il faut peut être que je t'explique une ou deux choses sur la récurence ? Par exemple, toujours s'assurer qu'elle ne boucle pas à l'inifini.

Ps : Cet algo n'est pas le must, il fonctionne très bien pour des lignes pas trop grande, son inconvienent majeur, est que dans le pire des cas, c'est à dire que le ségment est effectivement contenu, il va parcourir tout le ségment. Quelle est la taille maximale en pixel dans lequel tu travailles ?
Si c'est trop grand, tu vas remplir ta pile d'excution, et la ....
Je te conseilles de le transformer en non récursif, je n'ai pas le temps pour le moment.


J'ai mis toutes mes réponses au cas où tu serais une personne différentes, ou que quelqu'un d'autre serait intéréssé par le sujet.

JHelp