Discussion :

[FlowFrom05]

Bonjour a tous,

Par avance desole pour l'absence d'accent mais j'utilise un clavier uk.

voici mon petit probleme: je dispose de deux ellipses (sur un plan cartesien, c'est une image 2D en fait) dont je connais pour chacune la largeur (dx), la hauteur (dy), et le centre (centroid.x ou .y).
Mon but et de savoir si ces ellipses se chevauchent ou non.
En gros ce que j'ai fais c'est recuperer les variables suivantes: la distance entre les deux centres des ellipses (distCenter), la distance enter les centres en X (distCenterX), la meme chose en Y (distCenterY).

Si je reflechi bien je suis face a 4 cas de figures possible:
- mon ellipse de reference se trouve en bas a droite de la seconde
- mon ellipse de reference se trouve en bas a droite de la seconde
- mon ellipse de reference se trouve en haut a droite de la seconde
- mon ellipse de reference se trouve en haut a droite de la seconde

j'omet pour l'instant les cas ou les x et y des deux ellipses sont egaux...

voici mon code:
pour info:
polygonList[compt] = un objet polygone duquel je recupere mes variables tel que le centre dudit objet, sa largeur, sa hauteur, etc... polygonList[compt2] etant bien evidemment le second objet (seconde ellipse).

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
53
54
55
56
57
58
59
 
                     	double distCenterX, distCenterY, distCenter, angle1, angle2, pi, x1 , y1, x2, y2, a1, b1, da1, db1, a2, b2, da2, db2;
                        pi=3.14;
                        // represente en gros mon hypotenuse
			distCenter = sqrt(pow(polygonList[compt]->centroid.datapointx - polygonList[compt2]->centroid.datapointx, 2) + pow(polygonList[compt]->centroid.datapointy - polygonList[compt2]->centroid.datapointy, 2));
 
			//4 possibilities
			if (polygonList[compt]->centroid.datapointx > polygonList[compt2]->centroid.datapointx && polygonList[compt]->centroid.datapointy < polygonList[compt2]->centroid.datapointy) {
				distCenterX = polygonList[compt]->centroid.datapointx - polygonList[compt2]->centroid.datapointx;
				distCenterY = polygonList[compt2]->centroid.datapointy - polygonList[compt]->centroid.datapointy;
				angle1 = acos(distCenterY / distCenter)* (180 / pi);
				angle1 = angle1 + 90;
				angle2 = acos(distCenterX / distCenter)* (180 / pi);
				angle2 = 360 - angle2;		
			}
			else if (polygonList[compt]->centroid.datapointx < polygonList[compt2]->centroid.datapointx && polygonList[compt]->centroid.datapointy < polygonList[compt2]->centroid.datapointy) {
				distCenterX = polygonList[compt2]->centroid.datapointx - polygonList[compt]->centroid.datapointx;
				distCenterY = polygonList[compt2]->centroid.datapointy - polygonList[compt]->centroid.datapointy;
				angle1 = acos(distCenterY / distCenter)* (180 / pi);
				angle1 = 90 - angle1;
				angle2 = acos(distCenterX / distCenter)* (180 / pi);
				angle2 = angle2 + 180;	
			}
			else if (polygonList[compt]->centroid.datapointx < polygonList[compt2]->centroid.datapointx && polygonList[compt]->centroid.datapointy > polygonList[compt2]->centroid.datapointy) {
				distCenterX = polygonList[compt2]->centroid.datapointx - polygonList[compt]->centroid.datapointx;
				distCenterY = polygonList[compt]->centroid.datapointy - polygonList[compt2]->centroid.datapointy;
				angle1 = acos(distCenterY / distCenter)* (180 / pi);
				angle1 = 360 - angle1;
				angle2 = acos(distCenterX / distCenter)* (180 / pi);
				angle2 = angle2 + 90;
			}
			else if (polygonList[compt]->centroid.datapointx > polygonList[compt2]->centroid.datapointx && polygonList[compt]->centroid.datapointy > polygonList[compt2]->centroid.datapointy) {
				distCenterX = polygonList[compt]->centroid.datapointx - polygonList[compt2]->centroid.datapointx;
				distCenterY = polygonList[compt]->centroid.datapointy - polygonList[compt2]->centroid.datapointy;
				angle1 = acos(distCenterY / distCenter)* (180 / pi);
				angle1 = angle1 + 180;
				angle2 = acos(distCenterX / distCenter)* (180 / pi);
				angle2 = 90 - angle2;
 
			}
 
 
			a1 = polygonList[compt]->dx / 2;
			b1 = polygonList[compt]->dy / 2;
			da1 = polygonList[compt]->dx;
			db1 = polygonList[compt]->dy;
 
			a2 = polygonList[compt2]->dx / 2;
			b2 = polygonList[compt2]->dy / 2;
			da2 = polygonList[compt2]->dx;
			db2 = polygonList[compt2]->dy;
 
			angle1 = angle1*(pi / 180);
			angle2 = angle2*(pi / 180);
 
			x1 = polygonList[compt]->centroid.datapointx + (a1 * cos(angle1));
			y1 = polygonList[compt]->centroid.datapointy + (b1 * sin(angle1));
			x2 = polygonList[compt2]->centroid.datapointx + (a2 * cos(angle2));
			y2 = polygonList[compt2]->centroid.datapointy + (b2 * sin(angle2));

Dans l'idee je trace une droite entre les deux centres (distCenter); je trace une droite en x (distCenterX) et une en y (distCenterY). de la j'obtiens un rectangle "virtuel" duquel je deduis mes angles 1 et 2 que je convertis ensuite en radian. Cette operation s'effectue en fonction de la ou se trouve mon ellipse secondaire (polygonList[compt2]) par rapport a l'ellipse de reference (polygonList[compt]) (mes if, elseif ...).
De la je tente ensuite de trouver les points x1 et y1 qui sont censes representer le point ou la droite virtuelle reliant mes deux centres des ellipses (distCenter) coupe mon ellipse de reference. Idem pour x2 et y2 qui sont les coordonees cette foi ci du point qui est cense representer l'endroit ou a droite entre mes deux centres coupe l'ellipse secondaire.

c'est confus n'est-ce pas...?

Apres moulte tests, mes angles semblent bons, mes distances aussi. A ce niveau la ce sont mes connaissances en prog et en geometrie qui ne suivent plus. Donc ami(e)s dev, pourriez vous me venir en aide: pourquoi mes points x1,y1 et x2,y2 ne tombent en rien la ou je les attend ? ou me trompe-je ?

je precise que les ellipses ne sont pas necessairement toujours applaties, elles ne sont par contre jamais inclinees!

De plus, desole pour le code "usine a gaz", mais je ne suis pas du tout developpeur... merci de votre comprehension

edit: vous l'aurez compris, ce code est inclu dans une double boucle for...
edit2/ une image saura davantage vous expliquer que mes loooongues phrases; voici donc mon art



et les 4 cas de figures, et leurs angles:



je cherche donc les coordonnees des points en cyan sur l'image.

Merci :°)

