detection de lignes

**the.cable.guy** · 09/10/2002, 11h45

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

**blue** · 09/10/2002, 13h09

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.

gl · 09/10/2002, 13h14

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.

**blue** · 09/10/2002, 13h17

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!!!!!!!!!!!

**the.cable.guy** · 09/10/2002, 13h53

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é.

**blue** · 09/10/2002, 15h17

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.

**the.cable.guy** · 09/10/2002, 15h33

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 :)

**blue** · 09/10/2002, 15h52

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

**senke** · 09/10/2002, 15h58

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.

**the.cable.guy** · 09/10/2002, 16h08

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

**blue** · 09/10/2002, 16h12

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+

**Ol'** · 09/10/2002, 16h39

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'

**blue** · 09/10/2002, 16h49

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.

**the.cable.guy** · 09/10/2002, 16h50

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

**blue** · 09/10/2002, 16h52

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).

**the.cable.guy** · 09/10/2002, 16h56

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

**the.cable.guy** · 09/10/2002, 17h01

voila mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**blue** · 09/10/2002, 17h19

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.

**the.cable.guy** · 09/10/2002, 17h22

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

**blue** · 09/10/2002, 17h29

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

detection de lignes

Algorithmes et structures de données

Discussions similaires

Partager

Partager