Задача из любого процедурного леса, россыпи камней или системы частиц: точки должны быть случайными, но не ближе заданного радиуса. Наивный вариант, кидать точки и отбрасывать близкие, быстро упирается в почти стопроцентный процент отказов. Джастин Стайнман разбирает одностраничный алгоритм Роберта Бридсона 2007 года, у которого почти тысяча цитирований: сетка с ячейкой
r / sqrt(d), где в каждой ячейке не больше одной точки, активный список и до 30 попыток на кольце от r до 2r вокруг каждой точки.Дальше две простые доработки. Для 2D: точка помнит родителя и не тратит попытки на сектор кольца, где заведомо слишком близко к нему. Вторая работает и в 3D. Есть объяснение, как равномерно сэмплировать кольцо и почему
2r * x^(1/d) на случайном единичном векторе при x, равномерном на отрезке от 1/2^d до 1, даёт правильное распределение, и пример на GPU. Метод старый, разбор свежий, применять можно в любом движке.@make_game