Создание точек не в пределах досягаемости друг друга?

Question

Я пытаюсь создать набор точек, которые не попадают в диапазон друг друга в фиксированной области.Мой подход приведен ниже:

import collections
from random import uniform

X = 100.0
Y = 100.0
points = 10
radius = 10

def in_circle(c_x, c_y, radius, x, y):
    dist_squared = (c_x - x)**2 + (c_y - y)**2
    return dist_squared <= radius ** 2

current = collections.defaultdict(lambda: [])

threshold = 0    

for point in range(1, points+1):
    cX = uniform(1.0, X)
    cY = uniform(1.0, Y)

    for cur in current:
        while in_circle(current[cur][0], current[cur][1], 2*radius, cX, cY):
          cX = uniform(1.0, X)
          cY = uniform(1.0, X)

          threshold += 1
          if threshold >= 1e+05:
              print "Cannot satisfy constraints"
              sys.exit(1)

    threshold = 0

    current[point] = [cX, cY]
    print cX, cY

Есть ли хороший способ завершить этот алгоритм, не заставляя его входить в бесконечный цикл?У меня есть пороговая проверка, но есть ли лучшие способы сделать это?

Answer 1

Эта статья о сэмплировании пуассоновских дисков может быть вам интересна.Автор объясняет стратегию выбора точек, которые не слишком близки друг к другу, и даже предоставляет пример кода на нескольких языках, включая Python.

Проблема с изложенной стратегией, как вы заметили,что если вы хотите выбрать много точек, или вы хотите, чтобы точки были довольно далеко друг от друга, производительность может стать ужасной.Я полагаю, что схема пуассоновского диска имеет лучшие характеристики производительности.

Answer 2

Этот класс проблем известен как круговая упаковка .В статье о mathworld указывается, что самые плотные из известных упаковок для единичного квадрата известны (и эту проблему можно преобразовать в эту, масштабируя x и y).Изображения в этой статье демонстрируют две плотные сферические упаковки (квадратную и гексагональную).

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

Answer 3

Можете ли вы разделить область на квадраты с side> = минимально допустимым расстоянием между точками , а затем просто выбрать несколько из них случайным образом?

Например, это ваши точечные квадраты, «пронумерованные» от 0 до j:

0 1 2 3 4
5 6 7 8 9
a b c d e
f g h i j

Затем вы создаете массив квадратных индексов (в данном примере от 0 до j), случайным образом перемешаете его , заканчивая, скажем, bc4j25e1670dfgh89ai3, и берете из его начала столько индексов, сколько вам нужно точки, например 5: bc4j2. Затем вы размещаете свои точки в центрах (или, возможно, в верхнем левом углу) выбранных квадратов:

0 1 * 3 *
5 6 7 8 9
a * * d e
f g h i *