Discussion :

[Sylvain255]

Bonjour,
j'ai un ensemble de points (xi,yi) et je souhaiterais tracer l'ellipse la plus petite qui englobe un certain pourcentage P de points SVP Cette ellipse peut être oblique. Et je suis dans un plan cartésien.
Merci
Bien cordialement

[tbc92]

Dans l'échelle des difficultés, entre le précédent exercice et celui-ci, on fait un bond énorme !

Je te propose un exercice intermédiaire (un que je sais à peu près faire) très proche de ton précédent exercice :

On a n points dans le plan.
On veut garder un maximum de points, sachant qu'on s'interdit d'avoir 2 points à une distance inférieure à D fixé (donc le même exercice qu'hier, mais dans le plan et non sur une droite).
Je pense que les mécanismes de raisonnement nécessaires seront assez proches de ceux nécessaires pour ce nouvel exercice, mais en beaucoup plus simples.

Cet exercice avec une ellipse et en plus avec des axes qui peuvent-être inclinés, il est franchement difficile.

[Flodelarab]

Bonjour

L'énoncé n'a démontré ni l'existence, ni l'unicité de la dite ellipse.

[Sylvain255]

j'ai trouvé ça :
https://stackoverflow.com/questions/...-around-points
ça ne fait pas avancer la discussion ?
ça trace une ellipse autour de 100% des points
appelons cet algo X

un algo brute force qui répond à la question pourrait être :

Code :

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

1
2
3
4
5
6
7
8
9
10
min_aire=+Infini
Ellipse bonne_ellipse
pour chaque combinaison V de points correspondant à P% du total :
   tracer l''ellipse E englobant V grâce à X
   calculer l''aire A de l''ellipse E
   si A < min_aire alors
      min_aire=A
      bonne_ellipse=E
   finsi
finpour

la question est maintenant comment trouver chaque combinaison V de points correspondant à P% du total

[tbc92]

Comment trouver chaque combinaison correspondant à P% des points, je dirais que c'est facile.
Dans certains langages (Python), il y a des commandes toutes faites. cf : itertools.combinations

[Sylvain255]

ok merci dans :
"Return r length subsequences of elements from the input iterable."
length correspond à n*P/100 ?

[wiwaxia]

Bonjour,

... j'ai un ensemble de points (xi,yi) et je souhaiterais tracer l'ellipse la plus petite qui englobe un certain pourcentage P de points SVP Cette ellipse peut être oblique. Et je suis dans un plan cartésien ...

Il s'agit d'un problème apparenté à celui de la détermination de la droite moyenne; mais il n'a de sens que si le nuage de points présente effectivement une forme allongée, dépourvue de courbure. Dans le cas d'une forme coudée (en "V" ou en "Z") ou - pire encore - ramifiée ou lacunaire, l'ellipse obtenue ne représenterait plus rien.

On est conduit dans le cas favorable à une famille d'ellipses centrées sur l'isobarycentre du nuage, et admettant pour grand axe une droite des moindres carrés; la taille de ces courbes fermées ne dépendant que d'un paramètre sans dimension (λ), il suffit d'ajuster ce dernier à la valeur correspondant à l'enlacement du nombre de points recherché.

Le résultat ne correspond pas, en toute rigueur, à l'ellipse de dimensions minimales ... mais on n'en est pas loin. Et rien n'interdit, pour une proportion (p) donnée, de ne retenir que les points les plus proches du barycentre.

Je partage la réserve de Flodelarab, qui met en doute l'existence et l'unicité systématiques d'une telle ellipse.
Exemple parmi d'autres: l'ensemble des (N) points de coordonnées

x = a*Cos(2kπ/N) , y = b*Sin(2kπ/N) avec 0 ≤ k < N

pour lequel la proportion de points enlacés ne pourra prendre que les valeurs 0 ou 100% ... à moins de tabler sur les petits écarts contestables liés à la discrétisation de l'espace ... ou encore celui des (2N) points:

x² = a² , y = kb/N avec 0 ≤ k < N ,

pour lequel on trouve (entre autres) deux ellipses d'aire nulle pour p = 50% .

[Guesset]

Bonjour wiwaxia,

Exemple parmi d'autres: l'ensemble de points de coordonnées

x = a*Cos(2kπ/N) , y = b*Sin(2kπ/N) avec 0 ≤ k < N

pour lequel la proportion de points ne pourra prendre que les valeurs 0 ou 100% ... à moins de tabler sur les petits écarts contestables liés à la discrétisation de l'espace ...

Je pense que tu voulais mettre 2.k.n.Pi/N sinon cela ne parcourt qu'environ un tiers d'ellipse.

Avec les approches proposées, c'est inévitable car elles travaillent sur l'ensemble alors que le but est éventuellement d'entourer qu'une partie des points. Illustration :

