3

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

Дана область x ∈ (-6: 6), y ∈ (-3; 3) в декартовой системе координат. Минимальное расстояние между точками равно единице.

Необходимо абсолютно случайным образом раскидать точки так, чтобы они не стояли между собой ближе, чем на минимальное расстояние.

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

7
  • 1
    Расстояние между двумя точками считать - не? 21 окт 2017 в 12:15
  • И чем это поможет? 21 окт 2017 в 12:33
  • Вы сможете проверить, попадает ли новая точка в запрещенную область 21 окт 2017 в 12:34
  • Да не очень-то много точек при ваших условиях получается. Тут можно просто сравнивать расстояния со всеми уже вброшенными точками выбрасывать, если не годится. Но только к концу заполнения, боюсь, слишком много точек будут неподходящими...
    – Harry
    21 окт 2017 в 12:59
  • Итерационно - слишком медленно и не подходит при большом количестве точек с малой вероятностью попадания без "коллизии" с другими точками. Задача выше - упрощенный вариант. 21 окт 2017 в 13:02

1 ответ 1

2

Можно:

  1. Замостить прямоугольник одинаковыми квадратами со стороной b >= R/2, где R - требуемое расстояние (в общем случае - прямоугольниками со сторонами a, b >= R/2).
  2. Составить список из этих квадратов, и для каждого квадрата - список соседей по горизонтали, вертикали и диагонали..
  3. Точку выбирать в два этапа: сначала квадрат из списка, потом координаты внутри квадрата.
  4. После выбора удалять из списка квадрат точки и его соседей.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.