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 :wink: , merci !

[modéré par Clément Cunin]
Problème d'algorithmique, réalisation en Java

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:

---

1 2 3 4 5 6 7 8 9 10

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

---

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.

JHelp

Hum, entre convexe et concave, j'avais une chance sur deux, et évidemment je m'suis trompé :? Enfin bref.....

Ta solution est ma foi fort intéressante, mais voilà, je n'ai pas seulement un T. :oops: En fait, j'ai dit ça pour simplifié, pensant naïvement qu'on ne pouvait pas traiter le cas du T de façon particulière. Désolé....

Pour l'histoire, le contour extérieur est également tracé au clic-par-clic. Donc forcément, tu peux avoir des formes pas possible, avec des pointes dans tous les sens, bref, tout ce que tu veux.

Le problème reste le même, néanmoins. Mais si t'as d'autres idée n'hésite pas :D , de mon coté c toujours du surplace...

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);
}

Dis moi si ça te conviens

JHelp

Superbe, la récurtion :) . Je connaissais de nom mais je l'avais jamais utilisée.

Du coup, j'ai juste une question : Comment dire au programme de cesser l'appel à la fonction contientSegment() ? Tu mets return true; si le point 1 ou 2 = le point du milieu, ou return false; sinon. Mais concrétement, je vois pas....

Cette méthode se boucle d'elle-même, ça veut dire que pendant tout le test, le prog reste à l'intérieur de cette méthode. Est-ce que le simple fait de mettre return true; revient à dire "Fini de tourner en boucle" ?

Dans le corps du programme principal, j'aurais quelque chose du genre :

boolean segmentOk = contientSegment(x1...);
if (!segmentOk) {
System.out.println("pas bon");
}else {
System.out.println("bon");
}

est-ce que c bien le return qui stoppe la boucle ?

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 ?

JHelp

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.

ok merci ! J'ai saisi le principe, maintenant.

Pour ce qui est de la longueur du segment, j'estime qu'environ 1% des cas dépasseront 600 pixels, sinon, ce sera entre 1 pixel de long minimum à quelque chose comme 100, voir 200. En fait, la zone fait 600 * 400.

Voilà en gros, mais je pense pas qu'il y aura de problème, enfin j'espère ;)

Dans ce cas, je pense, que tu n'auras pas de souci, pour une taille de 600, tu aursas environ log2(600) < 10 appel sur la pile en attente, donc pas de soucis majeur
JHelp

Une solution très simple et efficace :

puisque ton circuit est tracé au clic par clic, tu as une méthode qui trace des lignes.

Réécris la, par exemple en utilisant l'algo de Bresenham ou tou autre algo de tracé de ligne point par point.

Et modifie là pour que avant d'écrire dans un pixel, il regarde s'il n'y a pas déjà quelque chose dedans. Si oui, alors on efface le début de la ligne qu'on a commencé à tracer, et on attend un clic valide.

Au final ça implique de stocker : l'image dans un tableau (pour que la ligne ne commence pas à s'afficher puis s'efface si elle est pas bonne), la liste des point allumés pour cette ligne (afin de pouvoir les éteindre si elle est pas bonne), et c tout.

L'algo est plus que simpliste à coder quel que soit le langage, et super efficace. J'espère que mes explications sont compréhensibles, il se fait tard ;)

C plus efficace que l'algo de JHelp, par contre le sien est bien plus général, et est applicable quasiment sans modif si on ne connait que les points des extrêmités des arètes du contour, alors que dans ce cas le mien devient totalement inefficace.

Citation:

---

Envoyé par Pazz

Et modifie là pour que avant d'écrire dans un pixel, il regarde s'il n'y a pas déjà quelque chose dedans. Si oui, alors on efface le début de la ligne qu'on a commencé à tracer, et on attend un clic

---

hhhhmmm...me rappelle le clipping ça

Citation:

---

alors que dans ce cas le mien devient totalement inefficace.

---

pas tant que ça en fait... il sufit de retracer le polygone à partir des points c très rapide aussi. Donc c bon même si on n'a que les extrêmités des arêtes il est ok.

Citation:

---

hhhhmmm...me rappelle le clipping ça

---

oui c ça. Mais bon l'algo marche aussi bien sans ça, c pas l'essentiel.