Encontrar puntos de intersección entre 3 esferas

Question

Estoy buscando un algoritmo para encontrar los puntos de intersección comunes entre 3 esferas.

Presentando un algoritmo completo, una descripción minuciosa/detallada de los cálculos sería de gran ayuda.

Este es el único recurso útil que he encontrado hasta el momento: http://mathforum.org/library/drmath/view/63138.html

Pero ninguno de los métodos descritos no es lo suficientemente detallada para mí escribir un algoritmo sucesivamente.

Preferiría el método puramente algebraico descrito en la segunda publicación, pero lo que funcione.

Answer 1

Considere la intersección de dos esferas. Para visualizarlo, considere el segmento de línea 3D N que conecta los dos centros de las esferas. Considere esta sección transversal

alt text http://gara.matt.googlepages.com/circles.PNG

donde la línea roja es la sección transversal del plano con normal N. Por simetría, puede girar esta sección transversal desde cualquier ángulo, y la longitud de los segmentos de línea roja puede Sin cambio. Esto significa que la curva resultante de la intersección de dos esferas es un círculo, y debe estar en un plano con N. normal

Dicho esto, vamos a encontrar la intersección. Primero, queremos describir el círculo resultante de la intersección de dos esferas. Usted no puede hacer esto con 1 ecuación, un círculo en 3D es esencialmente una curva en 3D y no puede describir las curvas en 3D en 1 eq.

considerar el cuadro alt text http://gara.matt.googlepages.com/circlesa.PNG

Sea P el punto de intersección de la línea azul y rojo. Deje h ser la longitud del segmento de línea a lo largo de la línea roja desde el punto P hacia arriba. Deje que la distancia entre los dos centros sea denotada por d. Sea x la distancia desde el centro del círculo pequeño a P. Entonces tenemos que tener

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) 

es decir, se puede resolver para h, que es el radio del círculo de intersección. Puedes encontrar el punto central C del círculo desde x, a lo largo de la línea N que une los 2 centros del círculo.

Entonces se puede describir completamente el círculo como (X, C, U, V son todos vector)

X = C + (h * cos t) U + (h * sin t) V for t in [0,2*PI) 

donde U y V son vectores perpendiculares que se encuentran en un plano con normal N.

La última parte es la más fácil. Solo resta encontrar la intersección de este círculo con la esfera final. Esto es simplemente un complemento y chug de las ecuaciones (inserte para x, y, z en la última ecuación las formas paramétricas de x, y, z para el círculo en términos de t y resuelva para t)

editar ---

La ecuación que obtendrá es bastante fea, tendrá un montón de seno y coseno igual a algo. Para solucionar esto se puede hacer de 2 maneras:

1. escribir las ay seno del coseno en términos de exponenciales utilizando la igualdad

   e^(es) = cos t + i sen t

   entonces agrupe todos los términos e^(it) y obtendrá una ecuación cuadrática de e^(it) que puede resolver utilizando la fórmula cuadrática, luego resuelva para t. Esto te dará la solución exacta.Este método realmente le dirá exactamente si existe una solución, existen dos o existe uno dependiendo de cuántos de los puntos del método cuadrático son reales.

2. use el método de newton para resolver t, este método no es exacto pero es mucho más fácil de entender desde el punto de vista computacional, y funcionará muy bien para este caso.

Answer 2

Básicamente, debe hacer esto en 3 pasos. Digamos que tienes tres esferas, S1, S2 y S3.

1. C12 es el círculo creado por la intersección de S1 y S2.
2. C23 es el círculo creado por la intersección de S2 y S3.
3. P1, P2, son los puntos de intersección de C12 y C13.

La única parte realmente difícil aquí es la intersección de la esfera, y afortunadamente Mathworld has that solved pretty well. De hecho, Mathworld también tiene el solution to the circle intersections.

A partir de esta información, debería poder crear un algoritmo.

Answer 3

Probablemente más fácil que la construcción de los círculos en 3D, porque trabajar principalmente en líneas y planos:

Para cada par de esferas, obtener la ecuación del plano que contiene su círculo intersección, restando las ecuaciones esferas (cada uno de la forma X^2 + Y^2 + Z^2 + a X + b Y + c * Z + d = 0). Entonces tendrá tres aviones P12 P23 P31.

Estos aviones tienen una línea común L, perpendicular al plano Q por los tres centros de las esferas. Los dos puntos que está buscando están en esta línea. El medio de los puntos es la intersección H entre L y Q.

Para implementar esta:

• calcular las ecuaciones de P32 P12 P23 (diferencia de ecuaciones esfera)
• calcular la ecuación de Q (resolver un sistema lineal o calcular un producto cruzado)
• calcular las coordenadas de la intersección del punto H de estos cuatro planos. (Resolver un sistema lineal)
• obtener el vector normal de U para Q partir de su ecuación (normalizar un vector)
• calcular la distancia t entre H y una solución X: t^2 = R1^2-HC1^2, (C1, R1) son el centro y el radio de la primera esfera.
• soluciones son H + t U y H-t U

construcción A Cabri 3D que muestra los diversos planos y la línea L

Answer 4

Aquí es otra interpretación de la imagen que Eric ha escrito más arriba:

Sea H el plano generado por los centros de las tres esferas. Deje C1, C2, C3 ser las intersecciones de las esferas con H, entonces C1, C2, C3 son círculos. Deje que Lij sea la línea que conecta los dos puntos de intersección de Ci y Cj, luego las tres líneas L12, L23, L13 se cruzan en un punto P. Sea M la línea ortogonal a H a P, entonces sus dos puntos de intersección se encuentran en el línea M; por lo tanto, solo necesitas intersecar M con cualquiera de las esferas.

Answer 5

después de buscar en la web este es uno de los primeros éxitos, así que estoy publicar la solución más limpia y sencilla que encontré después de algunas horas de investigación aquí: Trilateration

Este sitio wiki contiene una descripción completa de un ayuno y enfoque vectorial fácil de entender, por lo que uno puede codificarlo con poco esfuerzo.

Answer 6

Aquí hay una respuesta en Python Acabo de portar desde el artículo de Wikipedia. No hay necesidad de un algoritmo; hay una solución de forma cerrada.

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