Flo

[Iradrille]

Hello,

Je ferais le calcul en 2 étapes :
- remplace tes ellipses par des rectangles et vérifie s'ils se chevauchent (c'est rapide, pas de sqrt / sin / cos)
- si les rectangles se chevauchent tu continue

L'équation d'une ellipse est
x = u + a cos(t)
y = v + b sin(t)

avec {x,y} un point de l'ellipse
{u,v} le centre
a le grand rayon : max(dx / 2, dy / 2) dans ton cas
b le petit rayon : min(dx / 2, dy / 2)
t l'angle : angle1 ici

Code :

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

1
2
3
4
5
a1 = polygonList[compt]->dx / 2;
b1 = polygonList[compt]->dy / 2;
 
a2 = polygonList[compt2]->dx / 2;
b2 = polygonList[compt2]->dy / 2;

A priori ya une erreur ici : dx n'est pas forcément le grand rayon.

[FlowFrom05]

Merci pour ta réponse (enfin un clavier fr !).

En effet l’ensemble du code passe par une analyse du chevauchement des rectangles, bien vu !!

Les équations de trigo que tu me donne sont donc déjà implémentées au code. En fait Polygon[compt].centroid.dx ou dy est la largeur et longueur en x et y de mon rectangle. je me ressert de ces variables pour définir les axes x et y de mon ellipse, qui est finalement virtuelle, elle n'existe jamais réellement dans mon code. Et j'ai beaucoup de mal a réutiliser la distance dx pour obtenir mon point y dans la formule y=b.sin(t). En fait j'en vois pas la logique. J'ai déjà cependant essayer de faire deux petits if pour inverser les demi grand axes si dy > dx mais les x1 y1 x2 y2 ne tombent toujours pas juste...

je ne comprend plus ou se situe mon erreur. peut être mes angles? je suis tout perdu..

help

Flo