algorithm to place N rectilinear blocks in a ring to minimize total area
-
Imagine having ‘N’ rectilinear blocks of varying sizes. 'N' can be any number (< 1000); and of different but similar sizes. See here... blocks — ImgBB[^] I need an algorithm that will place these in a “ring” fashion, such that the area is minimized. White spaces or blank spaces within the ring are fine. Ring picture... ring — ImgBB[^] The constraints are… Each rectilinear block must be placed Minimize the area (x*y) Create a ring such as below Ring implementation Note that my two pictures don't align exactly, meaning not all the blocks in the first picture are placed in the second. These pictures are only provided as reference/examples. I’m not a computer scientist by trade. This would seem to be a cost optimization problem, by I’m having a problem wading through the many optimization algorithms out there. Any guidance on which algorithm would be viable? Thanks!
-
Imagine having ‘N’ rectilinear blocks of varying sizes. 'N' can be any number (< 1000); and of different but similar sizes. See here... blocks — ImgBB[^] I need an algorithm that will place these in a “ring” fashion, such that the area is minimized. White spaces or blank spaces within the ring are fine. Ring picture... ring — ImgBB[^] The constraints are… Each rectilinear block must be placed Minimize the area (x*y) Create a ring such as below Ring implementation Note that my two pictures don't align exactly, meaning not all the blocks in the first picture are placed in the second. These pictures are only provided as reference/examples. I’m not a computer scientist by trade. This would seem to be a cost optimization problem, by I’m having a problem wading through the many optimization algorithms out there. Any guidance on which algorithm would be viable? Thanks!
rbuchana wrote:
Create a ring such as below
What exactly is a ring? Of course I looked at the example, but it could be interpreted differently. Can the ring look [like this](https://ibb.co/2qnQ8CZ)? Or [this](https://ibb.co/R6qD5K0)? Maybe like [this](https://ibb.co/wdsKSK9)? Maybe even like [this](https://ibb.co/MVgBJRj)? Are the coordinates/sizes discrete?
-
rbuchana wrote:
Create a ring such as below
What exactly is a ring? Of course I looked at the example, but it could be interpreted differently. Can the ring look [like this](https://ibb.co/2qnQ8CZ)? Or [this](https://ibb.co/R6qD5K0)? Maybe like [this](https://ibb.co/wdsKSK9)? Maybe even like [this](https://ibb.co/MVgBJRj)? Are the coordinates/sizes discrete?
-
Imagine having ‘N’ rectilinear blocks of varying sizes. 'N' can be any number (< 1000); and of different but similar sizes. See here... blocks — ImgBB[^] I need an algorithm that will place these in a “ring” fashion, such that the area is minimized. White spaces or blank spaces within the ring are fine. Ring picture... ring — ImgBB[^] The constraints are… Each rectilinear block must be placed Minimize the area (x*y) Create a ring such as below Ring implementation Note that my two pictures don't align exactly, meaning not all the blocks in the first picture are placed in the second. These pictures are only provided as reference/examples. I’m not a computer scientist by trade. This would seem to be a cost optimization problem, by I’m having a problem wading through the many optimization algorithms out there. Any guidance on which algorithm would be viable? Thanks!
Cut the pieces out, move them around until optimum, then reverse engineer into a software solution.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it. ― Confucian Analects: Rules of Confucius about his food
-
Imagine having ‘N’ rectilinear blocks of varying sizes. 'N' can be any number (< 1000); and of different but similar sizes. See here... blocks — ImgBB[^] I need an algorithm that will place these in a “ring” fashion, such that the area is minimized. White spaces or blank spaces within the ring are fine. Ring picture... ring — ImgBB[^] The constraints are… Each rectilinear block must be placed Minimize the area (x*y) Create a ring such as below Ring implementation Note that my two pictures don't align exactly, meaning not all the blocks in the first picture are placed in the second. These pictures are only provided as reference/examples. I’m not a computer scientist by trade. This would seem to be a cost optimization problem, by I’m having a problem wading through the many optimization algorithms out there. Any guidance on which algorithm would be viable? Thanks!
Are you stating all of the constraints? To minimize the x*y area, it would often be preferable to have two very long sides and two very short ones for the inner rectangle. For example, say that all rectangles are the same shape and that there are 4n of them. They could be arranged to leave a square in the middle. Let's say the size of the square is a*a and that the four outer areas are also a*a. The x*y area would then be 3a*3a=9a^2. But instead of leaving an inner square, we can reduce two of its sides by 50% and increase the other two by 50%. Now we have an area of (7a/2)(5a/2) = (35/4)a^2, which is slightly smaller. The size of the inner rectangle is now (a/2)*(3a/2) = (3/4)a^2 instead of a^2.
Robust Services Core | Software Techniques for Lemmings | Articles
-
Are you stating all of the constraints? To minimize the x*y area, it would often be preferable to have two very long sides and two very short ones for the inner rectangle. For example, say that all rectangles are the same shape and that there are 4n of them. They could be arranged to leave a square in the middle. Let's say the size of the square is a*a and that the four outer areas are also a*a. The x*y area would then be 3a*3a=9a^2. But instead of leaving an inner square, we can reduce two of its sides by 50% and increase the other two by 50%. Now we have an area of (7a/2)(5a/2) = (35/4)a^2, which is slightly smaller. The size of the inner rectangle is now (a/2)*(3a/2) = (3/4)a^2 instead of a^2.
Robust Services Core | Software Techniques for Lemmings | Articles
-
You're correct. There is somewhat of a constraint on the aspect ratio (x/y), but also some flexibility. Meaning it doesn't need to be 50%, but 10% or 90% are probably too much. But no hard limit.
In that case, it's vague (at best) to speak of minimizing the total area.
Robust Services Core | Software Techniques for Lemmings | Articles
-
You're correct. There is somewhat of a constraint on the aspect ratio (x/y), but also some flexibility. Meaning it doesn't need to be 50%, but 10% or 90% are probably too much. But no hard limit.
If the problem can be stated more clearly, my guess is that it's a variant of the bin packing problem[^]. The article mentions that this problem is NP-hard, which effectively means that the time required to find the optimal solution rises exponentially, although it may be possible to more efficiently find a solution that is known to bounded in terms of how close it is to the optimal one.
Robust Services Core | Software Techniques for Lemmings | Articles
