Создание интерактивного макета. Упаковка кругов в квадрат и прямоугольник. Жадный алгоритм

[malkovsky]

Вроде как важа задача довольно известная, но к сожалению не самая простая. Беглый поиск "Circle packing" выдаёт например https://github.com/elmotec/circlify

Есть такой математик Роберт Ланг, который произвёл в 90х годах революцию в оригами придумав схему построения crease pattern из фигурки из спичек с помощью задачи упаковки кругов.
https://langorigami.com/article/treemaker/
https://dl.acm.org/doi/pdf/10.1145/237218.237249

Пример его работы

https://langorigami.com/artworks/

Во время ковида был у меня забавный случай. Все супермаркеты использовали квадратную разметку для соблюдения дистанции в 1,5м (только у Призмы я обнаружил на кассах разметку, соответствующую хексагональному замощению), написал на все контакстные почты известных мне супермаркетов с предложением хотя бы сделать как в Призме. Написал заодно и Роберту Лангу с просьбой дать первичную консультацию по задаче об упаковке. Оветили Роберт и менеджер из Призмы, ото всех остальных ничего.

[wataru]

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

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

[AnnaLafleur]

По просьбам трудящихся добавила пояснительный абзац перед переходом к коду:

Но что означает применение жадного алгоритма по отношению к задаче упаковки кругов? А именно то, что алгоритм будет выбирать позицию для нового круга, ориентируясь только на позиции ближайших кругов и не будет оценивать всю расстановку в целом. То есть код будет решать задачу оптимальности только на небольших независимых участках, что и означает решать задачу локально. Но как, даже локально, разместить круги максимально плотно? Что будет являться одним шагом для алгоритма? Максимально плотное размещение двух кругов — это касание. Но для двух кругов количество вариантов касаний бесконечно, тогда что насчёт трёх кругов? Как раз здесь это возможно: если известно расположение двух кругов, то третий круг будет касаться обоих одновременно только в двух случаях. Эту идею и реализуем далее после того, как разберёмся с вводными данными.