Discussion :

[MDiabolo]

Bonjour,

Voila je n arrive pas a trouver d informations sur les differents algorithmes existants pour calculer l equation d une sphere a partir d un nuage de points.

Je pense que cela est un probleme connu donc j aimerai faire appel a vos connaissances pour trouver des liens et de la litterature.

Merci d avance pour votre aide.

[ToTo13]

Bonjour,

ta question est plutot imprécise dans le sens où :
1 - Est ce que t uveux l'équation de la sphère qui englobe ton nuage de points ?
2 - Est ce que tu veux l'équation de la sphère passant par trois points ?

L'équation d'une sphère est de la forme :
(X-Xc)^2 + (Y-Yc)^2 = R^2

Sinon la solution des deux est de toute façon tres simple.

[MDiabolo]

Bonjour, merci pour ta reponse.

Oui j ai ete imprecis. En fait j ai a ma disposition une liste de points (tous senses etre equidistants du centre de la sphere a + ou - les erreurs de mesure). Mon probleme est de trouver le centre de cette sphere.

En ce moment j utilise un algorithme (que je n ai pas programme) derive de DownHill simplex mais il ne me donne des resultats mediocres.

Une des contraintes entre autres est que l echantillonement des points ne peut pas se faire sur "l ensemble de la surface de la sphere" mais plutot seulement dans une liberte de mouvement d environ 30°.
Est- ce clair ?

[Matthieu Brucher]

Tu as donc une fonction de coût à minimiser, les paramètres étant le centre de la sphère et son rayon. Tu peux utiliser d'autres algos plus classiques qui convergent directement si tu utilises une fonction de coût quadratique tel Newton, ...

[ToTo13]

Bonjour,

