Прошу прощения за написание такого длинного ответа. Мой подход заключается в том, чтобы начать с теоретического максимума и гарантированного минимума. Когда вы подходите к проблеме, вы можете использовать эти значения, чтобы определить, насколько хорош любой алгоритм, который вы используете. Если вы можете придумать лучший минимум, вы можете использовать его вместо этого.
Мы можем определить верхний предел для задачи, просто используя площадь круга
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, то вы не сможете поместить квадраты внутри круга.
Теперь, вооружившись теоретическим максимумом и абсолютным минимумом, вы можете начать использовать любой эвристический алгоритм для упаковки квадратов. Простой алгоритм состоит в том, чтобы просто разбить круг на строки и разместить в каждой строке столько квадратов, сколько вы можете. Затем вы можете принять этот минимум в качестве ориентира, чтобы убедиться, что вы нашли лучшее решение. Если вы хотите потратить больше вычислительной мощности в поисках лучшего решения, используйте теоретическое руководство в качестве ориентира для определения того, насколько вы близки к теоретическому наилучшему.
И если вы заботитесь об этом, вы можете решить, какой максимальный и минимальный теоретический процент покрытия минимальный алгоритм, который я определил, дает вам. Самый большой квадрат всегда покрывает фиксированное соотношение (я думаю, что это число равно pi / 4 или около 78,5% от внутренней площади круга). Таким образом, максимальный теоретический минимум составляет 78,5% покрытия. А минимальный нетривиальный (т. Е. Ненулевой) теоретический минимум - это когда вы можете разместить только 1 квадрат внутри самого большого квадрата, что происходит, когда вы упаковываете квадраты, которые на 1 больше половины ширины и высоты самого большого квадрата, который вы можете вписаться в круг. В основном вы занимаете чуть более 25% внутреннего квадрата с 1 упакованным квадратом, что означает, что вы получаете приблизительное покрытие около 20%