CODEWITHSUNDEEP
python
Raja Sattiraju
Raja Sattiraju

Reputation: 1272

Packing a rectangle with equal sized circles python

I have a rectangular bounding box defined by width w and height h and area A.

How can we pack n number of circles of equal area a inside this rectangle such that A-n*a is minimal.

In other words, how can we calculate the optimal number of equal sized circles that can be packed inside a rectangle

My use case: I am using kmeans clustering algorithm for clustering vehicles in a geographical bounding box. In order to set the number of clusters for the kmeans algorithm, I am experimenting with circle packing as one way of deriving the number of clusters before I apply the kmeans algorithm.

Upvotes: 1

Views: 2198

Answers (1)

Sreyantha Chary
Sreyantha Chary

Reputation: 656

Edit: Edited to help the OP get a number that can help in deciding the number of k-means clusters based on fitting circles in a plane and minimizing the uncovered places.

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

Upvotes: 1

Related Questions