bottles in a cupboard

[lionelhill]

This isn't really a puzzle in the conventional sense, as I don't have an answer, but it's a conundrum that's been trundling round in my head for some years now, and has given me a lot of fun. I also have to admit I posted it before in Dr Dobbs Journal, but the regular readership there had dwindled to about 10, and shortly afterwards dwindled by another one. I hope you enjoy it as much as I have:

Given a collection of random bottles (circles of a variety of sizes), write an algorithm that will decide whether they fit in a given cupboard (rectangle), and preferably, how to do it.

Note that I'm viewing this entirely as a 2 dimensional question; stacking bottles is not encouraged. All bottles are round without any projecting handles etc.

 

[p5wizard]

Well... the [tt]drink_bottle()[/tt] way out was an idea of mine, because I have a similar problem at home. My wife only allows me one shelf in our living room cupboard as drinks cabinet. So when I buy another bottle of liquor, I *have* to make sure there's room for it, even if this means [tt]drink_bottle()[/tt]-ing one of the existing ones. ;-)

But I see that this solution is not always a viable one. Unless of course you're using the lab's chemical bottles as hiding places for... No! You couldn't really...
Or could you?

p5

 

[SamBones]

Here's a solution treating the bottle as circles, not squares. It's a brute force algorithm since it hunts for a place to fit. And it's not an optimal solution, since the order the bottles are attempted can affect whether they fit or not. But is CAN find a solution and even seems to default to a honeycomb pattern if the bottle are all the same size (which is good).

First assume that the center of any bottle can be no closer to any wall of the cabinet than it's radius. This means we only have to test x,y positions for the center of a bottle that are smaller than the cabinet.
[tt]
0,0
+----------------------------+
| .......................... |
| . . |
| . . |
| . . |
| . . |
| .......................... |
+----------------------------+
max_x,max_y
[/tt]
That is, if the cabinet is from the vertical lines and dashes, then the center of a bottle can only be on or within the dots (from 0+radius,0+radius to max_x-radius,max_y-radius). And this changes per bottle as they each may have a different radius. Smaller bottles can have their center closer to the wall than a bigger bottle.

Then, to place each bottle, it's just a matter of testing each bottle. It can be placed if you can find an x,y in the cabinet that meets these criteria...

1) It's center is more than a radius away from any wall
2) The distance from it's center to the center of any other bottle is greater than the sum of their radiuses.

So, something like this (in bad pseudocode)...

int	max_x;	// width of cabinet
int	max_y;	// depth of cabinet

for each bottle not yet placed
  for test_x = (0 + bottle_radius) to (max_x - bottle_radius)
    for test_y = (0 + bottle_radius) to (max_y - bottle_radius)
      for b = loop through all bottles already placed
        if distance from test_x,test_y to b_x,b_y > bottle_radius+b_radius
          place bottle
        endif
      endfor
    endfor
  endfor
endfor

Presorting the bottles by their radius will change their placement. From smallest to biggest, verses biggest to smallest will cause different placements. Randomizing the bottle order would give different results.

Since it is a brute force method, you could even try every permutation of bottle order which would cover any and all order advantages and disadvantages.

Do I make sense? Not sure if I described it very well, but it makes sense to me.

 

[SamBones]

I guess Olaf first described it as fitting bottles using their radius. This is the basis of my algorithm.

I think it's wrong to treat the bottles as squares, or any other shape, since calculating intersections using it's radius is so simple.

In other words, if you have bottle A and bottle B, their centers must be farther apart than the sum of their radiuses. A bottle can't overlap another bottle.

 

[Olaf Doschke]

Hi SamBones,

well, a bounding box is defined by xmin, xmax, ymin, ymax and intersection checks of bounding boxes are simple comparisons, while checking the distance means computing (x2-x1)^2+(y2-y1)^2 > (r1+r2)^2.

But in fact solving the last equation (= instead of >) in a bottle by bottle algorithm will find an ideal position regarding the first bottle and that makes any bounding box check unneccessary, no matter how cheap it is, if you already know in relation to which other bottle you want to find an ideal position. In fact it turns out that bottle two can be placed on any point of a circle with radius r1+r2 around the center of the first bottle. Quite similar to that rectangle you found for a bottle in relation to the cupboard edges.

But then there could be two or more bottles. Taking two other bottles into consideration will make it an equation finding the intersection points of two circles with radius r1+r3 around (x1,y1) and r2+r3 around (x2,y2), r3 being the radius of the new bottle in that case (x1,y1) and (x2,y2) being the positions of the first two bottles.

And then there were three... This makes the bounding box check helpful in general, especially if you have a huge number of bottles and a veery large cupboard. Keeping track of what bottles are near to some area or point is another way. Spatial or in this case aerial subdivision can help to see, which bottles even don't need a bounding box check, because they are not even remotly neighbor bottles.

In fact many geometrical problems have solutions in raytracing algorithms and taking a look at that topic can help a lot for the bottles in a cupboard problem.

Bye, Olaf.