Bonjour à tous,

Dans un graphe, j'ai beaucoup de point où j'ai leur coordonnées (x,y) et j'aimerais créer une ellipse pour tous les regrouper dedans, y a-t-il une fonction pour cela?

Merci beaucoup.

si on ne se donne pas de contraintes, il y a autant d'ellipses que l'on veut qui contiennent un ensemble fini de points.

Une contrainte usuelle assez logique, ellipse de surface minimale, conduit à un problème d'optimisation assez classique   (et de solution non élémentaire)   De mémoire, il me semble que on montre que cette ellipse  est unique. 

Bonjour,

Effectivement,  comme le dit Sennacherib, on peut montrer qu'il existe une unique ellipse de surface minimale contenant tes points: tu peux rechercher "ellipse de John-Löwner" pour trouver des détails sur le sujet. Le problème de base est plutôt dédié à un ellipsoide dans Rn de volume maximal (voire aussi ellipse de Steiner) inscrit dans un compact convexe mais ton cas est souvent traité dans Rn à la suite). C'est un sujet très apprécié des agrégatifs de Mathématiques donc tu trouveras pas mal de choses bien détaillées pour la démo théorique. (Par exemple : http://citron.9grid.fr/docs/JohnLowner.pdf)

Par contre, au niveau de la construction dans un cas concret, j'ai peur que ce soit moins documenté !

-
Edité par sylpro 6 avril 2019 à 9:56:05

Ta as beaucoup de points. On va déjà essayer de réduire le nombre de points. Si tu  prends 4 points ABCD parmi tous tes points, et si D est dans le triangle ABC, alors tu peux supprimer purement et simplement le point D, il n'apporte rien au problème. En répétant l'opération, tu vas réduire le nombre de points.

Au final, le but est d'obtenir l'enveloppe convexe de ton ensemble de points. La démarche que j'ai proposée n'est certainement pas la plus efficace pour obtenir l'enveloppe convexe, à toi de rechercher à partir de ce mot-clé.

Si on cherche une ellipse de surface minimale, comme dit maître Sennacherib, La 2ème étape est relativement compliquée.

Ou alors il résout numériquement le problème d'optimisation correspondant selon qu'on souhaite une formule ou juste les paramètres de l'ellipse pour un cas précis ...