La plus petite sphère contenant nuage des points

[invite34a418bf]

Bonjour à tous,

voici mon problème :

je cherche le centre et le rayon de la plus petite sphère circonscrit à un nuage de points coordonnées x,y et z.

merci de votre aide
-----

[invite986312212]

salut,

si tu as de la chance cette sphère a pour diamètre le segment qui joint les deux points les plus éloignés, mais ça peut ne pas être le cas.

[invitebe08d051]

Salut,

Premier réflexe: puisque vous ne donnez pas le nombre de points de ce nuage, rien ne garantit l'existence de cette sphère....

[invite986312212]

pourquoi n'existerait-elle pas?

j'utiliserais la stratégie suivante:
1) essayer la sphère dont un diamètre est le segment joignant les 2 point les plus distants.
2) si ça ne marche pas, essayer pour chaque triple de points la sphère dont un cercle équatorial contient ces 3 points.
3) si ça ne marche pas la sphère doit contenir au moins 4 points du nuage (je l'intuite mais je ne sais pas le montrer). Il faut donc essayer toutes les quadruples de points, chacun déterminant une sphère unique.
Il y a donc un nombre fini de cas à examiner.

[A voir en vidéo sur Futura]

[sylvainc2]

Voir le sujet 5.24: http://www.faqs.org/faqs/graphics/algorithms-faq/

[invitebe08d051]

pourquoi n'existerait-elle pas?

Pour la simple raison qu'on a un système de 4 inconnues, avec 5 points par exemple on peut trouver facilement un système n'admettant aucune solution.

Simple analogie avec la 2D: C'est comme ci vous me dites que je peux toujours trouver un cercle circonscrit à 4 points fixés du plan...

[invite51d17075]

je n'ai pas compris si la question était "physique" ou "mathematique".
ce qui fait une grosse différence.
car je ne vois aucune limite dans le monde mathematique.

[invite986312212]

Pour la simple raison qu'on a un système de 4 inconnues, avec 5 points par exemple on peut trouver facilement un système n'admettant aucune solution.

Simple analogie avec la 2D: C'est comme ci vous me dites que je peux toujours trouver un cercle circonscrit à 4 points fixés du plan...

ah d'accord. Mais ça me semblait tellement évident que j'ai pensé que Robauto cherchait le rayon de la plus petite boule contenant le nuage. Laquelle existe évidemment.

[invite34a418bf]

bonjour tout le monde ,

pour plus de détaille, mon objectif est de calculer la répétabilité et l'exactitude d'un robot (j'ai fais des mesures pour atteindre la même cible et j'ai pris 14 points ), mais avant que je puisse faire ça je dois d'abord avoir calculer la petite sphère qui contient toutes les points .

[NicoEnac]

Bonjour,

Simple analogie avec la 2D: C'est comme ci vous me dites que je peux toujours trouver un cercle circonscrit à 4 points fixés du plan...

Sauf qu'ici, on ne parle pas d'une sphère circonscrite mais d'une sphère contenant les points. Les équations deviennent alors des inéquations avec lesquelles il s'agit de trouver la sphère de rayon minimum.

Etant donné la contexte(répétabilité d'un robot), je pense qu'en prenant la sphère qui admet pour diamètre le segment entre les 2 points les plus éloignés, on devrait tomber juste (ou pas loin ^^).

[Médiat]

Mathématiquement (donc hors de l'hypothèse robot), si on considère les points (en 3D) , je ne vois pas comment définir La plus petite sphère contenant ce nuage de points.

[invite4ef352d8]

la réponse à déjà était donné, mais si ton objectif est d'évaluer la précision d'un robot qui vise une cible, pourquoi ne pas plutôt regarder le max des distance à la cible ? (enfin ou la moyenne des ecart quadratique, ou tout autre grandeur liée à la distance à la cible...) c'est quand même plus simple, et je trouve plus représentatif...

[invite986312212]

on peut voir ça comme un problème de statistiques. Un statisticien calculerait la position moyenne (le barycentre des points) et appellerait la différence entre cette position et la cible le "biais". Il calculerait ensuite la matrice de variance et la diagonaliserait. Le nuage serait alors représenté par un ellipsoïde (et non une sphère) ce qui a l'avantage de pouvoir mettre en évidence une éventuelle anisotropie des erreurs. Tout ça se fait très bien avec l'analyse en composantes principales.

[invite79d10163]

Bonjour,

Ce problème est bien connu et renseigné sur wikipedia, les références à des algorithmes sont aussi sur cette page:
http://en.wikipedia.org/wiki/Smallest_circle_problem

Mathématiquement, pour trouver la "plus petite" (au sens du rayon) sphère de centre c contenant un ensemble de points {p_i}, on résout le problème de minimisation suivante: min_c max _i || p_i - c ||