Ellipse et coordonéés [Résolu]

Flow05 5 Messages postés samedi 3 octobre 2015Date d'inscription 8 octobre 2015 Dernière intervention - 3 oct. 2015 à 20:14 - Dernière réponse : Flow05 5 Messages postés samedi 3 octobre 2015Date d'inscription 8 octobre 2015 Dernière intervention
- 8 oct. 2015 à 17:12
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).

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

Voici deux images illustrant le principe :°)





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

Help !

Merci :°)
Afficher la suite 

Votre réponse

11 réponses

KX 15781 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 octobre 2018 Dernière intervention - 3 oct. 2015 à 22:21
0
Merci
Bonjour,

Mathématiquement une ellipse n'a pas qu'un centre, elle a aussi deux foyers aux propriétés bien plus intéressantes.
Pour n'importe quel point sur l'ellipse, la distance au 1er foyer ajoutée à la distance du 2è foyer, est toujours égale.
On peut donc facilement déterminer si un point est à l'intérieur de l'ellipse si cette somme des distances aux foyers est inférieure.

Un moyen simple de déterminer si deux ellipses se coupent est de se promener sur "chaque point" de la première ellipse pour savoir s'ils sont à l'intérieur de la seconde ellipse.

Remarque : puisque le nombre de points sur une ellipse est infini, je te conseille de t'intéresser au point de la première ellipse pour lequel la somme des distances aux foyers de la seconde ellipse est minimale (on peut faire cela par dichotomie sur l'angle).
Commenter la réponse de KX
KX 15781 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 octobre 2018 Dernière intervention - 3 oct. 2015 à 23:38
0
Merci
Remarque :

Ton idée de départ de tracer une ligne entre les deux ellipses est fausse.
Voici un contre exemple :
Commenter la réponse de KX
Flow05 5 Messages postés samedi 3 octobre 2015Date d'inscription 8 octobre 2015 Dernière intervention - 4 oct. 2015 à 13:31
0
Merci
Merci KX pour ta réponse. Effectivement ton exemple prouve que les ellipses seules ne suffisent pas à contraindre mon problème. cependant je passe d'abord par une procédure qui vise à vérifier si deux rectangles se chevauchent ou non, et dans ton contre exemple cette procédure suffirait à elle seule. Mais tu a soulevé un problème intéressant, et je dois trouver une solution à ça.

Je vais m'intéresser aux foyers. mais le problème reste le même, mon code n'arrivent pas a me faire trouver un point (x,y) sur le périmètre d'une ellipse, et je ne sais toujours pas ce qui cloche....
Commenter la réponse de Flow05
KX 15781 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 octobre 2018 Dernière intervention - Modifié par KX le 4/10/2015 à 13:53
0
Merci
Le périmètre d'une ellipse se calcul en fonction des foyers.
Si tu n'as pas les foyers tu ne peux pas faire grand chose.

Je considère que (x0,y0) est le centre de l'ellipse, dx et dy les rayons (pas les diamètres !), je calcule (fx,fy) et (gx,gy) qui sont les deux foyers.

        if (dx > dy) {
            a = dx;
            b = dy;
        } else {
            a = dy;
            b = dx;
        }
        c = Math.sqrt(a*a-b*b);
        if (dx > dy) {
            fx = x0 - c;
            fy = y0;
            gx = x0 + c;
            gy = y0;
        } else {
            fx = x0;
            fy = y0 - c;
            gx = x0;
            gy = y0 + c;
        }

    // somme des distances aux foyers pour (x,y)
    private double distance(double x, double y) {
        double dfx = x - fx;
        double dfy = y - fy;
        double dgx = x - gx;
        double dgy = y - gy;
        return Math.sqrt(dfx*dfx+dfy*dfy) + Math.sqrt(dgx*dgx+dgy*dgy);
    }

    // test si l'ellipse contient (x,y)
    public boolean contains(double x, double y) {
        return distance(x, y) <= 2*a; // sur l'ellipse si égalité, à l'intérieur si inférieur
    }

PS. je code en Java, mais les maths sont similaires.
Flow05 5 Messages postés samedi 3 octobre 2015Date d'inscription 8 octobre 2015 Dernière intervention - 8 oct. 2015 à 17:12
KX, j'ai employe ta solution. je ne suis pas sur que mes foyers soient bien defini cependant (parfois je trouve qu'ils sont tres tres pres des bords des ellipses, mais peut etre est-ce normal ?)

