Как сгенерировать окружности на сфере, что бы они оптимально перекрывали друг-друга?

Требуется оптимально покрыть окружностями произвольного радиуса (одинакового для одной генерации) сфере, произвольного радиуса. Нужно что-то похожее на покрытие сотами для плоскости.

Испробовал несколько вариантов, но все оказываются не оптимальными, либо я не могу учесть всех дополнительных смещений.
  • Вопрос задан
  • 1102 просмотра
Пригласить эксперта
Ответы на вопрос 3
SHVV
@SHVV
Детерминированный алгоритм построения оптимального разбиения, скорее всего, существует лишь когда центры окружностей лежат в вершинах правильных многогранников, то есть тетраэдра, куба, октаэдра и т.д. Но это условие соблюдается только при определённом соотношении между радиусами сферы и окружностей.

Можно попробовать разбивать на сфере правильные многогранники и подбирать оптимальный многогранник / уровень разбиения под каждый вариант радиуса. Код для построения подобного можно глянуть хоть в том же Three.js.

Ещё можно погуглить "Periodic Centroidal Voronoi Tessellation", этот метод часто используется для схожих задач. В частности, для построения сетки для численного моделирования физических процессов на произвольных поверхностях или в объёме.
Ответ написан
Комментировать
Mrrl
@Mrrl
Заводчик кардиганов
Это известная проблема. Пока её решили до 10 кругов и ещё для некоторых чётных значений. Впрочем, всё это сведения 25-летней давности, свежих результатов найти не удаётся. Вот статья, где разбирается построение для 11 кругов (правда, я её не читал, и не знаю, есть ли там окончательное решение для этого случая):
https://eudml.org/doc/141375
Или у вас задача - "дан радиус сферы и радиус круга, найти минимальное число кругов"? Или можно задать примерный радиус (или примерное число кругов) и найти какое-нибудь решение, близкое к оптимальному, для этого случая?
В общем, сейчас задача упирается в вопрос "а зачем?". Если нужно точное решение для написания докторской диссертации - то решайте. Если есть какая-нибудь практическая цель - напишите, какая, и будем искать реалистичные приближения.

UPD. В общем, берёте икосаэдр, и каждую грань делите на маленькие правильные треугольники. Вершины этих треугольников и дадут центры кругов. Радиус придётся считать исходя из картинки вблизи вершины икосаэдра - там треугольники заметно искажаются. Возможно, радиальное расстояние между точками там придётся слегка уменьшить.
Ответ написан
@bromzh
Drugs-driven development
Раз пересечения допустимы, то наверное надо построить что-то типа такой штуки en.wikipedia.org/wiki/Geodesic_dome, ну т.е. разбить сферу на правильные многоугольники (скорее всего 5-ти угольники), пускай и не одинакового размера. Главное, чтобы расстояние от центра многоугольника до вершины было не больше заданного радиуса для "кругов". Потом для каждого многоугольника найти центр и провести луч от центра сферы, проходящий через центр этого многоугольника и найти точку пересечения этого луча с поверхностью сферы. Это и будет центр "круга". Важно понимать, то это уже не евклидова геометрия, поэтому некоторые приёмы работать в таком пространстве не будут.
Правда не знаю, будет ли это оптимальным размещением. Возможно даже доказательства его оптимальности ещё нет.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы