Алгоритм вычисления позиций случайных кругов, чтобы они не перекрывались

У меня следующая проблема.

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

Количество кругов и их размер ограничены, но случайны. Область будет довольно большой (2500x2500, может быть), поэтому массив пикселей, как предлагаетсяВот не может быть и речи. Человек, который ответил на тот же вопрос, предложил сетку, в которой ячейки имеют размер кругов. Это решило бы мою проблему, используя ячейки размером с максимально возможный круг, но я бы хотел, чтобы круги оставались как можно ближе, чтобы они не полностью удовлетворяли моим потребностям.

Очень простой подход состоит в обнаружении столкновений при размещении нового круга и удалении его от круга, с которым он сталкивается. После этого снова проверьте наличие коллизий и повторите процесс. Это, очевидно, не очень элегантно и склонно к бесконечным циклам (чаще, чем вы думаете).

The goal is to find the closest possible position for the newly inserted circle so it does not overlap with anyone else.

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

Ответы на вопрос(3)

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

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

 13 июн. 2012 г., 17:55
Вы правы, однако ЛЮБОЙ алгоритм, основанный на сетке, станет приближением, так как размещение ограничивающего прямоугольника вокруг круглого элемента ВСЕГДА оставляет пространство неиспользованным. Я думаю, что алгоритм, основанный на сетке, мог бы быть лучшим для скорости, но если вы ищете точность, или даже BEST FIT, то любой ответ сетки, вероятно, не будет подходящим способом, или, по крайней мере, не сеткой 1-го порядка.
 broncoAbierto13 июн. 2012 г., 16:00
Это хорошая идея. Проблема состоит в том, что каждый раз, когда помещается круг, будет применяться больше ограничений, чем необходимо, и в конечном итоге их может стать слишком много. Я проведу несколько тестов, чтобы увидеть, как это ведет себя. Благодарю.
Решение Вопроса

Я хотел бы сделать следующее: определить сетку х, у а для сетки рассчитайте минимальное расстояние до всех окружностей минус радиус до окружности. На полученной карте вы можете выбрать любой пиксель, который будет ярче X, что означает, что вы можете поместить круг с радиусом X без наложения. Вот код и изображение, показывающее полученную карту. Если вы хотите сделать это быстрее, вы можете использовать версию карты с меньшим разрешением.

import numpy as np,numpy.random
import matplotlib.pyplot as plt,matplotlib,scipy.optimize

maxx=2500
maxy=2500
maxrad=60 #max radius of the circle
ncirc=100 # number of circles
np.random.seed(1)

#define centers of circles
xc,yc=np.random.uniform(0,maxx,ncirc),np.random.uniform(0,maxy,ncirc)
rads=np.random.uniform(0,maxrad,ncirc)
#define circle radii

xgrid,ygrid=np.mgrid[0:maxx,0:maxy]
im=xgrid*0+np.inf

for i in range(ncirc):
    im = np.minimum(im, ((xgrid - xc[i])**2 + (ygrid - yc[i])**2)**.5 - rads[i])
# im now stores the minimum radii of the circles which can 
# be placed at a given position without overlap

#plotting 
fig=plt.figure(1)
plt.clf()
plt.imshow(im.T,extent=(0, maxx, 0, maxy))
plt.colorbar()
ax = plt.gca()
for i in range(ncirc):
     ax.add_patch(matplotlib.patches.Circle((xc[i], yc[i]), rads[i],
          facecolor='none', edgecolor='red'))
plt.xlim(0, maxx)
plt.ylim(0, maxy)
plt.draw()

The map of the minimum radii of a circles which can be placed without overlap

То, как карта выглядит как диаграмма Вороного, но неясно, можно ли ее использовать.

Обновление: после некоторых размышлений есть потенциально более быстрое решение, которое будет работать для большого количества кругов. Сначала создайте сетку области (скажем, 2500x2500). Заполните все пиксели, которые находятся внутри кругов на 1, все остальное с нуля. Затем вам нужно свернуть эту карту с круговым ядром с необходимым радиусом круга, который вы хотите разместить. Полученная карта должна иметь 0 в пикселях, которые можно использовать для размещения пикселей. Преимущество этого метода в том, что он может работать с очень большими сетками и количеством кругов, а свертывание может быть легко выполнено с помощью fft.

Вот иллюстрация, показывающая первую маску и маску после свертки с круглым ядром с радиусом 128 пикселей. Все нулевые пиксели в правой маске являются возможным расположением нового круга с радиусом 128.

mask

 13 июн. 2012 г., 16:52
Я обновил свой ответ, чтобы проиллюстрировать вторую идею
 broncoAbierto13 июн. 2012 г., 16:22
Это интересно, хотя я не уверен, что понимаю ваше обновление очень хорошо ... Это заставило меня задуматься о способе использования сетки довольно быстро. Я отвечу сам, если мне это удастся.

алгоритм компоновки на основе силы с разумным балансом отталкивающих и привлекательных сил.Этот ответ Указывает на библиотеку, которую вы можете использовать, Google найдет для вас другие, которые я ожидаю.

 broncoAbierto13 июн. 2012 г., 21:20
Это сделало бы отличное решение для моей цели, хотя его сложность (O (n ^ 3)) немного пугающая. Я проверю эти библиотеки в поисках эффективной реализации. Благодарю.

Ваш ответ на вопрос