Discussion :

[karistouf]

bonjour à tous !
bon là je commence à coincer alors je poste , en espérant un coup de paluche.

j ai 3 points qui forment un triangle
je desire savoir si ma souris passe dans ce triangle ( dont l orientation varie)

xA yA
xB yB
xC yC
xMouse YMouse

au travers de ce tuto je pensais avoir trouvé la soluce mais j ai un peu de mal à comprendre comment transformer mes points en vecteurs et faire les opérations de manière simples..

http://www.blackpawn.com/texts/pointinpoly/default.html

voilà, un petit coup de paluche pour convertir celà en simple code C sans bibliothèques tierces serait génial !

[3DArchi]

Rappel sur les vecteurs:
AB = AO + OB = OB -OA
Donc AB.x = B.x - A.x et AB.y = B.y - A.Y.
Voilà pour la transformation de tes points en vecteurs!
Ensuite, quelles sont les opérations qui te bloquent? As-tu un bout de code C?

[karistouf]

bonjour 3Darchi. hum.... j ai pas fait bp de maths à l ecole ;-)

il faut que je regarde comment me depatouiller juste avec des coordonnées simples ( x y ) de cette problematique de vecteurs....

bref, comment calculer que ma souris est bien située dans le triangle de ces 3 points....
du coup je nage un peu car je n utilise pas de vecteurs d habitude...

[karistouf]

ok... je vasouille completement...
quelqu un peut me filer un petit coup de main ? merci !

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
 
	V3D_f v1 =
	{
		xchroma+vxd, ychroma+vyd, 0,
		0., 0.,
		makecol(0, 0, 0) // black vertex
	};
	V3D_f v2 =
	{
		xchroma+vxw, ychroma+vyw, 0,
		0., 0.,
		makecol(255, 255, 255) // white vertex
	};
	V3D_f v3 =
	{
		xchroma+vxh, ychroma+vyh, 0,
		0., 0.,
		makecol(r_pick, v_pick, b_pick) // color vertex
	};
 
 
	triangle3d_f(screen, POLYTYPE_GCOL, NULL, &v1, &v2, &v3);
 
 
float vec0,vec1,vec2,dot00,dot01,dot02,dot11,dot12, invdenom, u , v;
 
vec0 = (mouse_x - xchroma+vxh)*(mouse_y - ychroma+vyw)-(mouse_x - ychroma+vyw)*(mouse_y-ychroma+vyh);
vec1 = (mouse_x - xchroma+vxw)*(mouse_y - ychroma+vyd)-(mouse_x - xchroma+vxd)*(mouse_y - ychroma+vyh);
vec2 = (mouse_x - xchroma+vxd)*(mouse_y - ychroma+vyd)-(mouse_x - xchroma+vxh)*(mouse_y -  ychroma+vyd);
 
dot00=dot_product_f(vec0,vec0);
dot01=dot_product_f(vec0,vec1);
dot02=dot_product_f(vec0,vec2);
dot11=dot_product_f(vec1,vec1);
dot12=dot_product_f(vec1,vec2);
 
invdenom= 1/(dot00*dot11 -dot01 *dot01);
u = (dot11 * dot02 - dot01 * dot12) * invdenom;
v = (dot00 * dot12 - dot01 * dot02) * invdenom;
//Donc AB.x = B.x - A.x et AB.y = B.y - A.Y.
if(mouse_b&1)
{
if (u>0 && v>0 && (u+v)<1)
{
    sprintf(string_Last_Order,"Mouse IN triangle");     
}
 
else {
 sprintf(string_Last_Order,"Mouse NOT in triangle");              
}
}

[souviron34]

ce post aurait plutot sa place sur le forum Algo....

En gros :

3 points (x1,y1) (x2,y2) (x3,y3)
1 point (souris) (x,y)

• Calculer xmin, xmax ymin, ymax, des 3 points
• Première élimination : si x < xmin ou x > xmax ou y < ymin ou y > ymax, le point n'est pas dedans
• Ensuite, pour vraiment tester, voir la méthode traditionnelle de savoir si un point appartient à un polygone : calculer l'angle (ou son signe) entre le point et 2 sommets. Répéter. Dès que l'angle change de signe, le point est en dehors.

Code :

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

1
2
3
4
  1
                   Pb
    Pa          3
2

1. (angle (Pa-1 Pa-2) * angle (Pa-2 Pa-3) * angle (Pa-3 Pa-1)) positif : Pa est intérieur
2. (angle (Pb-1 Pb-2) * angle (Pb-2 Pb-3) * angle (Pb-3 Pb-1)) négatif : Pb est extérieur.

[karistouf]

ok. merci souviron, mais en code C, comment j obtiens mon angle ?

angle (Pa-1 Pa-2)

je ne me suis pas mis pour rien dans débuter

[Médinoc]

voir la méthode traditionnelle de savoir si un point appartient à un polygone : calculer l'angle (ou son signe) entre le point et 2 sommets. Répéter. Dès que l'angle change de signe, le point est en dehors.

Salut, désolé de m'incruster comme ça, surtout pour une question pas directement pertinente, mais juste pour ma curiosité personnelle: Cela marche-t-il uniquement pour les polygones convexes ?