#python #2d #coordinates
#python #2d #координаты
Вопрос:
У меня есть квадратная область размером [a, a], содержащая вещественные числовые координаты. Я хочу заполнить его N случайными точками. Условия таковы, что расстояние между любыми двумя точками должно быть больше минимального расстояния D.
Способ грубой силы заключается в том, чтобы продолжать генерировать случайную точку до тех пор, пока она не будет соответствовать условию. Но проверять условие со всеми другими точками довольно дорого. Есть ли лучший алгоритм для этого?
Комментарии:
1. Строго говоря, после первой точки каждая дополнительная точка не помещается случайным образом в пространство.
2. @Andrew да, ты прав в этом. Но я просто хочу, чтобы следующее случайное число было размещено случайным образом в пространстве, доступном в этой точке
Ответ №1:
Если бы у вас было наложение сетки поверх точек, вы могли бы сгенерировать окружность, радиус которой равен минимальному расстоянию вокруг каждой точки, и пометить каждую ячейку сетки, которая находится в этих кругах. Затем случайным образом выберите ячейку сетки без флажков для создания точки, затем повторяйте, пока не останется пробелов.
Комментарии:
1. Это действительно хорошее решение. Для этого вы можете использовать гексагональную плотную упаковку.
2. Это была моя мысль, также, в более общем плане, для фиксированных значений
aиD, вероятность того, что вы сможете разместить N точек, падает очень быстро по мереNувеличения3. На самом деле это именно то, что я делал до сих пор. Но я больше не могу использовать сетку, потому что теперь мне нужно работать в непрерывном домене.
4. @corvo значит, вы не можете просто перевести / преобразовать координаты сетки в непрерывные? Теоретически вы можете поместить точку в любом месте внутри свободного «пикселя», она не обязательно должна находиться прямо в мертвой точке, поэтому местоположение точки не обязательно должно быть жестко квантовано в соответствии с координатами сетки.
5. @RandomDavis Да, это дало бы мне значения в непрерывной области, но я могу отметить только целую ячейку в сетке. Итак, допустим, часть ячейки удовлетворяет ограничению расстояния, а другая часть — нет. Но мне придется пометить всю ячейку. Таким образом, это означало бы ложную пометку этой области ячейки. Итак, это не то решение, которое я хочу. Но да, это определенно улучшение по сравнению с моим текущим подходом к сетке, и размер ложной области можно уменьшить, создавая все меньшие и меньшие сетки с учетом компромисса между точностью и вычислениями, который кто-то готов сделать.
Ответ №2:
Я не уверен, существует ли аналитическое решение вашей проблемы. На самом деле, может быть, как было предложено выше :-).
Однако предложенный вами метод грубой силы можно сделать более эффективным, используя R-дерево и выполняя поиск ближайших соседей. В принципе, я бы вставил точку в случайном порядке, искал ее ближайших соседей и перемещал ее в соответствии с расстоянием от этих NN.