Я ищу алгоритм для поиска общих точек пересечения между 3 сферами.
Завершая полный алгоритм, полное/подробное описание математики было бы очень полезно.
Это единственный полезный ресурс, который я нашел до сих пор: http://mathforum.org/library/drmath/view/63138.html
Но ни один из описанных здесь методов не является достаточно подробным для меня, чтобы написать алгоритм.
Я бы предпочел чисто алгебраический метод, описанный во втором посте, но что когда-либо работает.
Рассмотрим пересечение двух сфер. Для наглядности рассмотрим отрезок 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.)
редактировать ---
Уравнение, которое вы получите, на самом деле довольно уродливо, у вас будет целая куча синусов и косинусов, равных чему-то. Для решения этой проблемы вы можете сделать это двумя способами:
написать косинус и синус в терминах экспонент, используя равенство
е ^ (это) = потому что + я грешу
затем сгруппируйте все члены e ^ (it), и вы должны получить квадратные уравнения e ^ (it), которые вы можете решить для использования квадратной формулы, а затем решить для t. Это даст вам точное решение. Этот метод фактически скажет вам точно, существует ли решение, существует два или одно существует в зависимости от того, сколько точек из квадратичного метода являются действительными.
используйте метод Ньютона, чтобы решить для t, этот метод не точен, но его вычислительно намного легче понять, и он будет очень хорошо работать в этом случае.
Наверное, проще, чем создавать 3D-круги, поскольку они работают в основном на линиях и плоскостях:
Для каждой пары сфер получим уравнение плоскости, содержащей их окружность пересечения, вычитая уравнения сфер (каждый из форм X ^ 2 + Y ^ 2 + Z ^ 2 + aX + bY + c * Z + d = 0). Тогда у вас будет три плоскости P12 P23 P31.
Эти плоскости имеют общую линию L, перпендикулярную плоскости Q тремя центрами сфер. Две точки, которые вы ищете, находятся на этой линии. Середина точек - это пересечение H между L и Q.
Чтобы реализовать это:
Конструкция Cabri 3D, показывающая различные плоскости и линию L
В принципе, вам нужно сделать это за 3 шага. Скажем, у вас есть три сферы: S1, S2 и S3.
Единственная действительно сложная часть здесь - пересечение сферы, и, к счастью, Mathworld так хорошо решает, Фактически, Mathworld также имеет решение для пересечений круга.
Из этой информации вы сможете создать алгоритм.
Вот ответ на 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
после поиска в Интернете это одно из первых хитов, поэтому я отправляю самое чистое и простое решение, которое я нашел после нескольких часов исследований здесь: Trilateration
Этот сайт вики содержит полное описание быстрого и понятного векторного подхода, поэтому его можно легко скомпенсировать.
Вот еще одна интерпретация картины, которую Эрик опубликовал выше:
Пусть H - плоскость, натянутая на центры трех сфер. Пусть C1, C2, C3 - пересечения сфер с H, тогда C1, C2, C3 - круги. Пусть Lij - линия, соединяющая две точки пересечения Ci и Cj, то три линии L12, L23, L13 пересекаются в одной точке P. Пусть M - прямая, ортогональная H через P, то ваши две точки пересечения лежат на строка M; поэтому вам просто нужно пересечь M с любой из сфер.