Trouver des points d'intersection entre 3 sphères

Je suis à la recherche d'un algorithme pour trouver le points d'intersection entre les 3 sphères.

Mise à nu complète de l'algorithme, un examen détaillé/description des mathématiques serait grandement utile.

C'est la seule ressource utile que j'ai trouvé jusqu'à présent:
http://mathforum.org/library/drmath/view/63138.html

Mais ni la méthode décrite il y a suffisamment détaillée pour moi d'écrire un algorithme sur.

Je préfère la version purement algébrique de la méthode décrite dans le deuxième post, mais ce que jamais fonctionne.

5

Considérer l'intersection de deux sphères. Pour le visualiser, d'examiner la 3D segment de la ligne N qui relie les deux centres des sphères. Envisager cette section

le texte d'alt http://gara.matt.googlepages.com/circles.PNG

où la ligne rouge est la section transversale de l'avion avec la normale N. Par symétrie, vous pouvez faire tourner cette section à partir de n'importe quel angle, et la ligne rouge en segments de longueur ne peut pas le changer. Cela signifie que la courbe résultante de l'intersection de deux sphères de la vie est un cercle, et doit se situer dans un avion avec la normale N.

Cela étant dit, permet de se rendre sur la recherche de l'intersection. Tout d'abord, nous voulons décrire le cercle de l'intersection de deux sphères. Vous ne peut pas le faire avec 1 équation d'un cercle en 3D est essentiellement une courbe en 3D et vous ne pouvez pas décrire des courbes en 3D par 1 eq.

Considérer l'image
le texte d'alt http://gara.matt.googlepages.com/circlesa.PNG

notons P le point d'intersection de la ligne bleue et la ligne rouge. Soit h la longueur du segment de ligne le long de la ligne rouge de point P à la hausse. Admettons que la distance entre les deux centres-être marqué par la d. Soit x la distance entre le petit cercle de centre à la P. nous devons Alors avoir
```
x^2 +h^2 = r1^2
(d-x)^2 +h^2 = r2^2
==> h = sqrt(r1^2 - 1/d^2*(r1^2-r2^2+d^2)^2)
```
c'est à dire que vous pouvez résoudre pour h, qui est le rayon du cercle d'intersection. Vous pouvez trouver le point de centre C du cercle de x, le long de la ligne qui joint les 2 centres des cercles.

Ensuite, vous pouvez décrire complètement le cercle (X,C,U,V sont tous des vecteurs)
```
X = C + (h * cos t) U + (h * sin t) V for t in [0,2*PI)
```
où U et V sont des vecteurs perpendiculaires qui se trouvent dans un avion avec la normale N.

La dernière partie est la plus facile. Il ne reste plus qu'à trouver l'intersection de ce cercle avec la finale de la sphère. C'est tout simplement un bouchon et chug des équations (plug-in pour x,y,z dans la dernière équation paramétrique formes de x,y,z pour le cercle en termes de t et de résoudre pour t.)

edit ---

L'équation que vous obtiendrez, c'est en fait assez moche, vous aurez tout un tas de sinus et de cosinus est égal à quelque chose. Pour résoudre ce problème, vous pouvez le faire de 2 façons:
1. écrire le cosinus et le sinus en termes de exponentielles en utilisant l'égalité
  
  e^(il) = cos t + i sin t
  
  puis de les regrouper tous les e^(il) et vous devriez obtenir une équation du second degré des équations de e^(il)'s
  que vous peut résoudre à l'aide de la formule quadratique, puis résoudre pour t. Cela va vous donner la solution exacte. Cette méthode sera effectivement vous dire exactement si une solution existe, deux existe pas ou existe en fonction du nombre de points à partir de l'équation de la méthode sont réels.
2. utiliser la méthode de newton pour résoudre de t, cette méthode n'est pas exacte, mais son calcul beaucoup plus facile à comprendre, et il fonctionne très bien pour ce cas.
8

Probablement plus facile que la construction en 3D des cercles, car le travail, principalement sur les lignes et les plans:

