Discussion :

[tlemcenvisit]

Salut,

Je cherche à avoir le rayon et le centre de la boule minimale qui contient un ensemble de n points de l'espace, les coodronnées de ces points sont données par x[i], y [i] et z[i] avec i=1..n

Quelqu'un a une idée?
merci d'avance

[benratti]

A priori, je dirais que tu dois regarder les deux points les plus espacer et ca va te donner le diametre de ta boule. pour le centre, tu prends le centre du segment composer de ces deux points...

[tlemcenvisit]

Faux !

Je raisonne en 2D, en 3D c'est pareil,
Si tu prends trois points d'un triangle équilatéral, si tu prends ensuite un cercle (ou une boule) qui passe par deux points, il ne contiendra pas le troisième !

[Kangourou]

t'as un lien pour un algo en n*log(n) ici :

http://www.cs.brown.edu/people/tor/java/mec/

mais faut deja avoir qlq fonction de geometrie sous la main

Sinon une version recursive pour matlab :
http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=6457&objectType=FILE

a+

[tlemcenvisit]

Merci !

Aïe ! ça parait compliquer à implémenter,
En fait, je n'aurai en général que dix points dans le pire des cas, je peux me permettre donc d'augmenter la complexité, existe-t-il une version plus simple à implémenter (même si elle est plus couteuse en temps de calcul )

[tlemcenvisit]

La version de matlab parrait plus facile à implémenter et facilement généralisable

[FrancisSourd]

Si tu as peu de points, tu peux utiliser le fait que la sphère est circonscrite à 4 points. Cela donne comme algo

Code :

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

1
2
3
4
5
6
7
8
9
 
S nuage de points
R = infini
Pour chaque quadruplet (a,b,c,d) de S,
  calculer la sphère B(x,r) définie par (a,b,c,d)
  Si B(x,r) contient S et si r < R
     B = B(x,r)
     R = r
Renvoyer B

[Graffito]

Bonjour,

L'algorithme de Francis me semble globalement bon.
Toutefois, il faut aussi envisager les boules dont le diamètre est constitué par 2 points ainsi que les sphéres centée sur les centre de gravité des triangles (intersection des médianes) définis par 3 points de l'ensemble.

[FrancisSourd]

Toutefois, il faut aussi envisager les boules dont le diamètre est constitué par 2 points ainsi que les sphéres centée sur les centre de gravité des triangles (intersection des médianes) définis par 3 points de l'ensemble.

Effectivement, si aucune sphère définie par un quadruplet de points ne contient tous les points du nuage, il faut passer aux sphères définies par trois points qui ont leur centre dans le plan défini par les 3 points puis, en cas de nouvel échec prendre le diamètre maximal comme diamètre de la boule... et là on a forcément une boule qui contient tous les points!