detection de lignes

Hello, je developpe une sorte d'editeur de "schéma" (on peut l'appeler comme sa) et je cherche la formule qui permet de vérifier si une coordonnée X et Y serais sur le tracé d'une ligne (qui est entre X1 Y1 et X2 Y2).
C'est pour pouvoir selectionner une ligne en cliquant dessus simplement à l'aide de la souris.
quelqu'un saurais comment faire, quel formule utiliser ou aurais des indices à me donner ?
Merci d'avance à toute personne pouvant me donner un coup de pouce :)

Comme c'est un problème indépendant du language, j'ai pensé qu'en postant ce message sur ce forum si plus de monde pourrais m'aider.

ps : au cas ou, je developpe en C sous linux et ma GUI est en GTK, mais je sais pas si c'est vraiement utile de le préciser

Je vais te repondre d'une maniere tres generaliste.
Si ca vas pas demande moi plus de precision par apres.

Ta ligne peut etre representer par une equation de type y=ax+b.
Il suffit de verifier si les coordonnees, de type (x,y) , du point de ta souris repond a cette equation.


exemple: si l'equation de la droite est y=2x+5
et la souris se trouve a (6,5).


tu peux par exemple remplacer le x par 6 et verifier si y est egale a 5.
Si oui alors la souris se trouve sur la ligne autrement non.

(2*6)+5=17
17 n'est pas egale a 6 donc pas sur la ligne.

Conseil ta souris sera trop sensible si tu prens commme resolution 1 pixel.

J'espere que j'ai ete clair.

Citation:

---

Envoyé par blue

Ta ligne peut etre representer par une equation de type y=ax+b.
Il suffit de verifier si les coordonnees, de type (x,y) , du point de ta souris repond a cette equation.

---

Il existe un cas particulier, la verticale qui est de la forme x=c, mais ca ne pose pas de pb particulier a verifier et ne remet pas en cause la methode de blue.

Merci gl a cause de moi il aurais pu provoquer un plantage de la machine( ca m'est deja arrive).
T.C.G >>Toujours tester la division par zero et prevoir cette situation!!!!!!!!!!!

heu ... je comprend pas trop le y=ax+b
A quoi correspond a et b ? à X1 et X2 ?
je suis pas très doué en algo désolé

en passant, il paraitrais que je me suis trompé de forum en le postant sur le forum "Developpement général" et qu'il aurais fallu le poster dans le forum "algo" alors si j'ai dérangé quelqu'un je tiens a m'excuser. ( ... tiens il l'a déplassé dans ce forum :)
par ce que de la fasson dont j'ai été avertis il avais l'aire très faché !
désolé.

Ce n'est pas grave, ca arrive a tout le monde.

y=ax+b

Le y represente tout les points en ordonnees
le x represente tous les point en abscisses
le a represente la pente
et le b la constante.
On voit ca dans tous les cours de math. en secondaire.( oups!! je suis belge je ne sais pas si on as le meme systeme).

Voici comment tu peut calculer cette equation :


a= (X2-X1) / (Y2-Y1)
b=Y1-(a*X1)

A ce moment la tu as une equation,
par exemple y=5x+9.
Si tu regarde bien tu t'apercevra que pour une valeur de x tu ne peux a voir qu'une seule valeur de y.

Donnes moi un exemple de droite et de la souris avec la valeur des coordonnees, je vais le refaire.

je commance a comprendre gantillement.
tiens, voila un example :
une ligne : X1=21, Y1=4 - X2=60, Y2=55
et le curseur se trouve ... admeton à X=35, Y=31
je vais déjà commancer à coder les truques que tu m'a dis.
merci.

ps : en suisse y'a 4 niveau différant pour les classes secondaires et moi ben j'étais en préproffessionel, le niveau 2, disons pas les nul mais prèsque :)

Votre systeme a l'aire de ressembler au notre.

Dans ce cas tu fais :

a=(60-21)/(55-4) donc a=0.9512195121...
b=4-(0.9512195121*21) donc b=19.9512195121... .

donc equation :
y=0.95121X+19.95121

Maintenant verifions si ta souris passe bien par cette droite.


Remplacons X par 35 on a alors y=( 0.95121*35 )+19.95121


y=53.24356.

Comme tu le vois cette valeur ne correspond pas avec celle que tu m'as donne pour la souris ( y=31) donc je sais que la souri ne se trouve pas sur cette droite.

Si tu as besoin plus d'eclaircissement .....

Bon travail

t'étais en option 2?

parce que l'option 2 c'est l'option scientifique, pas pour les nuls, faut quand même avoir au minimum 2 A un B...

j'ai plutôt l'impression que t'es en option 3.

heum ..
en refaisant le calcule, pour a je trouve 0.764705882
y'a pas comme un bug ?


en suisse les niveau sont classé par difficulté, y'a :
terminal, niveau 1, gros nul
preproffessionel, niveau 2, un peut moi (la ou j'étais)
modern, niveau 3, niveau normal
scientifique/classique, niveau 4, les gros balèzes

tu as raison c'est bien ca.
Le raisonement reste de toute facon le meme.

2 choses encore :

1)n'oublie pas de tester si X1 est egale a X2, car alors la la procedure n'est plus la meme et faudra en prevoir une autre.

2)je t'ai parler de la definition du curseur et un pixel c'est trop precis peut etre.
il est possible que tu n'arrives jamais juste la ou il faut pour etre sur ta ligne.

