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 ?

[tbc92]

Oui, la fonction en question retourne tous les groupes possibles de r points choisis parmi un tableau.
Donc appliqué à cette situation, il faut initialiser r avec r = Pourcentage voulu *NbTotal Points
Avec éventuellement un arrondi supérieur.

[Sylvain255]

je doute du programme cité dans le thread de stackoverflow que j'ai cité car il me paraît trop simple au vue de l'article cité dans le post précédent,
Voici l'article en question car l'autre lien pointe vers un 404 : http://www.cs.cornell.edu/courses/cs...A6/Ellipse.pdf Apparemment en R il existe une fonction pour ça : https://community.rstudio.com/t/fit-...oints/134018/4 pour le second article qui mène aussi à un 404 voici : https://refubium.fu-berlin.de/bitstr.../1/1998_05.pdf
Le second article est plus intéressant car il propose une implémentation en C++, l'article date de 1998 donc c'est un problème réglé depuis longtemps les 100%
je vais tenter d'implémenter la méthode C++ de l'article + mon petit algo et si j'y arrive je mettrai en résolu, au pire je prendrai la fonction R

[tbc92]

Le traitement sera très long. Il y a un truc que tu peux faire pour beaucoup optimiser le code (en particulier si le pourcentage p de points est dans une fourchette comme [30% ,70%]
Dans ces ordres de grandeurs, le nombre de combinaisons de r points parmi n est très grand. Par exemple, il y a 47 129 212 243 960 façons de choisir 30 points parmi 50 !

Quand tu as choisi r points, tu commences par calculer l'enveloppe convexe de ces r points. C'est peu coûteux.
Si à l'intérieur de ce polygone, il y a au moins un point qui ne fait pas partie des r points choisis, alors tu sais déjà que cette combinaison de r points ne sera pas optimale. Pas la peine de chercher l'ellipse correspondant à ces n points.
Idem, si tu as r points qui ont passé ce premier test, tu peux calculer la surface de l'enveloppe convexe. Surface d'un polygone, ça va. Si cette surface est plus grande que la meilleure ellipse déjà trouvée, pas la peine d'aller plus loin avec cette liste de r points.

Bon, même avec cette optimisation, chercher les enveloppes convexes de 47 129 212 243 960 listes de 30 points, ça va être long.
Et donc, il faut d'entrée essayer d'éliminer les points les plus excentrés, ou quelque chose du genre.

[Sylvain255]

Ok comment tu calcule le nombre de combinaisons STP ? le pourcentage devrait être aux alentours de 90%

il y a une autre méthode : c'est de choisir le barycentre des points et de faire grossir un cercle depuis ce centre et quand on a environ P% de points dans le cercle on sait qu'on est proche de la solution

mais si le problème est trop complexe je vais embaucher un mathématicien

ah je viens de trouver cette discussion :

https://stackoverflow.com/questions/...en-points-in-r
https://exchangetuts.com/ellipse-con...40399763954714

après pour trouver l'algo il suffit de décoder le code source de R.

ou regarder directement le source ici : https://github.com/wch/r-source

[tbc92]

La formule donnant le nombre de combinaisons est très simple.
Sous excel ou un autre tableur, , tu tapes =Combin(50;30) et tu auras le nombre de mon precédent message.

C'est quoi cette fonction combin ? combin(a,b) = a! / ( b! * (a-b)!)
Donc ici : Combin(50,30) = 50! / (30! 20!) = (50*49*...*32*31)/(20*19*18...*3*2*1)

[dourouc05]

Pour répondre à la question d'origine, il existe des techniques à base de SDP pour minimiser le volume d'une ellipse qui englobe des points : https://math.stackexchange.com/quest...te-program-sdp

[Flodelarab]

Ne serait-ce pas une situation merveilleuse pour utiliser un algorithme génétique ? On tâtonne en faisant varier le centre, l'inclinaison d'un axe, les 2 rayons. On voit alors le pourcentage d'inclusion de chaque situation. Et après quelques générations, on aura sans doute l'optimum.

[dourouc05]

Et après quelques générations, on aura sans doute l'optimum.

Ou rien du tout. Je n'ai pas connaissance de véritables résultats de convergence d'un algo génétique, même sur un problème convexe (ce qui est le cas ici), c'est-à-dire extrêmement facile à résoudre (d'un point de vue théorie de la complexité, pas forcément en pratique ) ; le mieux que j'ai, c'est des choses comme https://ls11-www.cs.tu-dortmund.de/p...papers/CCJ.pdf, avec des résultats d'une utilité douteuse. L'approche que j'ai citée, à base de SDP, aura la solution optimale en temps polynomial (en pratique, je suppose qu'il faudra un très bon solveur comme présenté sur http://plato.asu.edu/ftp/sparse_sdp.html).

[Guesset]

Bonjour,

Sauf si je n'ai pas bien compris SDP, il s'adresse à un ensemble de points en ignorant tout autres points. Cela veut dire que si je m'intéresse à 50 points parmi 100, SDP va bien trouver l'ellipse qui encadre ces 50 points mais sans me garantir qu'il n'y en a pas plus.

Bien sûr, une étude préalable des points dans et sur l'enveloppe convexe des 50 points donne rapidement une impossibilité si le total est supérieur à 50. S'il y a plus de 50 points dans l'enveloppe convexe des 50 points donnés, ce n'est même pas la peine d'appliquer SDP car il n'y a pas de solution (au sens du problème posé)

Mais ce n'est pas suffisant, même si l'enveloppe convexe n'embarque pas d'intrus, la solution SDP peut être en défaut. En effet, il peut y avoir des points dans les surfaces entre le contour convexe et les limites de l'ellipse trouvée.

On voit alors que SDP seul ne répond pas au problème posé.

J'aurais tendance à inverser le problème en travaillant sur le grand axe de la distribution de points (i.e. la droite qui supporte le segment des 2 points les plus éloignés) et, à partir des projections triées des autres points sur cet axe (l'un des deux points extrêmes étant choisi comme origine) progresser jusqu'à avoir le nombre de points représentant le taux requis dans l'un des 2 demi-plans délimités par la droite orthogonale à l'axe de projection et passant par le point courant. Pour toute progression d'un seul point, il existe une ellipse qui n'embarquera pas de points inopportuns.
Cependant il n'y pas garantie de trouver exactement le nombre de points recherché. Par exemple, si deux points ont la même projection on peut passer de 49 à 51 sans jamais avoir les 50 requis. Cela ne signifie pas qu'il n'y a pas de solution. En prenant le grand axe on minimise les risques sans les faire disparaître. Pour optimiser les chances, on peut travailler avec une fenêtre glissante. En désespoir de cause il faut changer d'axe de projection...

Je ne sais pas si c'est très clair.

Salutations

[tbc92]

Qui peut le plus peut le moins.
Tu interprètes l'énoncé ainsi : On cherche une ellipse aussi petite que possible, qui contienne exactement n points.
Et je l'interprète : On cherche une ellipse aussi petite que possible, qui contienne au moins n points.

[Flodelarab]

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.

[Guesset]

Bonjour,

Le post originel disait "je souhaiterais tracer l'ellipse la plus petite qui englobe un certain pourcentage P de points" donc effectivement je l'interprète comme un nombre de points donnés (à une unité près). Sinon il suffit de dire que tout % est dans 100% et d'entourer l'ensemble de tous les points ce qui est assez simple. Mais dans ce cas, à quoi sert de parler de % ?

Le PO pourrait peut être nous éclairer.

Salutations

[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