Поиск точек пересечения между 3 сферами

Ответ 1

Рассмотрим пересечение двух сфер. Для наглядности рассмотрим отрезок N трехмерной линии, соединяющий два центра сфер. Рассмотрим это сечение

_{(источник: googlepages.com)}

где красная линия - это поперечное сечение плоскости с нормальной N. Симметрично, вы можете повернуть это поперечное сечение на любой угол, и длина отрезков красной линии не может измениться. Это означает, что полученная кривая пересечения двух сфер является окружностью и должна лежать в плоскости с нормальной N.

При этом давайте перейдем к поиску перекрестка. Сначала мы хотим описать результирующий круг пересечения двух сфер. Вы не можете сделать это с 1 уравнением, круг в 3D по сути является кривой в 3D, и вы не можете описать кривые в 3D на 1 экв.

Посмотрите на картинку
_{(источник: googlepages.com)}

пусть P будет точкой пересечения синей и красной линии. Пусть h - длина отрезка вдоль красной линии от точки P вверх. Пусть расстояние между двумя центрами обозначено через d. Пусть x - расстояние от центра малого круга до P. Тогда мы должны иметь

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)

то есть вы можете решить для h, который является радиусом круга пересечения. Вы можете найти центральную точку C круга из x вдоль линии N, которая соединяет 2 центра круга.

Тогда вы можете полностью описать круг как (X, C, U, V все векторные)

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

где U и V - перпендикулярные векторы, лежащие в плоскости с нормалью N.

Последняя часть самая простая. Осталось только найти пересечение этого круга с конечной сферой. Это просто пробка из уравнений (вставьте для x, y, z в последнем уравнении параметрические формы x, y, z для круга в терминах t и решите для t.)

редактировать ---

Уравнение, которое вы получите, на самом деле довольно уродливо, у вас будет целая куча синусов и косинусов, равных чему-то. Для решения этой проблемы вы можете сделать это двумя способами:

1. написать косинус и синус в терминах экспонент, используя равенство

   е ^ (это) = потому что + я грешу

   затем сгруппируйте все члены e ^ (it), и вы должны получить квадратные уравнения e ^ (it), которые вы можете решить для использования квадратной формулы, а затем решить для t. Это даст вам точное решение. Этот метод фактически скажет вам точно, существует ли решение, существует два или одно существует в зависимости от того, сколько точек из квадратичного метода являются действительными.

2. используйте метод Ньютона, чтобы решить для t, этот метод не точен, но его вычислительно намного легче понять, и он будет очень хорошо работать в этом случае.

Ответ 2

Наверное, проще, чем создавать 3D-круги, поскольку они работают в основном на линиях и плоскостях:

Для каждой пары сфер получим уравнение плоскости, содержащей их окружность пересечения, вычитая уравнения сфер (каждый из форм X ^ 2 + Y ^ 2 + Z ^ 2 + aX + bY + c * Z + d = 0). Тогда у вас будет три плоскости P12 P23 P31.

Эти плоскости имеют общую линию L, перпендикулярную плоскости Q тремя центрами сфер. Две точки, которые вы ищете, находятся на этой линии. Середина точек - это пересечение H между L и Q.

Чтобы реализовать это:

• вычислить уравнения P12 P23 P32 (разность сферных уравнений)
• вычислить уравнение Q (решить линейную систему или вычислить кросс-произведение)
• вычислить координаты пересечения точки H этих четырех плоскостей. (решить линейную систему)
• получить нормальный вектор U в Q из его уравнения (нормализовать вектор)
• вычислить расстояние t между H и решением X: t ^ 2 = R1 ^ 2-HC1 ^ 2, (C1, R1) - центр и радиус первой сферы.
• решения H + tU и H-tU

Конструкция Cabri 3D, показывающая различные плоскости и линию L

Ответ 3

В принципе, вам нужно сделать это за 3 шага. Скажем, у вас есть три сферы: S1, S2 и S3.

• C12 - это круг, созданный пересечением S1 и S2.
• C23 - это круг, созданный пересечением S2 и S3.
• P1, P2, являются точками пересечения C12 и C13.

Единственная действительно сложная часть здесь - пересечение сферы, и, к счастью, Mathworld так хорошо решает, Фактически, Mathworld также имеет решение для пересечений круга.

Из этой информации вы сможете создать алгоритм.

Ответ 4

Вот ответ на Python, который я просто портировал из статьи в Википедии. Алгоритм не нужен; существует замкнутое решение формы.

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                       

Ответ 5

после поиска в Интернете это одно из первых хитов, поэтому я отправляю самое чистое и простое решение, которое я нашел после нескольких часов исследований здесь: Trilateration

Этот сайт вики содержит полное описание быстрого и понятного векторного подхода, поэтому его можно легко скомпенсировать.

Ответ 6

Вот еще одна интерпретация картины, которую Эрик опубликовал выше:

Пусть H - плоскость, натянутая на центры трех сфер. Пусть C1, C2, C3 - пересечения сфер с H, тогда C1, C2, C3 - круги. Пусть Lij - линия, соединяющая две точки пересечения Ci и Cj, то три линии L12, L23, L13 пересекаются в одной точке P. Пусть M - прямая, ортогональная H через P, то ваши две точки пересечения лежат на строка M; поэтому вам просто нужно пересечь M с любой из сфер.