Одностраничный алгоритм Бридсона: как размещать объекты случайно, но не слишком близко
Poisson Disk Sampling
В 2007 году Роберт Бридсон опубликовал одностраничную статью, которая решила классическую проблему компьютерной графики: как размещать объекты случайно, но с гарантированным минимальным расстоянием между ними. Алгоритм Бридсона, простой и эффективный, лежит в основе процедурной генерации лесов, симуляций и других задач. В этой статье подробно разбирается работа алгоритма, предлагаются два улучшения, которые ускоряют его в разы, а также рассматривается применение для стиплинга изображений и альтернативный алгоритм Митчелла, который обеспечивает максимальность и равномерность выборки без rejection sampling.
В 2007 году Роберт Бридсон опубликовал одностраничную статью, которая имеет почти 1000 цитирований и требует менее 10 минут для полного понимания.
- akkartik
Один из самых приятных интерфейсов для отладки, которые я когда-либо придумывал.
- jacobolus
Кому-то может пригодиться https://observablehq.com/@fil/poisson-distribution-generator...
- Terr_
> Рассмотрим, когда алгоритм размещает точку p, а затем сэмплирует её кольцо, чтобы получить новую точку q.
Я какое-то время путался, думая, что p и q здесь перепутаны, относительно визуализации ниже. [0] Однако теперь я понимаю, что упустил тот факт, что визуализация показывает две уже прочно установленные точки, и вопрос в том, где может быть размещена потенциальная третья (невидимая, безымянная) точка.
Так что, метафорически говоря, речь идёт о выборе нового направления движения, которое не обязательно ведёт по твоим собственным недавним следам.
[0] Можно сказать, у меня проблемы с тем, чтобы следить за своими p и q.