Je ne suis pas sûr qu'il y ait toujours une solution même si j'aurais tendance à le croire.

En effet s'il existe une droite qui passe entre les points sans en toucher plus d'un et sépare le plan en 2 dont une partie présente le nombre de points recherché, il est possible de tracer une ellipse, fut elle très allongée, les entourant de grand axe // à cette droite. Or la discrétisation de la surface par les points laissera toujours un espace pour une droite. Même les alignements ne l'empêchent pas. Enfin, je n'ai pas trouvé de contre exemple

Salut

[tbc92]

@Guesset : on veut l'ellipse la plus petite possible (= de surface minimale). Donc une ellipse qui contiendrait tous les points ne sera a priori pas optimale, si on vise 60% ou 80%.

Trouver une droite qui passe par un seul point : oui, c'est toujours possible. Passant par un point, la liste des directions interdites est un nombre fini, et on a une infinité de directions possibles, et donc, c'est une certitude, on peut toujours construire une droite passant par un point et un seul.

[Guesset]

Bonjour,

Je n'ai pas dit que l'ellipse passe par un seul point, j'ai juste montré qu'il était possible de partager le plan avec une droite qui, au plus a un point de l'ensemble. Le nombre de points entourés est le nombre de points dans l'un des demi-plan (+1 s'il y a un point sur la droite de clivage).

L'objectif n'était pas de trouver la plus petite ellipse mais de répondre à la question qui restait en suspend : y a-t il une ellipse qui entoure un nombre donné de points ? Cela semblait un préalable avant de chercher la plus petite.

J'étais toujours sur un nombre n donné. Si c'est n et plus, la contrainte est moins forte et il y a évidemment une solution voire plusieurs.

L'isobarycentre est tentant mais se fait assez rapidement piégé par une distribution en haltère, de même la densité n'est pas sans risque. Illustration rapide et très perfectible :

Salutations

[wiwaxia]

Bonjour Guesset,

... Je pense que tu voulais mettre 2.k.n.Pi/N sinon cela ne parcourt qu'environ un tiers d'ellipse ...

C'était bien la bonne expression 2.k.Pi/N

mais la graphie du caractère grec n'est vraiment pas réussie, et prête à confusion.

La solution graphique que tu proposes, bien que conforme à la lettre de l'énoncé, me paraît aberrante: une parenté de forme entre le nuage de points et la frontière cherchée me semble aller de soi, on peut sinon obtenir n'importe quoi. Mais c'est peut-être là un point de vue trop restreint.

[Guesset]

Bonjour wiwaxia,

C'était bien la bonne expression 2.k.Pi/N

Même en gros, j'ai du mal à reconnaître PI mais j'aurais du y penser car, à défaut, il y aurait eu deux variables k et n. Mea culpa .

...La solution graphique que tu proposes, bien que conforme à la lettre de l'énoncé, me paraît aberrante: une parenté de forme entre le nuage de points et la frontière cherchée me semble aller de soi, on peut sinon obtenir n'importe quoi...

Si je comprends bien, tu partirais de l'ellipse minimale des 100% que tu réduirais progressivement sans la déplacer ni la tourner (sinon tu pourrais retomber sur le genre de solution du dessin).

Cela montre que le problème mériterait d'être précisé. Si chacun cherche une solution à des problèmes voisins mais subtilement différents, on peut discuter et s'amuser longtemps en vain

Salut

[wiwaxia]

... Si je comprends bien, tu partirais de l'ellipse minimale des 100% que tu réduirais progressivement sans la déplacer ni la tourner (sinon tu pourrais retomber sur le genre de solution du dessin) ...

C'est effectivement cela. Et dans le cas d'un nuage "normal" en forme de cigare, dépourvu de lacunes, le procédé a l'avantage de conduire rapidement à une solution.
Et rien n'empêche de se limiter d'emblée aux (N') points les plus proches du barycentre, pour un meilleur ajustement.

J'ai peut-être tort d'envisager le problème sous le biais de la statistique; cependant envisager les configurations les plus inattendues conduit inéluctablement à un balayage multiple, une ellipse quelconque étant caractérisée par les coordonnées de son centre, l'inclinaison de son grand axe et son excentricité - soit en tout 4 variables.

Intervient de plus la question du critère de comparaison: comment distinguer la plus petite de deux ellipses ?
Par son périmètre (à rejeter d'emblée !), son aire ? Ou par la somme des distances aux foyers (MF1 + MF2) ?
L'énoncé aurait pu effectivement donner plus de précisions ...

[Sylvain255]

j'ai trouvé cet article : http://ada-posturologie.fr/EllipseConfiance.htm

mon article fait-il avancer la discussion ?

[tbc92]

Non, même si tes données vérifient des conditions dont tu n'as pas parlé.

Si je ne m'abuse, cet article traite des données où il y a corrélation linéaire entre les 2 axes (par exemple des individus, pour lesquels on aurait mesuré la taille et le poids, ou des appartements, avec le prix et la surface).
Les points sont donc plus ou moins sur un nuage de forme d'ellipse.
Si tes points sont totalement quelconques (par exemple 2 paquets assez espacés, ou en forme en V, ou en T ...), ça ne marche pas du tout.

De plus, c'est une approche probabiliste. C'est à dire qu'on part de 2 ou 3 indicateurs synthétiques (la moyenne, la variance, la covariance) et on en déduit l'ellipse.
L'ellipse obtenue peut contenir moins de 90% des points, et elle peut aussi être un peu plus grande que l'ellipse minimale.
Il faudrait vraiment un coup de chance énorme (=impossible) pour que l'ellipse obtenue contienne 90% des données, et soit l'ellipse minimale.

[Sylvain255]

donc la bonne réponse est celle de :
11/11/2022, 16h07
wiwaxia

?

mais je ne comprends pas du tout son algo, ça me dépasse !
moi ce que je veux c'est un algo qui prend en entrée une suite de points (x,y) et le pourcentage de points attendu à l'intérieur de l'ellipse et qui nous donne en sortie les paramètres d'une ellipse
je pense qu'on peut dire que le minimum de points à fournir est trois points

je viens de trouver cet article aussi :
https://www.ngs.noaa.gov/PUBS_LIB/Al...OS107_CGS3.pdf

[wiwaxia]

Soit un nuage de (N) points, de coordonnées barycentriques

x_G = Σ_j=0^N-1x_j , y_G = Σ_j=0^N-1y_j ,

à partir desquelles on peut calculer les sommes:

S_x2 = Σ_j=0^N-1(x_j - x_G)² , S_y2 = Σ_j=0^N-1(y_j - y_G)² , S_xy = Σ_j=0^N-1(x_j - x_G)(y_j - y_G) .

L'étalement du nuage de points selon une direction donnée de vecteur unitaire u = (Cos(θ), Sin(θ)) est mesuré par la somme des carrés des produits scalaires:

S(θ) = Σ_j=0^N-1(u.GM_j)² = Σ_j=0^N-1(Cos(θ)*(x_j - x_G) + Sin(θ)*(y_j - y_G))²
= Cos(θ)²S_x2 + Sin(θ)²S_y2 + 2Sin(θ)Cos(θ)S_xy .

Cette somme, qui dépend de (θ), admet pour dérivée:

S'(θ) = 2Sin(θ)Cos(θ)(S_y2 - S_x2) + 2(Cos(θ)² - Sin(θ)²)S_xy = Sin(2θ)(S_y2 - S_x2) + 2Cos(2θ)S_xy ,

et ses extremums sont caractérisés par l'annulation de cette dernière fonction, l'égalité S'(θ) = 0 impliquant:

Tan(2θ) = 2S_xy/(S_x2 - S_y2) = T (par convention),

soit encore

2θ = Arctan(T) + kπ (avec k = 0 ou 1) ,

ce qui conduit à deux directions orthogonales:

θ₁ = (1/2)Arctan(T) et θ₂ = (1/2)Arctan(T) + π/2 .

L'égalité S_y2 = S_x2 , peu probable quoique non exclue, correspondrait à un nuage de forme circulaire, dépourvu de tout allongement.

Dans le repère (XGY) utilisant les deux axes ainsi définis, on peut associer au nuage de points l'ellipse d'équation

X²/S_x2 + Y²/S_y2 = 1 :

le retour aux anciennes coordonnées s'effectue par l'intermédiaire des équations:

x = x_G + X.Cos(θ) - Y.Sin(θ) , y = y_G + X.Sin(θ) + Y.Cos(θ) (avec θ = θ₁) ,

d'où l'expression des nouvelles:

X = (x - x_G)Cos(θ) + (y - y_G).Sin(θ) , Y = -(x - x_G).Sin(θ) + (y - y_G).Cos(θ) .

Ainsi toute famille d'ellipses coaxiales à la précédente et de même forme admettra pour équation générale

X²/S_x2 + Y²/S_y2 = λ² ;

leurs demi-diamètres restant toujours dans le même rapport:

B'/A' = λB/λA = B/A = (S_y2/S_x2)^1/2 .

Une chose est certaine, il y a 2 phases indépendantes :
Fixer la frontière, c'est-à-dire le nombre de points (qu'il soit "strictement égal" ou "au moins égal"). Cette phase est purement arithmétique. Et "facile".
Déterminer l'ellipse et les points intérieurs. Moins facile.

Il suffira de consigner toutes les valeurs de (λ) ou (λ²) dans un tableau, et de trier celui-ci selon l'ordre croissant: la réponse sera immédiate.

Calculs à vérifier.