Pour chaque paire de sphères, d'obtenir l'équation du plan contenant leur intersection du cercle, en soustrayant les domaines des équations (chacune de la forme X^2+Y^2+Z^2+aX+bY+c*Z+d=0). Ensuite, vous disposez de trois avions P12 P23 P31.

Ces avions ont une commune de la ligne L, perpendiculaire au plan Q par les trois centres des sphères. Les deux points que vous recherchez sont sur cette ligne. La moyenne des points est l'intersection H entre L et Q.

Pour mettre en œuvre cette:
- calculer les équations de P12 P23 P32 (différence des équations de la sphère)
- calculer l'équation de Q (résoudre un système linéaire, ou calculer un produit vectoriel)
- calculer les coordonnées du point H, intersection de ces quatre avions. (résoudre un système linéaire)
- obtenir le vecteur normal U de Q à partir de son équation (normaliser un vecteur)
- calculer la distance entre H et une solution X: t^2=R1^2-HC1^2, (C1,R1) sont le centre et le rayon de la première sphère.
- solutions sont H+tU et H-tU
Un Cabri 3D de construction montrant les différents plans et ligne L
6

Fondamentalement, vous devez le faire en 3 étapes. Disons que vous avez trois sphères, S1, S2, et S3.
1. C12 est le cercle créé par l'intersection de S1 et S2.
2. C23 est le cercle créé par l'intersection de S2 et S3.
3. P1, P2, sont les points d'intersection de C12 et C13.
Le seul vraiment dur ici, c'est la sphère d'intersection, et heureusement Mathworld a réglé assez bien. En fait, Mathworld a aussi le solution pour le cercle des intersections.

À partir de cette information, vous devriez être en mesure de créer un algorithme.

Ici est une réponse en Python j'ai juste porté à partir de l'article de Wikipédia. Il n'est pas nécessaire pour un algorithme; il n'y est une solution de la forme finie.

import numpy                                             
from numpy import sqrt, dot, cross                       
from numpy.linalg import norm                            

# Find the intersection of three spheres                 
# P1,P2,P3 are the centers, r1,r2,r3 are the radii       
# Implementaton based on Wikipedia Trilateration article.                              
def trilaterate(P1,P2,P3,r1,r2,r3):                      
    temp1 = P2-P1                                        
    e_x = temp1/norm(temp1)                              
    temp2 = P3-P1                                        
    i = dot(e_x,temp2)                                   
    temp3 = temp2 - i*e_x                                
    e_y = temp3/norm(temp3)                              
    e_z = cross(e_x,e_y)                                 
    d = norm(P2-P1)                                      
    j = dot(e_y,temp2)                                   
    x = (r1*r1 - r2*r2 + d*d) /(2*d)                    
    y = (r1*r1 - r3*r3 -2*i*x + i*i + j*j) /(2*j)       
    temp4 = r1*r1 - x*x - y*y                            
    if temp4<0:                                          
        raise Exception("The three spheres do not intersect!");
    z = sqrt(temp4)                                      
    p_12_a = P1 + x*e_x + y*e_y + z*e_z                  
    p_12_b = P1 + x*e_x + y*e_y - z*e_z                  
    return p_12_a,p_12_b

3

après recherche sur le web c'est l'un des premiers hits, donc je vous poste le plus propre et facile solution que j'ai trouvé après quelques heures de recherche ici: Trilatération

Ce site wiki contient une description complète d'un rapide et facile à comprendre vecteur d'approche, de sorte que l'on peut coder avec peu d'effort.
1

Voici une autre interprétation de l'image d'Eric posté ci-dessus:

Soit H le plan engendré par les centres des trois sphères. Laissez C1,C2,C3 être l'intersection des sphères avec H, C1,C2,C3 sont des cercles. Laissez-Lij être la ligne reliant les deux points d'intersection de Ci et Cj, puis les trois lignes L12,L23,L13 se coupent en un point P. soit M la ligne orthogonale de H en P, alors vos deux points d'intersection se trouvent sur la ligne M; de là, vous avez juste besoin d'intersection de M avec l'une des sphères.

Vous devez vous connecter pour publier un commentaire.