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

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

Испробовал несколько вариантов, но все оказываются не оптимальными, либо я не могу учесть всех дополнительных смещений.
  • Вопрос задан
  • 877 просмотров
Пригласить эксперта
Ответы на вопрос 4
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-ти угольники), пускай и не одинакового размера. Главное, чтобы расстояние от центра многоугольника до вершины было не больше заданного радиуса для "кругов". Потом для каждого многоугольника найти центр и провести луч от центра сферы, проходящий через центр этого многоугольника и найти точку пересечения этого луча с поверхностью сферы. Это и будет центр "круга". Важно понимать, то это уже не евклидова геометрия, поэтому некоторые приёмы работать в таком пространстве не будут.
Правда не знаю, будет ли это оптимальным размещением. Возможно даже доказательства его оптимальности ещё нет.
Ответ написан
prototype_denis
@prototype_denis
Symfony
Ваш случай?
Начальный размер сферы можно взять единичным, радиусы нормализовать и в конце подогнать саму сферу под нужный радиус.
Ответ написан
Ваш ответ на вопрос

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

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