Я ищу алгоритм, к которому кто-то имеет доступ, который вычислит наименьшую ограничивающую сферу, которая охватывает набор других ограничивающих сфер. Некоторое время я думал об этом и придумал некоторые первоначальные решения, но я не думаю, что они обязательно являются самыми точными или наименее вычислительно дорогими (самыми быстрыми).
Первая мысль
Мое первое решение - самое простое наивное, которое состоит в том, чтобы усреднить центры сфер, чтобы получить центральную точку, а затем вычислить максимальное расстояние от вычисленного центра до центра каждой сферы плюс ее радиус в качестве радиуса. Таким образом, псевдокод выглядит так:
function containing_sphere_1(spheres)
center = sum(spheres.center) / count(spheres)
radius = max(distance(center, spheres.center) + radius)
return Sphere(center, radius)
end
Однако у меня возникает ощущение, что это не так уж и дешево, и не совсем точно, поскольку полученная сфера может быть намного больше, чем нужно.
Вторая мысль
Моя вторая мысль - использовать итерационный алгоритм для вычисления минимальной ограничивающей сферы. Он вычисляется путем последовательного тестирования другой сферы: если проверенная сфера находится внутри границ, то ничего не делается, в противном случае новая ограничивающая сфера вычисляется из двух доступных сфер. Новая ограничивающая сфера имеет центр, который находится на полпути между вектором между двумя центрами, если он был расширен до поверхностей сфер, а радиус равен половине длины этой линии (от нового центра до поверхности любой сферы).
function containing_sphere_2(spheres)
bounds = first(spheres)
for each sphere in spheres
if bounds does not contain sphere
line = vector(bounds.center, sphere.center)
extend(line, bounds.radius)
extend(line, sphere.radius)
center = midpoint(line)
radius = length(line) / 2
bounds = Sphere(center, radius)
end
end
return bounds
end
Первоначально я думал, что это будет путь, так как он итеративный и кажется достаточно логически последовательным, однако после некоторого прочтения, в частности, статьи «Самые маленькие вмещающие диски (шарики и эллипсоиды)» Эмо Вельцля I ' Я не так уверен.
Алгоритм Вельцля
Насколько я понимаю, в основе этого алгоритма лежит то, что минимальная ограничивающая сфера над набором точек в 3-х измерениях может быть определена не более чем в 4 точках (которые находятся на поверхности охватывающей сферы). Таким образом, алгоритм использует итеративный подход, выбирая 4 точки, а затем проверяя другие точки, чтобы увидеть, находятся ли они внутри или нет, если они не являются новой ограничивающей сферой, построенной с использованием новой точки.
Теперь алгоритм имеет дело строго с точками, но я думаю, что его можно применять для работы со сферами, главное усложнение которых заключается в увеличении радиуса при построении окружающей сферы.
Вернуться к вопросу
Так что же является «лучшим», как и наименее затратным в вычислительном отношении, алгоритмом, который создает минимальную ограничивающую сферу для набора заданных сфер?
Является ли один из них, который я описал, здесь ответом? Какой-то псевдокод или алгоритм будут великолепны.