![]() So the first thing we note is that if sqrt(2) * radius is less than the dimension of your squares, then you cannot fit any squares in the circle, because afterall, this is the largest square you can fit. The largest square you can fit inside the circle has 4 points on the perimiter, and has a width and length of sqrt(2) * radius (by using pythagoras' theorem and using the radius for the length of the shorter edges) So, let's consider a solution that exists for all circles by taking a look at the largest square we can fit inside the circle. So with an upper limit in hand, we can now take any solution that exists for all circles and call it a minimum solution. (A formal proof would work somewhere along the lines of assume we had one more box than this, then the sum of the area of the boxes would be greater than the area of the circle). We are sure this is an upper limit because a) we must have a discrete number of boxes and b) we cannot take up more space than the area of the circle. Where L is the width or height of the squares you are packing and r is the radius of the circle you are packing the squares into. We can define an upper limit for the problem by simply using the area of the circle Upper Limit = floor( (PI * (r pow 2)) / (L * L) ) If you can think of a better minimum then you can use that instead. When you approach the problem, you can use these values to determine how good any algorithm you use is. ![]() My approach is to start with a theoretical maximum and a guaranteed minimum. I apologise for writing such a long answer. ![]()
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |