Сколько квадратов можно упаковать в круг?

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

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

Upper Limit = floor( (PI * (r pow 2)) / (L * L) )

Где L — ширина или высота квадратов, которые вы упаковываете, а r — радиус круга, в который вы упаковываете квадраты. Мы уверены, что это верхний предел, потому что а) у нас должно быть дискретное количество ящиков и б) мы не можем занимать больше места, чем площадь круга. (Формальное доказательство будет работать примерно так: предположим, что у нас на один ящик больше, чем это, тогда сумма площадей ящиков будет больше площади круга).

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

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

Самый большой квадрат, который вы можете поместить внутри круга, имеет 4 точки по периметру, а его ширина и длина sqrt(2) * radius (используя теорему Пифагора и используя радиус для длины более коротких сторон)

Итак, первое, что мы замечаем, это то, что если sqrt(2) * radius меньше, чем размер ваших квадратов, то вы не можете поместить ни один квадрат в круг, потому что, в конце концов, это самый большой квадрат, который вы можете поместить.

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

floor((sqrt(2) * radius)/ L)

Таким образом, это минимальное решение утверждает, что вы можете иметь как минимум

Lower Limit = floor((sqrt(2) * radius)/ L) pow 2

количество квадратов внутри круга.

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

Если на этом этапе вы получите ответ 0, то вы не сможете поместить ни один квадрат внутри круга.

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

И если вас это волнует, вы можете выяснить, какой максимальный и минимальный теоретический процент покрытия дает вам алгоритм минимума, который я определил. Самый большой квадрат всегда покрывает фиксированное соотношение (я думаю, пи/4 или около 78,5% внутренней площади круга). Таким образом, максимальный теоретический минимум составляет 78,5% покрытия. И минимальный нетривиальный (т.е. ненулевой) теоретический минимум - это когда вы можете разместить только 1 квадрат внутри самого большого квадрата, что происходит, когда квадраты, которые вы упаковываете, на 1 больше, чем половина ширины и высоты самого большого квадрата, который вы можете вписаться в круг. В основном вы занимаете чуть более 25% внутреннего квадрата с 1 упакованным квадратом, что означает, что вы получаете приблизительное покрытие около 20%

Растеризуйте круг, используя что-то вроде алгоритма окружности средней точки. Количество заполненных пикселей — это количество квадратов, которые вы можете поместить в круг. Конечно, поскольку вы на самом деле не заполняете пиксели, а просто считаете их, это должно занять время, пропорциональное окружности круга, а не его площади.

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

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

Вы можете собрать столько квадратов, сколько захотите, в круг. Если вы сомневаетесь в этом утверждении, нарисуйте на листе бумаги большой круг, затем внутри него начертите квадрат со стороной 10^(-18) м, повторите. Когда вы приблизитесь к границе круга, начните рисовать квадраты со стороной 10 ^ (-21) м.

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

Просто выстрел в темноте после нескольких минут размышлений...

Что, если вы работали с половиной круга и удваивали его в конце. Я бы начал с сетки квадратов длиной диаметра и ширины радиуса, по существу покрывающей полукруг. Затем проверьте все 4 угла каждого квадрата и убедитесь, что их координаты находятся в пределах радиуса круга. Это, конечно, потребует, чтобы вы построили круг и квадраты в какой-то системе координат или сетке.

Я надеюсь, что это имеет смысл... Это у меня в голове, и кажется, что это немного сложно сформулировать :)

РЕДАКТИРОВАТЬ: После рисования я думаю, что этот метод будет работать с небольшой настройкой. Я бы выровнял квадраты по диаметру, но сдвину первый вниз, пока он не подойдет. Установите его на место и начните выстраивать квадраты рядом с ним, пока они не перестанут помещаться. Подойдите к краю этой линии квадратов и повторите те же шаги, пока ваши ряды квадратов не достигнут радиуса.