uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel

Как пересчитать плотно упакованные шары из центра по спирали?

Мне нужно разметить полотно из центра к окраине расставляя метки с равной плотностью.
Показано. что идеальная расстановка это соты, бильярдная пирамида.
Требования к метке M
  • Шар[М], где каждый шар помечен ровно одной меткой и каждой метке соответствует ровно один шар.
  • Критерий удаления от центра. Если М>К, то (Шар[М + 1] - Шар[1]) >= (Шар[К] - Шар[1])
  • Метод построения. Рекурсивное преобразование Шар[М + 1] = Индуктор(Шар[М]) сложности О(1), в идеале линейное. Если это не решено, то Шар[M] = Конструктор(М)

Я видел алгоритмы для спирали Архимеда и логарифмической. В логарифмической проще построить рекурсивный шаг потому, что проходя равную длину спирали мы всегда удаляемся от центра на равное расстояние. Обе спирали не дают гарантированно равноплотную упаковку. Можно построить ломаную спираль по клеткам координатной решетки, но плотность упаковки будет меньше сотовой конструкции. Может быть решен алгоритм для сотовой упаковки?

P.S. По рекомендации ресурса переношу уточнения из комментариев в тело вопроса
Примерно вот так habrastorage.org/files/bac/d16/317/bacd163174dc4d8...
Я пытаюсь реализовать алгоритм www.wordle.net описанный здесь static.mrfeinberg.com/bv_ch03.pdf и мне нужно частное решение задачи https://ru.wikipedia.org/wiki/Задача_об_упаковке_в...
  • Вопрос задан
  • 2423 просмотра
Пригласить эксперта
Ваш ответ на вопрос

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

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