la première partie est claire, mais pas la deuxième (mais j'avoue tourner un peu au ralenti).

Par contre, tu parles de sphère, et non de cercle, donc le fait d'etre en 3D rendra les choses un peu plus compliqué.

En tout cas :

En fait j ai a ma disposition une liste de points (tous senses etre equidistants du centre de la sphere a + ou - les erreurs de mesure).

Si c'est le cas, il est facile de trouver le centre : en faisant le barycentre des points. Puis pour le rayon, soit tu prends le rayon moyen, ce qui peut etre plutot bon, soit tu fais une sorte d'histogramme des distances entre les points et le barycentre, ce qui raffinera ta solution en tenant compte des erreurs de mesure.

La meilleure solution, si tu as vraiment des erreurs de mesures est de faire une transformée de Hough : tu prends au hasard quatre points parmis ta liste et tu calcules le centre de la sphère passant par ces quatres points. Tu réitère cette méthode un grand nombre de fois et tu prend comme résultat, le centre qui est trouvé le plus souvent.
Le souci sera alors de trouver le centre à partir de quatre points. Ca je sais tres bien le faire en 2D, mais pas en 3D

[MDiabolo]

Bon je vais deja chercher des infos sur ce sujet.

Je vais essayer de formuler differemment:
je ne peux pas decrire toutes la sphere a travers mon mouvement. Du coup le nuage de points ne represente qu un pourcentage de la sphere. Pour faire l analogie 2D, c est un peux si tu devais trouver le centre du cercle, et le rayon a partir des points places sur un arc de 30° ( et non 360°). Est ce plus clair ?

[ToTo13]

Oui, c'est tres clair et tres faisable en 2D.

La solution reste la meme en 3D, mais je ne sais pas comment trouver le centre d'une sphère passant par quatre points.
dsl

[MDiabolo]

As tu des liens expliquant ceci pour un cercle. Ca me ferait de bonnes bases deja.

Mais du coup l algorithme du simplex ne te semble pas adapte ici ?

Car je n ai pas precise, actuellement avec l algorithme utilise ca marche mais c est tres tres sensible. Du coup des fois, il me retourne des valeurs aberrantes ( du genre un centre en dehors de la sphere)...

[ToTo13]

Bonjour,

effectivement, je ne vois pas bien ce que le simplex ferait ici.

Pour la 2D, je n'ai pas de doc, cela est assez évident :
- Tu prends trois points se situant sur le cercle.
- Tu calcules le centre du cercle passant par ces trois points. pour cela tu calcules l'intersection des médiatrices des segments formés par les trois points. Ce qui mathématiquement est simple.
- Si tu as un taux d'erreur sur la position des points, tu réitère cela en prenant plusieurs séries de trois points et tu regardes quel est le centre qui apparait le plus souvent.

Mais pour la 3D, l'intersection des normales au plan formé par trois points de marche pas.

[Matthieu Brucher]

Dans le cas de points bruités et de plus de 4 points de manière générale, tu fais :
- poser des paramètres arbitraires - genre centre (0,0,0) rayon 1 -
- tu calcules l'erreur de reconstruction : norme(point - centre) - rayon
- tu minimises cette erreur avec un algorithme simple style descente de gradient, Newton ou quasi-Newton.

[MDiabolo]

Merci pour toutes ces infos,

je vais continuer a potasser ca ce soir.

Selon vous a quoi peu etre du un resultat aberrant dans l utilisation de l agorithme de la descente du simplexe ? Des fois ca marche, des fois ca marche pas et je me retrouve avec un centre et un rayon de sphere ne coincident pas du tout avec les points echantillones.

[Guigui_]

Je ne sais pas si je dis une bêtise, mais je pense que tu as aussi la possibilité de résoudre un système d'équation linéaire:
C'est ce que j'utilise pour trouver l'équation d'une ellipse (en fait d'une conique) à partir d'un nuage de point. J'avais parfois le souci qu'il me trouvait plutôt une parabole ou une hyperbole ( car parfois il me manquait des points dans certaines régions). Je ne sais pas si pour une sphère/cercle il peut y avoir des soucis du même genre.
En tout cas, il faudrait partir d'un équation linéaire du type
x^2+y^2+z^2-2ax-2by-2cz+d = 0 (=> 4 inconnues a,b,c,d, (a,b,c) étant le centre de la sphère et d =a^2+b^2+c^2-r^2, ce qui permet ensuite de trouver le rayon) et autant d'équations que tu as de points dans ton nuage (par contre, est-ce qu'on trouve toujours une équation de sphère ?)
http://www.developpez.net/forums/vie...110&highlight=

[Matthieu Brucher]

Ton équation, c'est une équation de sphère, clairement il y a autant de paramètres que dans ma proposition
D'ailleurs, si tu écris toutes les équations, tu verras que tu as un problème linéaire. La solution que j'ai proposé avec un optimiseur de Newton te trouve en 1 itération l'optimum de ce problème.

[j.p.mignot]

pour ce type de problème un moindre carré est tout indiqué

[Graffito]

Bonjour,

Que penseriez vous d'une approche en 2 étapes ?

Etape 1 :
- on grouper les points par groupe de 4,
- on cherche les centres des sphéres définies par chaque groupe,
- on détermine le barycentre des centres ainsi obtenus, ce qui donne un centre prrovisoire.

Etape 2 :
- on élimine les points "aberrants" (situés à une distance anormale du centre provisoire),
- on refait l'étape 1 pour trouver le centre définitif.

[Rafy]

Si c'est le cas, il est facile de trouver le centre : en faisant le barycentre des points.

hum ça c'est pas vrai...
Si tous les points sont par exemple compris dans une hemisphere, alors le barycentre des points ne donnera pas le centre....

[Matthieu Brucher]

Non, trop long. Les moindres carrés peuvent converger tout de suite avec une fonction quadratique telle que celle-ci !

[MDiabolo]

Merci pour toutes ces idees... je suis en train de bosser dessus.

Je me demande toujours pourquoi ca ne marche pas des fois avec le simplexe: pensez vous que cela peut etre du au point de depart ?

[Matthieu Brucher]

Au fait, c'est quel simplexe que tu utilises ? Celui qu'on appelle aussi polytope : on prend un barycentre des meilleurs points, on regarde si c'est meilleur, ... et on le garde ?
Normalement, il devrait converger. Si ce n'est pas le cas, c'est qu'il est pris dans un minimum local - peu probable vu la tête de la fonction de coût - ou que tu as mal défini ta fonction de coût.

[BugFactory]

Les forts en maths pourraient peut-être résoudre ce problème de cette façon.

Si on a deux points distincts de la sphere, le centre est forcément sur le plan médiant du segment ayant ces deux points pour extrémité.

Si on a un deuxième segment, on a deux plans, dont l'intersection est une droite où se trouve le centre.

Un troisième segment donnerait un troisième plan, dont l'intersection avec la droite donne le centre.

Attention aux cas particuliers! Par exemple si les trois segments sont les cotés d'un triangle, les trois plans se coupent en une même droite.

Reste à poser les équations des plans à partir des positions des points, en déduire celles des intersections, mettre en place un test pour vérifier que l'on est pas dans un cas particulier.

Je suis personnellement bien trop fainéant.