Какой оптимальный алгоритм заполнения canvas'а окружностями?

Question

[Максимка]

Подскажите алгоритм заливки плоскости кружками, желательно с максимальной плотностью. Сломал гугл - ничего даже близко не нашёл. Чтобы вы детальнее понимали о чём речь - посмотрите на таблицы Рабкина для определения дальтонизма, там всё поле плотно залито кружками разного диаметра и цвета.
Отрисовываю это всё, естественно, в canvas'e. Я придумал собственный алгоритм, но он вышел чересчур медленный т.к. уйма итераций расчёта координат происходит в основном потоке. Если бы веб-воркеры имели доступ к canvas элементу, то я бы сюда и не писал - пускай медленно, но координаты бы рассчитывались в отдельном потоке, не заставляя страницу зависать на 15 секунд.

Comments

[copal]

есть библиотека визуализации данных d3.js. В её примерах есть вот такое bl.ocks.org/mbostock/1893974. На вид это то что нужно. Как именно это сделано на все сто процентов я не уверен. Но могу предложить Вам спросить это на SO приложив этот пример. И если Вы разберетесь, то скажите мне названия алгоритмов, нажав ответить на этом сообщение.

[Максимка]

copal: Спасибо огромное, очень помог. Алгоритм называется "Лучший кандидат Митчелла"(Mitchell’s Best-Candidate). На самом деле очень распространённый и эффективный алгоритм. Кому интересно, вот тут принцип работы: bl.ocks.org/mbostock/d7bf3bd67d00ed79695b
Ещё раз спасибо!

Answer 1

[Александр Борисович]

глянь вот это.
paulbourke.net/texture_colour/randomtile

И это может пригодится
mrdoob.com/#/91/ball_pool

Answer 2

[alex_ak1]

То есть надо заполнить плоскость окружностями радиуса от р1 до р2 случайным образом?
Надо точно окружности ставить или примерно? Если примерно - то вообще проблемы не вижу.
Выбираем регион куда будем кидать, для него рассчитываем квадраты расстояний до соседних окружностей, где находим приемлемый минимум - туда и кидаем. Если минимумов несколько, то в случайный. Для простоты заполняем поле слева направо (типо пока есть место, кидаем в вертикальную полоску, как место кончается - сдвигаем полоску правее). Скорость будет велика (корень-то считать не надо), считать вообще можно в целых числах.

Comments

[alex_ak1]

Более того, можно расстояния считать при установке окружности, а не каждый раз заново. Что еще больше поднимет скорость.

[Максимка]

Да, именно от p1 до pn рандомно, только мне нужно отрисовывать в двух соседних регионах окружности разного цвета. Т.е есть фон и в нём фигура, к примеру, квадрат. Фон серыми а квадрат/круг/треугольник/цифру залить зелёными окружностями разных радиусов. Причём окружности в квадрате/whatever должны учитывать окружности фоновые, что они тоже существуют и плотно к ним прилегать, но не залезать. Т.е. прям таблица Рабкина получится.

[alex_ak1]

Максимка: Я для кругов это придумывал. Если квадраты-треугольники можно привести к кругу - то тоже самое. А выше вон есть алгоритмы заливки произвольными шаблонами.