python - 用相同大小的圆圈包装一个矩形python

Question

我有一个由宽度 w 和高度 h 以及面积 A 定义的矩形边界框。

我们怎样才能将n个面积相等的圆a打包到这个矩形内，使得A-n*a最小。

换句话说，我们如何计算可以容纳在矩形内的相同大小的圆形的最佳数量

我的用例:我正在使用 kmeans 聚类算法对地理边界框中的车辆进行聚类。为了设置 kmeans 算法的簇数，我在应用 kmeans 算法之前尝试使用圆形填充作为导出簇数的一种方法。

Answer 1

编辑:编辑以帮助 OP 获得一个数字，该数字可以帮助根据平面中的拟合圆并最小化未覆盖的位置来确定 k 均值簇的数量。

from math import sqrt, pi

def get_approximate_k(rectangle_area, circle_area):
    # Making use of the fact that in an infinite hexagonal packing, the packing ratio is (pi*sqrt(3)/6)
    return int((rectangle_area * pi * sqrt(3))/(6 * circle_area))

print get_approximate_k(10*100, 12) # Returns 75