трехмерное пространство, найти радиус Опции

[bairt]

В трехмерном пространстве задано N шаров. Найти шар минимального радиуса, охватывающий все заданные

[Lapp]

Выполняю обещанное - публикую анонсированное мной в одном из предыдущих постов решение задачи. То есть не решение, а только алгоритм в самом общем виде. Более того, в нем присутствуют нерешенные математические выражения. Программый код к этой задаче я стал бы писать только под дулом банкомата, и желательно как можно более крупного калибра .

Сначала извинюсь перед Бравым Генералом: я сомневался в легкой масштабируемости этой задачи с двумерного случая на трехмерный, но потом убедился, что суть действительно не меняется, хотя математика усложняется.

Рассмотрим двумерный случай: ищем окружность минимального радиуса, охватывающую заданный конечный набор кругов. Проведем небольшое исследование, по традиции начинаемое словами: предположим, что задача решена, и минимальная охватывающая окружность построена...

В этом месте небольшое лирическое отступление. Два утверждения:

1. На плоскости в общем случае можно провести одну и только одну окружность, касающуюся трех данных (окружность Апполония, ОА) так, чтобы все три данные оказались внутри нее (в дальнейшем, кроме оговоренного, под "касанием" я буду понимать именно такое касание). Иногда такую окружность провести невозможно (вот пример: О о О ), но такие случаи нас волновать не будут, так как они охватываются пунктом 2.

2. Если даны две окружности, то можно провести много окружностей, касающихся их, но только одна при этом будет охватывать их обе с минимальным радиусом ее центр лежит на отрезке, соединяющем центры.

... Охватывающий круг, будучи уже построен, должен либо а) касаться трех (или больше) кругов из данного набора; либо б) касаться только двух, имея при этом минимальный возможный радиус. Первое довольно очевидно, а во втором убедиться можно, представив себе круг неминимального радиуса, касающийся лишь двух кругов - очевидно, его можно уменьшить.

Итак, алгоритм решения состоит в следующем.
1. Провести полный перебор всех троек кругов. На каждую тройку натягивать касающуся их окружность , после чего перебором по всем оставшимся кругам смотреть, попадают ли они внутрь нее. Из всех таких окружностей ищем окружность с минимальным радиусом. (Для оптимизации вычислений эти две проверки лучше переставить местами: сначала проверять радиус на минимальность - но это лирика).

2. Найти два максимально отстоящие (дальними точками) круга, натянуть на них минимальную окружность и проверить, охватываются ли все остальные круги этой окружностью. Если да, то сравнить с радиусом, полученном в п.1 и выбрать минимальный.

По сути, тут два решения: одно - klem4'овское, только с добавленной проверкой на включение, второе - Бравого Генерала, с тем же самым дополнением.

Все! Казалось бы...

Но действительно ли все? Теоретически - да. А практически..
Выполнить п.2 сложности не представляет - klem4 уже сделал это. А вот п.1.. Хотя ОА принципиально и находима - этого достаточно для математика, для программера этого мало. Надо указать конкретный способ ее найти. Именно это и тормозило меня с самого начала: хотя описанные выше два пункта алгоритма нащупать было несложно, практический способ постороения ОА мне не давался. В указанной ссылке (см. мои предыдущие посты) способ построения геометрический, реализовать его в коде довольно сложно с моей точки зрения. Поэтому я продолжал думать.. Довольно долго все равно все мои усилия были вокруг простой геометрии типа циркулем и линейкой, хотя я понимал, что без инверсии тут не обойтись. В конце концов я на нее решился.

Все оказалось не так уж и страшно
Преобразование инверсии, как известно, переводит окружность в окружность, при этом сохраняя касание. Да, конечно - прямо то, что нужно! Только зачем? Зачем переводить окружности в другие? чем другие лучше?

А вот чем. Когда я написал уравнения, оказалось, что возможно провести одну инверсию, которая переведет три заданных окружности в три окружности одного заданного диаметра! Внизу, если останется время, приведу подтвеждающие выкладки.

Итак, общее правило такое:

1. По трем выбранным кругам (центры и радиусы) находим параметры (центр и радиус) того самого преобразования инверсии, которое переводит эти три окружности в три одинаковые.

2. Произвести инверсию.

3. Построить окружность, касающуюся трех полученных образов. Для этого просто строим окружность, проходящую через их центры, а потом увеличиваем ее радиус на величину радиуса образов.

4. Проводим обратную инверсию (то есть вторично применяем ее). Полученный образ построенной в п.3 окружности - это искомая кружность, касающаяся трех данных.

Просто? Не совсем. Но и это еще не все. Необходимо одно уточнение..
Дело в том, что, переводя окружность в окружность, инверсия не переводит центр в центр. Поэтому реально нужно инвертировать две точки окружности, лежащие на луче, проходящем из центра инверсии через центр инвертируемой окружности, а потом взять середину отрезка между ними - это будет центр инвертированной окружности.

Вот теперь, кажется, все..
Ах, да! не все.. Осталось добавить, что, как показывают выкладки, инверсия применяется в трехмерном случае (теперь уже к четырем сферам) вполне аналогично, хотя вычисления усложняются. Далее, в 3D придется рассматривать не два случая, а три:
1. Касание четырех шаров.
2. Минимальное касание трех шаров.
3. Минимальное касание двух шаров.
Строгости ради, сюда (а также выше) надо добавить еще и случай, когда одна из данных сфер уже охватывает все остальные, но он настолько тривиален, что лень было упоминать. Хотя в программном продукте он должен быть учтен, разумеется.

Теперь совесм все!!
Ну, как вам решеньеце? Мне почему-то кажется, что с набором из сотни шаров современный Р4 за пару часов справится. Но о тысяче не стоит и говорить.. Хотя, простор для оптимизации тут немеряный..

Мужики (дамы так и не присоединились к обсуждению), не судите строго - я выложу вычисления on request - ладно? И так уже больше получаса пишу..

Всем спасибо за внимание! Жду критики (или опровержений )


P.S.
Перечитал - и обнаружил в своих рассуждениях ошибку, которая может иметь принципиальное значение. Или, по крайней мере, еще усложнит алгоритм..
Кто еще заметил?