CODEWITHSUNDEEP
algorithmmathematical-optimizationbin-packing
robert3005
robert3005

Reputation: 83

Packing regular polygons into square

I am trying to figure out whether given those constraints regular 2D packing problem can be simplified. You have n regular s-sided polygons for s between 3 and 12. All of them have the same side length. We need to minimise the area of bounding square.

I would think that having all of the regular with same side length the packing can be easier since some configurations will always fit perfectly next to each other. Though I am not sure whether this property is of any use since local minimum might not translate to global minimum.

Upvotes: 4

Views: 2263

Answers (1)

Khaled.K
Khaled.K

Reputation: 5940

From your description, the polygons are regular polygons with all sides having the same length

This means that every polygon edges can connect to form a circle which can fit into a sub-square of size of 2r^2 perfectly

So an easy solution is to fit N polygons aligned in a square of size >= N * 2r^2, this is not an optimal solution, but works perfectly when you only have squares.

Here is an illustration that explains it:

enter image description here

First, knowing that all polygon sides have length of m

The polygon fits perfectly into a circle of ratio r

That circle fits perfectly into a square of size 2r^2

enter image description here

So we finally merge the fitting squares into one big square by tiling them in a matrix of M x M squares, where M * M >= N

Upvotes: 2

Related Questions