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

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

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 

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

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

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

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

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

 0 1 2 3 4 5 6 7 8 9 abcde fghij 

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

 0 1 * 3 * 5 6 7 8 9 a * * de fghi * 

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

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