Учитывая N точек в трехмерном пространстве, как найти самую маленькую сферу, которая содержит эти N точек?
Учитывая N точек в трехмерном пространстве, как найти самую маленькую сферу, которая содержит эти N точек?
3 ответа
Эта проблема называется проблемой минимального вмещающего шара. (Google этот термин, чтобы найти учебники и документы по нему).
Вот одна из реализаций: http://www.inf.ethz.ch/personal/gaertner/miniball.html в C++.
Его 2-й случай (найдите круг, чтобы заключить все точки на плоскости) - классический пример, преподанный в курсе вычислительной геометрии. 3D - это просто простое расширение 2D-кейса.
Один алгоритм для этой проблемы - инкрементный стиль. Вы начинаете с 4 очков, и они фиксируют сферу, а когда вы добавляете 5-ю точку, есть два случая:
дело в сфере. не нужно обновлять.
вне точки. В этом случае вам необходимо обновить свою сферу. Тогда нетривиальным свойством является то, что эта новая точка должна быть в вашей новой сфере!
Исходя из вышеизложенного, ваша проблема становится меньше. Прочитайте раздел 4.7 этой книги. Это также доступно в книге Google.
Задача сводится к поиску выпуклой оболочки из N точек. Большинство алгоритмов выпуклой оболочки, таких как разделяй и властвуй, упаковка подарков или алгоритмы Джарвиса Марча и Тимоти Чана, могут быть применены и к 3D. Из всех этих алгоритмов алгоритм Тимоти Чана является лучшим из известных алгоритмов.
Есть несколько алгоритмов и реализаций для этой проблемы.
Для 2D и 3D реализация Gärtner, вероятно, самая быстрая.
Для более высоких измерений (скажем, до 10000) взгляните на https://github.com/hbf/miniball, в котором реализованы алгоритмы Гертнера, Кутца и Фишера (примечание: я один из -авторы).
Для очень, очень больших размеров алгоритмы набора (аппроксимации) ядра будут быстрее.
Примечание: Если вы ищете алгоритм для вычисления наименьшей охватывающей сферы сфер, вы найдете реализацию C++ в Библиотеке алгоритмов вычислительной геометрии (CGAL). (Вам не нужно использовать весь CGAL; просто извлеките требуемый заголовок и исходные файлы.)