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

Question

[Gilberg]

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

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

Comments

[bromzh]

Какие условия покрытия? Могут круги пересекаться более чем в 1-й точке?

[Oxoron]

Уточните вопрос. Я могу провести диаметральную окружность, она разделит сферу на две полусферы. Это будет идеальным покрытием?

[bromzh]

Oxoron: Наверное имеется ввиду, что есть сфера радиуса r1 и некое число r2 < r1. Нужно расположить на сфере несколько "кругов" радиуса r2, так чтобы площадь покрытия была максимальной (если круги не могут пересекаться более чем в 1-й точке). Или же покрыть такими "кругами" всю площадь, при этом количество "кругов" должно быть минимальным (если "круги" могут иметь более 1-й общей точки).

[Gilberg]

bromzh: Могут, но оптимальным решением будет такой же алгоритм, как расположение "сот" на плоскости.
Oxoron: В конечном результате должна получиться фигура, при некоторых r1 и r2 (и сохранении условия r2 < r1, как правильно заметил @bromzh) похожая на футбольный мяч (усечённый икосаэдр).

Answer 1

[SHVV]

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

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

Ещё можно погуглить "Periodic Centroidal Voronoi Tessellation", этот метод часто используется для схожих задач. В частности, для построения сетки для численного моделирования физических процессов на произвольных поверхностях или в объёме.

Answer 2

[Mrrl]

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

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

Comments

[Gilberg]

>> В общем, сейчас задача упирается в вопрос "а зачем?".
Задачу можно сформулировать примерно так: "Разбить поверхность планеты(не обязательно Земли) (имеющей форму _шара_) на точки интереса, представляющие из круглые области с минимальным перекрытием друг друга."

[Mrrl]

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

[Gilberg]

Mrrl: Если я правильно Вас понял, то радиус кругов будет зависеть от радиуса шара, что не соответствует исходным данным: т.е, и шар, и круги произвольного диаметра, соответственно чем больше шар(при том же радиусе круга), тем больше кругов...

[Mrrl]

Gilberg: То есть, радиус областей у вас задан строго, и возможности заменить его на чуть меньший нет? Тогда задача практически безнадёжна.

[Mrrl]

Gilberg: Вариант с икосаэдром позволяет строить конструкции для радиуса кругов приблизительно R/(2*n), где R - радиус сферы, а n - натуральное. Таких кругов будет 10*n^2+2 (случай n=1 соответствует граням додекаэдра). Если строить перекошенные треугольные сетки (на икосаэдре они будут состоять из правильных треугольников, но рёбра не обязательно будут параллельны рёбрам икосаэдра), то можно получить круги радиусом около R/2/sqrt(n^2+m*n+m^2), где n,m - целые неотрицательные, не равные нулю одновременно. Кругов будет 10*(n^2+m*n+m^2)+2 (случай m=n=1 соответствует усечённому икосаэдру).

[Gilberg]

Mrrl: Соотношение радиусов в одном их случаев 1/1274

[Mrrl]

Gilberg: 5 километров? Тогда ребро икосаэдра придётся делить примерно на 815 частей (может быть, чуть больше). Число кругов будет около 6.7 миллионов. Для определения оптимальной конфигурации придётся строить, оптимизировать и просчитывать решётки разных размеров, пока не найдётся подходящая. Или не оптимизировать. Самые большие описанные конусы будут либо около вершины икосаэдра, либо в середине ребра, либо в центре грани. Надо будет проверить только их.

Answer 3

[bromzh]

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

Comments

[Gilberg]

Именно к этому я и пришел в своих "поисках", но запнулся на "разбить сферу на правильные многоугольники", т.е. фактически этот алгоритм и будет являться решением этого вопроса.

[SHVV]

Gilberg: Это же сферизованый Икосаэдр. Добавил в свой ответ ссылку на построение Polyhedron-а.

[SHVV]

Только там не совсем правильные многоугольники. Они только в плоскости правильные, а при натягивании на сферу искажаются.