Расположите N кругов с разными радиусами внутри большего круга без наложения

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

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

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

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

Вы можете использовать приведенный ниже код Python в качестве отправной точки (для этого кода вам понадобятся numpy и matplotlib - "sudo apt-get install 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 f,orm (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-полной. Тем не менее, бумага не доступна онлайн (по крайней мере, не легко).

 user23846904 окт. 2010 г., 00:27
@ Раджан: Вы также можете задать этот вопрос наmath.stackexchange.com
 Niki03 окт. 2010 г., 23:59
@Greg Hewgill: он ищет приближение к трудной проблеме NP. Где еще он должен спросить, если не на сайте вопросов и ответов по программированию / информатике ??
 Loïc Février04 окт. 2010 г., 00:34
Это доказано NP-Hard: где? Есть какие-нибудь ссылки? Вы смотрели в научной литературе для алгоритмов приближения?
 Greg Hewgill03 окт. 2010 г., 23:52
Неважно, у меня только один голос.
 user23846903 окт. 2010 г., 23:43
@ Грег: Я думаю, что это очень субъективно. То, что вы называете загадкой, некоторые люди называют это программированием, а другие - математическим. Я прошел через этот тип аргументов для одного из моих вопросов.
 Rajan04 окт. 2010 г., 01:08
@Loic - Да, я сделал домашнее задание до того, как опубликовал проблему (на самом деле я много изучал, прежде чем сам придумал эвристику).google.com/... результат для упаковки неравных кругов в круг.
 Niki04 окт. 2010 г., 00:10
@Harpreet: Вы думаете, что это субъективно? Как вы думаете, проблема коммивояжера (или ее приближения) не связана с программированием? Если нет, у вас естьочень узкое определение понятия «связанный с программированием». Если да, то чем это отличается?
 Loïc Février04 окт. 2010 г., 13:30
@Rajan. Причина, по которой я спрашивал, состоит в том, что доказательство NP-полноты обычно основано на сведении задачи к другой, для которой может существовать хорошо известный алгоритм приближения. Часто новая проблема намного больше (по размеру), чем первая, но иногда может помочь.
 user23846904 окт. 2010 г., 00:41
@nikie: Суть в том, что я не против таких вопросов. Я просто рассказывал, что думают другие на SO.
 Rajan04 окт. 2010 г., 00:19
@ArunSaha - я уже заглянул туда. Это хорошо для решения задач упаковки кругов, может быть, до 10-15 кругов. Кроме того, он смотрит только на круги с одинаковыми радиусами.
 Rajan03 окт. 2010 г., 23:59
@ Грег - Хорошо ... Это не тот вопрос, на который можно ответить, используя имеющиеся у них знания, или поиск в Интернете, или просматривая документацию. Нужно будет подумать, поэкспериментировать и провести мозговой штурм. Если кому-то нравятся такие вещи, это полезная проблема. Я новичок в SO, но я видел открытые вопросы вокруг, которые получили некоторые достойные ответы, что подсказало мне, что людям здесь нравится решать сложные / открытые проблемы.
 Arun04 окт. 2010 г., 00:04
См. «Упаковка кругов» вmathworld.wolfram.com/CirclePacking.html
 Rajan03 окт. 2010 г., 23:36
После вашего комментария я снова посмотрел на свою проблему, но не смог увидеть часть головоломки. Пожалуйста, дайте мне знать, если проблема сформулирована таким образом, что это наводит на мысль о несерьезном вопросе типа головоломки. я бы перефразировал это. Или вы имеете в виду, что это слишком сложная проблема для переполнения стека?
 Rajan03 окт. 2010 г., 23:32
Не загадка ... это проблема, с которой я боролся на работе. У меня есть базовое решение, но я ищу лучшее.

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

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

 Rajan04 окт. 2010 г., 00:52
Это довольно крутая идея.
 Chris Johnson04 окт. 2010 г., 01:03
Это звучит многообещающе для меня, особенно в сочетании с каким-то графиком отжига (en.wikipedia.org/wiki/Simulated_annealing ), который вводит случайный шум, чтобы смешать частицы в начале симуляции, и (продолжая аналогию с зарядом) сужает потенциалы почти до квадратной ямы в конце симуляции, чтобы усилить ограничения на отсутствие проникновения и глобальную круглую форму. точно.
 Niki04 окт. 2010 г., 01:20
@ Крис Джонсон: Точно. Я предполагал, что каждый круг будет притягиваться к центру, и что два круга будут отталкиваться друг от друга, как только они начнут перекрываться. Но я думаю, что результаты будут более или менее одинаковыми.
 Chris Johnson04 окт. 2010 г., 01:13
Этот ответ является своего рода «минимизацией энергии», которую можно использовать в качестве шага 2 ответа nikie.

алить 2d круги в большую круглую емкость - и подождать, пока они встанут на свои места.

 Mene12 янв. 2012 г., 14:59
Это было бы интенсивно в вычислительном отношении, и результаты, скорее всего, будут очень неоптимальными.

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

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

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

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

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

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

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

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

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

 Rajan04 окт. 2010 г., 01:51
Некоторые отличные идеи здесь nikie ... Я постараюсь объединить их (если это возможно) с подходом Rafe и посмотрим, к чему это приведет.
 Chris Johnson04 окт. 2010 г., 00:57
Зеркальное отображение линий - хорошая идея для внесения глобальных изменений без скремблирования локальных оптимизаций, но, конечно, может создавать наложения.
 VividD11 янв. 2014 г., 19:35
Прекрасный ответ.
 Rajan05 окт. 2010 г., 07:18
Алгоритм упаковки кругов, который обычно упоминается в результатах поиска Google, не применим к этой проблеме. Этот алгоритм начинается с плоского графа и получает соответствующую ему «круговую упаковку». Это приложение «теоремы об упаковке кругов» Терстона. Тем не менее, у нас нет плоского графика для начала. Если бы у нас был планарный график, было бы алгоритмом полиномиального времени найти упаковку окружности. В общей форме эта задача является NP-полной.
 Rajan05 окт. 2010 г., 07:28
Постановка задачи другого «алгоритма упаковки окружностей» такова: учитывая комплекс K (граф K) и соответствующие граничные условия, вычислите радиусы соответствующей упаковки окружностей для K .... Он в основном начинается с графика, говорящего о том, какой круги касаются друг друга (вершины графа обозначают круги, а ребра обозначают касание между кругами). Но вершины и ребра произвольно размещены в пространстве. Нужно найти радиусы и положения окружности, чтобы удовлетворить трогательное отношение, обозначенное на графике. Не так, как наша проблема.
Решение Вопроса

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

Похоже, они пересекаются в центре, но это не так. Я украсил функцию размещения вложенным циклом, который проверяет каждый круг против каждого второго круга (дважды) и поднимает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

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

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

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

 Rajan05 окт. 2010 г., 09:09
Я думаю, что это не будет работать без "основной" части вашего кода.
 Rajan05 окт. 2010 г., 08:33
Мне любопытно ... Сколько кругов на твоей картине? И сколько времени потребовалось, чтобы сгенерировать этот вывод?
 aaronasterling05 окт. 2010 г., 08:44
@ Раджан, на картинке 400 кругов. На моей машине это занимает несколько минут, но моя машина работает медленно, поэтому вам, вероятно, не придется ждать слишком долго. Это, к сожалению, бесполезно, например, в режиме реального времени для веб-службы. Чтобы запустить его, просто скопируйте и вставьте код из ссылки в предоставленную вами функцию-заглушку, и все готово.
 aaronasterling05 окт. 2010 г., 09:23
@ Rajan, весь код доступен по ссылке в первом абзаце моего поста. Это вpastebin.com/VciE4Js7, Это около 124 строк, поэтому я не хотел помещать это здесь. Обратите внимание, что он не близок к полной настройке, я все еще в фазе «заставить его работать»;) Он должен работать как отдельный модуль, который экспортируетpositionCircles функция или просто вставить поверх функции заглушки, которую вы предоставляете.
 Rajan05 окт. 2010 г., 08:27
Это выглядит потрясающе. Это несколько напоминает мне гиперболический диск Эшера из-за концентрации больших кругов вблизи центра. Я думаю, что это можно изменить, если нужно, не слишком сильно влияя на алгоритм (я все еще пытаюсь понять ваш алгоритм, поэтому я могу ошибаться). Кроме того, я использую Numpy и Matplotlib только для построения изображения. Они не делают никакой обработки в моей заглушке.
 Cynthia GS08 нояб. 2016 г., 05:26
@aaronasterling: это красиво! Спасибо! Вот еще один вопрос, чтобы выбрать свой мозг: как бы вы задали радиус большого круга и заполнили его как можно большим количеством непересекающихся кругов? Значение: должен ли диаметр большого круга быть основным параметром, вместо того, чтобы выбирать количество маленьких кругов? Я пытался настроить ваш код, чтобы сделать это, но так как радиус большого круга никогда не вступает в игру, у меня были проблемы.

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

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

 q__05 окт. 2010 г., 08:45
Я думаю, что это может работать в определенных случаях ввода: сгенерируйте аполлоновскую прокладку из трех самых больших входов кривизны / радиусов, а затем запишите кривизну / радиусы, которые генерируются впоследствии. Если остальные предоставленные радиусы соответствуют радиусам, которые равны или меньше, чем сгенерированные радиусы, то вы можете просто нарисовать круги концентрическими, где вы ожидаете найти сгенерированные круги в прокладке. Однако это не очень хорошее решение, но, возможно, оно даст дополнительное понимание.
 Rajan05 окт. 2010 г., 08:31
Я не уверен, как использовать прокладки, но они прекрасны. Спасибо за публикацию.

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