Круг в алгоритме упаковки прямоугольника

Question

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

Кто-то задал этот вопрос , который является своего рода обратным: мне нужны круги в прямоугольниках, а не наоборот, и я бы предпочел Java, а не MATLAB, хотя, при необходимости, я мог бы перенести его.

Спасибо!

EDIT:

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

Answer 1

Google: алгоритм, упаковывать круги в прямоугольник http://www.jstor.org/stable/4102107 Показывается прямо под этим вопросом переполнения стека. В статье jstor.org описан алгоритм жадных кругов в пакете прямоугольников.

Answer 2

Эта проблема, по-видимому, тесно связана с упаковкой бункера, поэтому я подозреваю, что она NP-сложная.Поэтому, к сожалению, я не думаю, что есть хороший алгоритм для эффективного решения этого вопроса (он же не грубая сила).

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

Было написано много исследовательских работ на эту тему, если у вас есть к ним доступ.Вот один из них: http://www.sciencedirect.com/science/article/pii/S0377221707004274