Как случайным образом, но равномерно распределить узлы на плоскости

Question

Мне нужно разместить от 1 до 100 узлов (на самом деле 25px точек) на холсте html5.Мне нужно, чтобы они выглядели случайно распределенными, поэтому использование какой-то сетки не работает.Я также должен убедиться, что эти точки не соприкасаются и не пересекаются.Я также хотел бы, чтобы не было больших пустых областей.Может кто-нибудь сказать мне, как называется этот алгоритм?Ссылка на проект с открытым исходным кодом, который делает это также будет приветствоваться.

Спасибо всем

Гвидо

Answer 1

То, что вы ищете, называется распределением Пуассона-диска . Это происходит в природе при распределении фоторецепторных клеток на сетчатке. Майк Босток ( Профиль StackOverflow ) написал замечательную статью под названием Алгоритмы визуализации . У него есть демонстрационные примеры JavaScript и много кода для просмотра.

В интересах сделать больше, чем добавить ссылку в ответ, я постараюсь дать краткое изложение статьи:

Алгоритм лучшего кандидата Митчелла

Простое приближение, известное как алгоритм лучшего кандидата Митчелла. Легко реализовать обе толпы в одних пространствах и оставить пробелы в других. Алгоритм добавляет новые точки по одному. Для каждой новой выборки алгоритм наилучшего кандидата генерирует фиксированное число кандидатов, скажем, 10. Точка, наиболее удаленная от любой другой точки, добавляется в набор, и процесс повторяется до тех пор, пока не будет достигнута желаемая плотность.

Алгоритм Бридсона

Алгоритм Бридсона для выборки с диска Пуассона ( оригинальная статья pdf) масштабируется линейно и также прост в реализации. Этот алгоритм растет с начальной точки и (ИМХО) довольно интересно наблюдать (снова см. Статью Майка Бостока). Все точки в наборе либо активны, либо неактивны. все точки добавляются как активные. Одна точка выбирается из активного набора, и в кольце (a.k.a кольцо) генерируется некоторое количество точек-кандидатов, которое проходит от образца с внутренним кругом, имеющим радиус r, и внешним кругом, имеющим радиус 2r. Выборка кандидата менее чем на расстоянии r от любой точки в FinalSet отклоняется. Как только образец найден, который не отклонен, он добавляется в FinalSet. Если все образцы-кандидаты отклонены, исходная точка помечается как неактивная, если предположить, что она имеет столько соседних точек, что больше не может быть добавлена ​​вокруг нее. Когда все выборки неактивны, алгоритм завершается.

Сетка размером r/√2 может быть использована для значительного увеличения скорости проверки баллов-кандидатов. Только одна точка может быть в квадрате сетки, и нужно проверять только ограниченное число соседних квадратов.

Answer 2

Самый простой способ - просто сгенерировать случайные (x, y) координаты для каждой из них, повторяя, если они касаются или перекрываются.

псевдокод:

do N times
{
start:
  x = rand(0, width)
  y = rand(0, height)
  for each other point, p
    if distance(p.x, p.y, x, y) < radius * 2
      goto start
  add_point(x, y);
}

Это O (n ^ 2) , но если n будет только 100, то это нормально.

Answer 3

Может быть, вы могли бы использовать сетку кругов и поместить одну 25px-точку в каждом круге?Не было бы случайно, но хорошо выглядишь.Или вы можете расположить точки случайным образом, а затем сделать так, чтобы пустые области притягивали точки и давали точкам отталкивание в ограниченном диапазоне, но это, возможно, слишком сложно и требует слишком много времени процессора для этой простой задачи.

Answer 4

Я не знаю, является ли это именованным алгоритмом, но похоже, что вы можете назначить каждому узлу позицию в «сетке», а затем выбрать случайное смещение. Это создаст впечатление хаоса, но при этом гарантирует отсутствие больших пустых пространств.

Например:

node.x = node.number / width + (Math.random() - 0.5) * SOME_SCALE;
node.y = node.number % height + (Math.random() - 0.5) * SOME_SCALE;