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
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
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...
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 !
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+
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 )
La version de matlab parrait plus facile à implémenter et facilement généralisable
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
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.
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!Envoyé par Graffito
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager