Je recherche un algorithme pour trouver les points d'intersection courants entre 3 sphères.
La barrage d'un algorithme complet, une description détaillée / détaillée du calcul serait grandement utile.
C'est la seule ressource utile que j'ai trouvée jusqu'à présent: http://mathforum.org/library/drmath/view/63138.html
Mais aucune méthode décrite, il est suffisamment détaillé pour que je puisse écrire un algorithme.
Je préférerais la méthode purement algébrique décrite dans le deuxième poste, mais ce qui fonctionne jamais.
6 Réponses :
Fondamentalement, vous devez le faire en 3 étapes. Disons que vous avez trois sphères, S1, S2 et S3.
La seule partie très difficile ici est l'intersection de la sphère, et heureusement Mathworld a ce bien résolu . En fait, Mathworld a également le Solution sur les intersections de cercle .
à partir de ces informations, vous devriez pouvoir créer un algorithme.
Probablement plus facile que la construction de cercles 3D, car travaillant principalement sur les lignes et les avions:
Pour chaque paire de sphères, obtenir l'équation du plan contenant leur cercle d'intersection, en soustrayant les équations sphères (chacune de la forme X ^ 2 + y ^ 2 + Z ^ 2 + a X + b < / em> Y + c + d * Z = 0). Ensuite, vous aurez trois plans P12 P23 P31.
Ces avions ont une ligne commune L, perpendiculaire au plan Q par les trois centres des sphères. Les deux points que vous recherchez sont sur cette ligne. Le milieu des points est l'intersection entre H et Q L.
Pour mettre en œuvre ceci:
construction A Cabri 3D montrant les différents plans et de la ligne L
3 Les avions n'ont pas besoin d'avoir une ligne commune. 2 avions qui se croisent dans un avion ou une ligne. 3 avions qui se croisent dans un plan, une ligne ou un point.
Dans ce cas, étant donné que les équations des plans ne sont pas indépendantes, l'intersection est un avion, soit une ligne (éventuellement à l'infini lorsque les trois centres sont colinéar). Dans le cas général, l'intersection sera une ligne.
Une implémentation de cette réponse en Python complet avec un exemple d'utilisation peut être trouvée à Cette repo github. p> Il s'avère que la solution analytique est en fait assez agréable en utilisant cette méthode et peut vous dire quand une solution existe et quand elle ne le fait pas (il est également possible d'avoir exactement une solution .) Il n'y a aucune raison d'utiliser la méthode de Newton. P> IMHO, c'est beaucoup plus facile à comprendre et à simplifier que la trilatéraité ci-dessous. Cependant, les deux techniques donnent des réponses correctes dans mes tests. P> Considérez l'intersection de deux sphères. Pour le visualiser, envisagez le segment de ligne 3D N connectant les deux centres des sphères. Considérons cette section transversale p> où la ligne rouge est la section transversale du plan avec une n. par symétrie normale, vous pouvez faire pivoter cette section transversale sous n'importe quel angle et la longueur des segments de ligne rouge ne peut pas changer. Cela signifie que la courbe résultante de l'intersection de deux sphères est un cercle et doit se situer dans un plan avec Normal n. P> qui étant dit, permet de trouver l'intersection. Premièrement, nous voulons décrire le cercle résultant de l'intersection de deux sphères. Vous ne peut pas em> le faire avec 1 équation, un cercle en 3D est essentiellement une courbe en 3D et vous ne pouvez pas décrire les courbes en 3D par 1 Eq. P> Considérez l'image
Soit P le point d'intersection de la ligne bleue et rouge. Soit H être la longueur du segment de ligne le long de la ligne rouge du point P vers le haut. Laisser la distance entre les deux centres être notés par d. Soit X la distance du petit centre de cercle à P. Ensuite, nous devons avoir P> Réponse originale H1>
(Source: GooglePages.com ) SUB> P> 
(source: GooglePages.com ) SUB> P> X = C + (h * cos t) U + (h * sin t) V for t in [0,2*PI)
L'intersection de la sphère-avion, quand elle existe, est un cercle, toujours.
Edité: l'intersection de la sphère-plan, quand il existe, est un cercle, toujours [citation nécessaire]
Hmm êtes-vous sûr? Je me souviens de l'UNIV, j'ai supposé que mon professeur a marqué le mal ... Peut-être que je me trompe mal, laissez-moi le considérer plus bien
Pour voir cela facilement (ce n'est pas une démonstration). Considérons une sphère et un avion l'intersectant. Obtenez la perpendiculaire à l'avion par le centre de la sphère et tournez tout autour de cette ligne. Rien ne change, l'intersection doit donc être invariante par rotation dans l'avion.
Seulement vrai si vous définissez un point comme un cercle, ce qui peut bouleverser des professeurs;)
Vos liens sont cassés. Vous semblez avoir changé-les à * .png à un moment donné.
L'hôte que je les ai mentionnés (Google Pages) doit d'annuler mon hébergement.
Teensy Note, je pense que vous avez manqué un terme SQRT (2) dans votre EQN pour h. Exemple, pour le cas trivial où R1 = R2 = D = 1, votre formule donne h = sqrt (1 - 1/1 * (1-1 + 1) ^ 2) = 0. Il devrait être h = sqrt (R1 ^ 2 - ((R1 ^ 2-R2 ^ 2 + D ^ 2) / 2D) ^ 2). (Scuse the Backet Hell) et la réponse pour le cas trivial ci-dessus à vérifier est SQRT (3) / 2.
C'est une solution trop compliquée, recherchez google pour trilateration ou vérifier ma réponse ...
Voici une autre interprétation de la photo postée ci-dessus:
Soit H être l'avion renversé par les centres des trois sphères. Soit C1, C2, C3 être les intersections des sphères avec h, puis C1, C2, C3 sont des cercles. Laissez LIJ Soyez la ligne Connecter les deux points d'intersection de CI et CJ, puis les trois lignes L12, L23, L13 se croisent à un point P. Soit m être la ligne orthogonale de H à P, puis vos deux points d'intersection se trouvent sur le ligne m; Par conséquent, il vous suffit de croiser m avec l'une des sphères.
Après avoir recherché sur le Web, c'est l'un des premiers hits. Je pose donc la solution la plus propre et la plus facile que j'ai trouvée après quelques heures de recherche ici: Trilateration
Ce site wiki contient une description complète d'une approche vectorielle rapide et facile à comprendre, alors on peut le coder avec peu d'effort.
C'est une très bonne façon de regarder. Je ne pense pas que ce soit moins compliqué que ma méthode proposée, il déplace simplement la "complication" en manipulation algébrique. Une chose à souligner est qu'elle utilise fortement la symétrie rotative d'une sphère sur chaque axe, ce qui rend cette méthode impossible à étendre à toutes les courbes ou surfaces sans cette propriété. Belle découverte cependant.
Voici une réponse à Python I juste porté de l'article Wikipedia. Il n'y a pas besoin d'un algorithme; Il y a une solution de forme fermée.
Andrew Je t'aime. Notez que P1, P2, P3 est créé avec numpy.array ([x, y, z]) .
Pouvez-vous confirmer que vous voulez dire des surfaces sphériques plutôt que des solides, et ajoutez quelque chose de pour que ce soit autre chose qu'une question mathématique et que la programmation est liée en quelque sorte?
Eh bien, je veux qu'un algorithme C ++ fasse cela, mais j'ai d'abord besoin de comprendre les maths derrière elle. Quant à l'autre partie de votre question, oui, juste la surface de la sphère.
Juste Google pour 'Trilateration': en.wikipedia.org/wiki/trilateration