A+

Pour verifier que trois points A,B et C sont alignés, il ne serait pas plus facile de vérifier que les vecteur AB et BC verifient le fait que le produit scalaire est égal au produit des normes.

(Il faudrait aussi vérifier que l'abcisse de B est bien comprise entre celle de A et celle de C).

Cordialement,
Ol'

Je ne sais pas ce que tu entends par plus facile, mais le plus simple reste d'utiliser l'equation d'une droite.

Il faut evidemment verifer que le point est bien compris a l'interieur des coordonnees de la droite.

heum ... je suis pas très doué en math alors j'ai pas compris grand chose.
tu peut l'expliquer plus simplement ?
avec un example pleut être.

Blue, j'ai l'impression que sa marche pas comme il faut ton calcule

Montre moi le source que tu as ecris.
Relis aussi ce que j'ai ecris plus haut a propos de la resolution (cfr points 2).

blue, avec un example simple qu'on pourrais raisoudre avec un shéma vite fais main levé sa marche pas.
par example, une ligne de X1=10 et Y =10 à X2=40 et Y2=30.
normallement, si le curseur est à X=20 et Y=15 sa devrais jouer, mais la sa fonctionne pas, le curseur devrais être à X=20 et Y=35 d'après le résultat de y dans ta formule
ou alors j'ai loupé quelque chose

voila mon code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

int SurLigne(float vX, float vY, float vX1, float vY1, float vX2, float vY2) { float a; // pente float b; // constante float x; float y; // calcule de a et b a=(vX2-vX1)/(vY2-vY1); b=vY1-(a*vX1); x=vX; y=(a*x)+b;   printf ("Variables :\n"); printf (" ligne de %f|%f à %f|%f\n", vX1, vY1, vX2, vY2); printf (" curseur %f|%f\n", vX, vY); printf (" a=%f\n" " b=%f\n", a, b); printf (" x=%f\n" " y=%f\n", x, y); }

---

ou j'ai essayé la version sans l'absolue de b:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int SurLigne(float vX, float vY, float vX1, float vY1, float vX2, float vY2) { float a; // pente float b; // constante float x; float y; // calcule de a et b a=(vX2-vX1)/(vY2-vY1); b=fabsf(vY1-(a*vX1)); x=vX; y=(a*x)+b;   printf ("Variables :\n"); printf (" ligne de %f|%f à %f|%f\n", vX1, vY1, vX2, vY2); printf (" curseur %f|%f\n", vX, vY); printf (" a=%f\n" " b=%f\n", a, b); printf (" x=%f\n" " y=%f\n", x, y); }

---

en faite je savais pas trop si je devais mêtre l'absolue de b ou pas par ce que d'après l'example que tu m'a fais, ton 19.9512195121, donnais en faire -12 quelque chose chez moi

J'ai essayer et ca marche mais je suis en train de chercher ou est ce que j'ai pu me tromper dans mon explication.
Mais avant de continuer plus loin pense a transformer tes valeur en int.
Car tes coordonnees sont des valeurs entieres.

je sais, mais je me suis dis que pour le début sa serais un peut moin claire de faire des (float) partout pour caster toute les valeur, alors j'ai déssidé, en attendant d'etre sur que sa marche, de les passer directement en float.
histoir de pas me planter dans le code et d'oublier des () importantes

Bon Je crois que la j'ai fais une grosse boulette.
J'ai confondu les x et les y.
Concretement tu dois dois faire ceci (Y1-Y2) / (X2 -X1).

a=(vX2-vX1)/(vY2-vY1); => a=(vY2-vY1)/(vX2-vX1);


Desole

sa à l'aire d'aller un peut mieux apparement.
dis moi, alros b c'est l'absolu ou pas ?

surtout en mathematique ne joue jamais avec les signes.
Garde les comme ils ont, donc pas d'absolu.

N'oublie pas de verifier que le point X (coord.) de la souris est compris entre X1 et X2 et que le y de la souris est compris entre Y1 et Y2.



AUSSI.



nt SurLigne(float vX, float vY, float vX1, float vY1, float vX2, float vY2)
{
float a; // pente
float b; // constante
float x;
float y;
// calcule de a et b

!!!!!!!!!!!!! if (y1!=y2)
a=(vX2-vX1)/(vY2-vY1); ////IL FAUT UN IF AVANT CETTE LIGNE
b=vY1-(a*vX1);
x=vX;
y=(a*x)+b;

printf ("Variables :\n");
printf (" ligne de %f|%f à %f|%f\n", vX1, vY1, vX2, vY2);
printf (" curseur %f|%f\n", vX, vY);
printf (" a=%f\n"
" b=%f\n",
a, b);
printf (" x=%f\n"
" y=%f\n",

..........

Si tu as encore des questions je te repondrais demain.Salut

ok ok.
Merci beaucoup, sa faisais longtemps que je sèchais la dessus avant de poster ce message dans se forum.
sans toi j'y serais jamais arrivé.
Vraiement merci.

Non, vraiment je crois qu'il n'est pas nécessaire de calculer l'équation de la droite.

Prenons A(10,11), B(20,21), C(30,31)
Prenons le produit scalaire de deux des vecteurs
AB.AC = ((20-10)*(30-10))+((21-11)*(31-11)) = 400
(J'ai pris le produit scalaire canonique de R²)

norme(AB).norme(AC) = racine((20-10)² + (21-11)²).racine((30-10)² + (31-11)²) = racine(200).racine(800) = 400

Les trois points sont donc bien alignés.

Cela repose sur le fait que le projection du point intermediaire sur la droite engendrée par les deux autres est le point intermedaire lui même.

Cordialement,
Ol'

sa m'interesse, car l'autre n'est pas très précise pour les lignes prèsques plattes.
je suis pas très doué en math et je connais pas vraiement ce sujet la,
a quoi correspond la "norme" ?
et, les différants calcules séparré par des "." comment dois-je les interpréter ?
c'est quoi un produit scalaire ?

hooo, jusque la j'arrive, j'ai AB.AC, AB et AC qui valent respectivement 400, 200 et 800.
et la, on fais racine carré de AB fois la racine carré de AC et sa donne 400, donc correcte, c'est bien juste ?

c'est bon j'y suis arrivé tout seul.
Cette formule est beaucoup mieux que l'autre, elle permet d'etre beaucoup plus précis que l'autre surtout pour les lignes prèsque verticales ou horizontales.
Merci beaucoup Ol' pour ta formule.

Citation:

---

Envoyé par the.cable.guy

hooo, jusque la j'arrive, j'ai AB.AC, AB et AC qui valent respectivement 400, 200 et 800.
et la, on fais racine carré de AB fois la racine carré de AC et sa donne 400, donc correcte, c'est bien juste ?

---

Il vaudrait mieux faire (si tu veux etre pile pour le pixel) :
carre(AB.AC)==norm(AB)*norm(AC) => 400*400=200*800 !
Dans ce cas toujours pas de flottants

ok.
se qui est domage c'est qu'après la différance entre les 2 valeurs est très grande, tandis qu'avec l'autre methode, ou on faisais la racine, la différance étais quasiment de 0 quand on étais sur la ligne, pour le programme c'est plus simple gèrer une valeur près de zéro plutot qu'une grande valeur, je trouve.
L'autre methode me va, merci quand même.