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

Question

Я ищу алгоритм для нахождения общих точек пересечения между 3 сферами.

Обнажив полный алгоритм, было бы очень полезно подробное / подробное описание математики.

Это единственный полезный ресурс, который я нашел до сих пор: http://mathforum.org/library/drmath/view/63138.html

Но ни один из описанных методов не является достаточно подробным, чтобы я мог написать алгоритм.

Я бы предпочел чисто алгебраический метод, описанный во втором посте, но то, что всегда работает.

Answer 1

Вероятно, проще, чем построение трехмерных кругов, потому что работа в основном на линиях и плоскостях

Для каждой пары сфер получите уравнение плоскости, содержащей их пересеченную окружность, вычитая уравнения сфер (каждая из форм X ^ 2 + Y ^ 2 + Z ^ 2 + a X + b Y + 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 + t U и H-t U

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

Answer 2

Вот ответ на 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                       

Answer 3

Рассмотрим пересечение двух сфер. Для наглядности рассмотрим отрезок 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) = cos t + i sin t

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

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

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

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

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