Позиция N окружностей разных радиусов внутри большего круга без перекрытия

Question

Учитывая, что n окружностей с радиусами r1 ... rn, расположите их так, чтобы никакие круги не перекрывались, а ограничивающая окружность имела «маленький» радиус.

Программа принимает список [r1, r2, ... rn] как входной сигнал и выводит центры окружностей.

1. Я прошу «маленький», потому что «минимальный» радиус преобразует его в гораздо более сложной проблемой (минимальная версия уже оказалась NP трудно/полная - см сноску ближе к концу вопроса). Нам не нужен минимум. Если форма, сделанная кругами, кажется довольно круговой, это достаточно хорошо.
2. Вы можете предположить, что Rmax/Rmin < 20, если это помогает.
3. Низкий приоритет - программа должна иметь возможность обрабатывать более 2000 кругов. В начале, даже 100-200 кругов должно быть хорошо.
4. Возможно, вы догадались, что круги не должны быть упакованы плотно или даже касаться друг друга.

Цель состоит в том, чтобы придумать визуально приятное расположение заданных кругов, которое может вписаться в большой круг и не оставлять слишком много пустого пространства. (например, круги в color blindness test picture).

Вы можете использовать код Python ниже в качестве отправной точки (вам нужно будет NumPy и Matplotlib для этого кода - "Суда APT-получить установку Numpy Matplotlib" на Linux) ...

import pylab 
from matplotlib.patches import Circle 
from random import gauss, randint 
from colorsys import hsv_to_rgb 

def plotCircles(circles): 
    # input is list of circles 
    # each circle is a tuple of the form (x, y, r) 
    ax = pylab.figure() 
    bx = pylab.gca() 
    rs = [x[2] for x in circles] 
    maxr = max(rs) 
    minr = min(rs) 
    hue = lambda inc: pow(float(inc - minr)/(1.02*(maxr - minr)), 3) 

    for circle in circles: 
     circ = Circle((circle[0], circle[1]), circle[2]) 
     color = hsv_to_rgb(hue(circle[2]), 1, 1) 
     circ.set_color(color) 
     circ.set_edgecolor(color) 
     bx.add_patch(circ) 
    pylab.axis('scaled') 
    pylab.show() 

def positionCircles(rn): 
    # You need rewrite this function 
    # As of now, this is a dummy function 
    # which positions the circles randomly 
    maxr = int(max(rn)/2) 
    numc = len(rn) 
    scale = int(pow(numc, 0.5)) 
    maxr = scale*maxr 

    circles = [(randint(-maxr, maxr), randint(-maxr, maxr), r) 
       for r in rn] 
    return circles 

if __name__ == '__main__': 
    minrad, maxrad = (3, 5) 
    numCircles = 400 

    rn = [((maxrad-minrad)*gauss(0,1) + minrad) for x in range(numCircles)] 

    circles = positionCircles(rn) 
    plotCircles(circles) 

---

Дополнительная информация: Алгоритм упаковки окружности, обычно упоминаемый в результатах поиска Google, не применим к этой проблеме.

Заявление о проблеме другого «алгоритма упаковки окружности»: Таким образом, для комплекса K (графики в этом контексте называются симплициальными комплексами или сложными краткими) и соответствующими граничными условиями, вычисляют радиусы соответствующего круга упаковка для K ....

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

Другая проблема действительно есть интересное наблюдение (независимо от этой проблемы):

круг упаковки Теорема - Каждый круг упаковки имеет соответствующий плоский граф (это легко/очевидная часть), и каждый плоский график имеет соответствующую упаковку круга (не столь очевидная часть). Графики и упаковки являются дуальными друг от друга и уникальны.

У нас нет планарного графика или тангенциального отношения, чтобы начать с нашей проблемы.

Эта статья - Роберт Дж Фаулер, Майк Патерсон, Стивен Л. Танимото: Оптимальная упаковка и Покрытие на плоскости является NP-Complete - доказывает, что минимальная версия этой проблемы является NP-полной. Однако документ недоступен в Интернете (по крайней мере, нелегко).

Answer 1

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

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

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

Идея заключается в том, чтобы смотреть только в отдельных точках, что круг может жить в и перебирать их, используя следующий генератор:

def base_points(radial_res, angular_res): 
    circle_angle = 2 * math.pi 
    r = 0 
    while 1: 
     theta = 0 
     while theta <= circle_angle: 
      yield (r * math.cos(theta), r * math.sin(theta)) 
      r_ = math.sqrt(r) if r > 1 else 1 
      theta += angular_res/r_ 
     r += radial_res 

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

Я положу некоторые идеи, которые у меня есть, и сделайте это mo`bettah. Это может послужить хорошим первым шагом для идеи, основанной на физике, потому что вы начинаете без дублирования. Конечно, он может быть достаточно плотным, чтобы у вас не было много места.

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

Answer 2

Не решение, просто идея мозгового штурма: IIRC - один из распространенных способов получить приблизительные решения для TSP - это начать с произвольной конфигурации, а затем применить локальные операции (например, «обменивать» два ребра на пути), чтобы попробовать и получить более короткие и короткие пути. (Wikipedia link)

Я думаю, что что-то подобное можно было бы здесь:

1. Старт с произвольным центром позиции
2. «Оптимизация» эти позиции, так что нет пересекающихся кругов и поэтому круги как можно ближе возможно, увеличивая расстояние между перекрывающимися кругами и уменьшая расстояние между другими кругами, пока они не будут плотно упакованы. Это может быть сделано путем минимизации энергии, или может быть более эффективное жадное решение.
3. Применить итерационный оператор улучшения центра Позитоны
4. Goto 2, перерыв после максимального числа итераций или последняя итерация не нашла какие-либо улучшений

Интересный вопрос: какой от «оператора итерационного улучшения», который вы могли бы использовать на шаге 3? Можно предположить, что позиции на этом этапе локально оптимальны, но их можно улучшить, переставив большую часть кругов. Мое предложение состояло в том, чтобы произвольно выбрать линию через круги. Затем возьмите все круги «влево» от линии и поместите их на какую-то ось, перпендикулярную этой линии: Возможно, вы попробуете несколько строк и выберите тот, который приведет к самому компактному решению.

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

Другие возможные операции я мог думать:

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

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

(Ответ на комментарий :) Обратите внимание, что каждое из этих «улучшений» почти гарантировано создает перекрытия и/или ненужное пространство между кругами. Но на следующей итерации шаг 2 будет перемещать круги, чтобы они были плотно упакованы и снова не перекрывались. Таким образом, я могу сделать один шаг для локальных оптимизаций (не заботясь о глобальных) и один для глобальных оптимизаций (которые могут создавать локально субоптимальные решения). Это намного проще, чем один сложный шаг, который делает оба.

Answer 3

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

Answer 4

Похоже, проблема Круг упаковки, вот некоторая информация:

• Circle Packing Wolfram MathWorld
• Circle Packing Algorithms Google Scholar
• CirclePack software

Answer 5

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

Answer 6

http://en.wikipedia.org/wiki/Apollonian_gasket

Это кажется несколько соответствует тому, что вы пытаетесь сделать, и может обеспечить некоторые потенциальные ограничения для вас.