Donc voici comment j'ai implemente ton code:

	for (double i = 0; i <= 360; i = i+1) {
testAngle = 2 * pi*(i / 360);
////r2
if (test2) {
x2 = polygonList[compt2]->centroid.datapointx + a2 * cos(testAngle);
y2 = polygonList[compt2]->centroid.datapointy + b2 * sin(testAngle);
if (distanceFoyer(x2, y2, fx1, fy1, gx1, gy1, a1)) {
myfile4 << polygonList[compt]->id << "," << polygonList[compt]->centroid.datapointx << "," << polygonList[compt]->centroid.datapointy << "," << polygonList[compt2]->id << "," << polygonList[compt2]->centroid.datapointx << "," << polygonList[compt2]->centroid.datapointy << endl;
}
}
else {
x2 = polygonList[compt2]->centroid.datapointx + b2 * cos(testAngle);
y2 = polygonList[compt2]->centroid.datapointy + a2 * sin(testAngle);
if (distanceFoyer(x2, y2, fx1, fy1, gx1, gy1, a1)) {
myfile4 << polygonList[compt]->id << "," << polygonList[compt]->centroid.datapointx << "," << polygonList[compt]->centroid.datapointy << "," << polygonList[compt2]->id << "," << polygonList[compt2]->centroid.datapointx << "," << polygonList[compt2]->centroid.datapointy << endl;
myfile5 << polygonList[compt]->id << "," << polygonList[compt2]->id << "," << x2 << "," << y2 << endl;
}
}
}


En gros je prend mon ellipse de reference, et je fais le tour de l'ellipse secondaire, degre par degre. Voici ce que renvoie la fonction distanceFoyer:

bool distanceFoyer(double x2, double y2, double fx1, double fy1, double gx1, double gy1, double a1)
{
double dfx = x2 - fx1;
double dfy = y2 - fy1;
double dgx = x2 - gx1;
double dgy = y2 - gy1;
double distance = sqrt(dfx*dfx + dfy*dfy) + sqrt(dgx*dgx + dgy*dgy);
if (distance <= 2 * a1) {
return true;
}
else {
return false;
}
}


C'est pompeux comme code mais ca semble marcher !
Commenter la réponse de KX
0
Merci
Merci KX, je vais tester ton code et l'appliquer a mes ellipses. je te tiens au courant
Commenter la réponse de Flow05
0
Merci
Quelques questions:

- comment obtiens tu tes x,y ? je n'arrive toujours pas a definir un point x,y sur mon ellipse
- je ne suis pas sur de la formule pour obtenir un point x,y a parti des foyer
-mes angles sont en radian, j'ai bon?

encore merci de ton aide
Commenter la réponse de Flow05
Flow05 5 Messages postés samedi 3 octobre 2015Date d'inscription 8 octobre 2015 Dernière intervention - 6 oct. 2015 à 17:27
0
Merci
j'ai rep a mes questions... maintenant petit probleme de calibrage, comme tu peux le voir sur le screenshot, les points ne sont pas tout a fait allignes et semblent ne pas se trouver sur la droite reliant les deux centres.



mes deux ellipses, bleu et orange. les centres sont relies par la ligne theorique noire.

les points violet et rouge sur les ellipses sont les points d'interceptions (output de mon code). on voit bien une legere diff2rence.
Commenter la réponse de Flow05
KX 15781 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 octobre 2018 Dernière intervention - 6 oct. 2015 à 19:29
0
Merci
Si tu veux dessiner "tout" les points (x,y) d'une ellipse tu peux utiliser l'équation paramétrée en fonction de l'angle t :

    private double getX(double t) {
        return x0 + dx * Math.cos(t);
    }

    private double getY(double t) {
        return y0 + dy * Math.sin(t);
    }

for (double t = 0; t < 2 * Math.PI; t += 0.1) {
    double x = getX(t);
    double y = getY(t);
    // dessin de (x,y)
}
Commenter la réponse de KX
KX 15781 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 octobre 2018 Dernière intervention - 6 oct. 2015 à 19:29
0
Merci
Mathématiquement, un point, une droite, ou n'importe quelle forme géométrique n'a pas d'épaisseur. Informatiquement, tu devrais donc te limiter à l'épaisseur minimum (1px) et là ce sera sûrement "aligné".

Remarque : comme je ne sais pas comment tu as fait ton dessin je ne peux pas te dire ce qui est faux.
Commenter la réponse de KX
Flow05 5 Messages postés samedi 3 octobre 2015Date d'inscription 8 octobre 2015 Dernière intervention - 7 oct. 2015 à 00:05
0
Merci
En fait le même type de plot mais avec des rectangles (ellipses) davantage éloignés présentent le même style de problème, à savoir une déviation (parfois importante). A savoir d'ou ça vient maintenant. Mes définitions d'angles semblent bonnes, mais ça ne peut venir que de la...
Commenter la réponse de Flow05

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.