How can I better pack rectangles tangent to a sphere for a 3d gallery?

I am creating a 3D sphere gallery with ActionScript 3 and the Flash 10 3D (2.5D) APIs. I have found a method that works but is not ideal. I would like to see if there is a better method.

My algorithm goes like this:

Let n = the number of images
    h = the height of each image
    w = the width of each image

1. Approximate the radius of the circle by assuming (incorrectly) that the surface area of the images is equal to the surface area of the sphere we want to create.

   To calculate the radius solve for r in nwh = 4πr2. This is the part that needs to be improved.

2. Calculate the angle between rows.

   rowAngle = 2atan(h / 2 / r).

3. Calculate the number of rows.

   rows = floor(π / rowAngle).

4. Because step one is an approximation, the number of rows will not fit perfectly, so for presentation add padding rowAngle.

   rowAngle += (π - rowAngle * rows) / rows.

5. For each i in rows:

   1. Calculate the radius of the circle of latitude for the row.

      latitudeRadius = radius * cos(π / 2 - rowAngle * i.

   2. Calculate the angle between columns.

      columnAngle = atan(w 开发者_如何学Python/ 2 / latitudeRadius) * 2.

   3. Calculate the number of colums.

      columns = floor(2 * π / columnAngle)

   4. Because step one is an approximation, the number of columns will not fit perfectly, so for presentation add padding to columnAngle.

      columnAngle += (2 * π - columnAngle * column) / column.

   5. For each j in columns, translate -radius along the Z axis, rotate π / 2 + rowAngle * i around the X axis, and rotate columnAngle * j around the Y axis.

To see this in action, click here. alternate link. Notice that with the default settings, the number of items actually in the sphere are less by 13. I believe is the error introduced by my approximation in the first step.

I am not able to figure out a method for determining what the exact radius of such a sphere should be. I'm hoping to learn either a better method, the correct method, or that what I am trying to do is hard or very hard (in which case I will be happy with what I have).

I would divide this problem into two connected problems.

1. Given a radius, how do you pack things on to the sphere?

2. Given a number of things, how do you find the right radius?

If you have a solution to the first problem, the second is easy to solve. Here it is in pseudo-code.

lowerRadius = somethingTooSmall

fittedItems = itemsForRadius(lowerRadius)

while fittedItems < wantedItems:
    lowerRadius *= 2
    fittedItems = itemsForRadius(lowerRadius)

upperRadius = 2 * lowerRadius

while threshold < upperRadius - lowerRadius:
    middleRadius = (upperRadius + lowerRadius)/2
    if itemsForRadius(middleRadius) < wantedItems:
        lowerRadius = middleRadius
    else:
        upperRadius = middleRadius

This will find the smallest radius that will pack the desired number of things with your packing algorithm. If you wish you could start with a better starting point - your current estimate is pretty close. But I don't think that an analytic formula will do it.

Now let's turn to the first problem. You have a very reasonable approach. It does have one serious bug though. The bug is that your columnAngle should not be calculated for the middle of your row. What you need to do is figure out the latitude which your items are in that is closest to the pole, and use that for the calculation. This is why when you try to fit 10 items you find a packing that causes the corners to overlap.

If you want a denser packing, you can try squishing rows towards the equator. This will result in sometimes having room for more items in a row so you'll get more things in a smaller sphere. But visually it may not look as nice. Play with it, and decide whether you like the result.

BTW I like the idea. It looks nice.

In the case of squares, it seems to be an approximate formula for knowing the relationship between the radius, the square's side and the number of squares embedded.

Following this, the number of squares is:

Floor[4 Pi/Integrate[(x^2 + y^2 + r^2)^(-3/2), {x, -a/2, a/2}, {y, -a/2, a/2}]]

or

Floor[(Pi r)/ArcCot[(2 Sqrt[2] r Sqrt[a^2+2 r^2])/a^2]]  

where

   r = Radius
   a = Square side

If you plot for r=1, as a function of a:

Where you can see the case a=2 is the boundary for n=6, meaning a cube:

Still working to see if it can be extended to the case of a generic rectangle.

Edit

For rectangles, the corresponding formula is:

 Floor[4 Pi/Integrate[(x^2 + y^2 + r^2)^(-3/2), {x, -a/2, a/2}, {y, -b/2, b/2}]]

which gives:

Floor[(2 Pi r)/(Pi-2 ArcTan[(2 r Sqrt[a^2+b^2+4 r^2])/(a b)])]

where

   r   = Radius
   a,b = Rectangle sides

Let's suppose we want rectangles with one side half of the other (b = a/2) and a sphere of radius 1.

So, the number of rectangles as a function of a gives:

Where you may see that a rectangle with a "large" side of size 2 allows 10 rectangles in the sphere, while a rectangle of "large" side 4 allows only 4 rectangles.