Ellipse et coordonéésRésolu

Question

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

KX · Answer

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

KX · Answer

Remarque :

Ton idée de départ de tracer une ligne entre les deux ellipses est fausse.
Voici un contre exemple :

Flow05 · Answer

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

KX · Answer

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 · Answer

Merci KX, je vais tester ton code et l'appliquer a mes ellipses. je te tiens au courant

Flow05 · Answer

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

Flow05 · Answer

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.

KX · Answer

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

KX · Answer

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.

Flow05 · Answer

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

Ellipse et coordonéés

10 réponses

Votre réponse

Discussions similaires