
 Index
 » Help Me !
 » Finding the container circle of multiple circles (A circle packing Q)
Topic review (newest first)
 MathsIsFun
 20051111 07:55:37
Well found. And the authors say "No significant published research appears to exist addressing this problem, except ..."
Is this an NPComplete (travelling salesman) type problem? (In other words, you really need to check all possibilities, and that can take unrealistic amounts of computer time) My (limited) experience with such problems has been that just when you think you have the ultimate answer, someone comes along and shaves .002% off.
In which case, it deserves further work!
(BTW: It would be fun and educational to see the solutions animated)
 nbrewer
 20051111 01:25:53
 nbrewer
 20051110 09:11:27
It's actually all done in MS Excel. I then take a screen capture and manipulate the image in Photoshop. The code is spaghetti and not commented (alpha version), and it's not currently working very well, but I'll gladly share it with anyone. You can find it here:
http://www.bruware.com/cp/Circles.zip
After I get the kinks out, I plan on transferring the code to VB.NET. If I ever get around to it, I'll distribute the code and executable.
To use the Excel version (Assuming you have MS Excel installed):
1) Open sheet 1, and delete all the coordinates you see. 2) For as many circles as you want to play with, put in dummy coordinates. For example, if you want to play with 5 circles, put '1' in for the x and y of all circles radius 15. 3) Double click on 'Draw Circles' 4) Use your mouse and drag the circles around and place anywhere you like. 5) Once you have them positioned appropriately, click on 'Save Coordinates' (or something like that) 6) Then click on 'Draw Circles' again. You may have to click it several times to get the container circle to shrink down appropriately.
That's it. Cheesy, but a fun experiment.
 mathsyperson
 20051110 08:46:05
What are you using to make all of those pictures? If other people could use it too, they might be able to play around with it to help them to help you.
 nbrewer
 20051110 08:40:38
Since I know the coordinates of all circles, I wonder if I could imagine the points as a polygon. Not a polygon in the traditional sense, but the algorithm to find the center of a polygon (centroid) may still work. Or do you think the intersecting lines would cause the algorithm to fail?
The more I think about it, the more I think it would fail due to the vaarying radius sizes....
 nbrewer
 20051110 08:07:07
 MathsIsFun
 20051110 07:51:11
BTW, nbrewer, you should be able to do image uploads now.
Click "Post Reply", and you should see an "Upload Slots" selector. Have a go and tell me if it works for you.
 nbrewer
 20051110 07:33:10
 mathsyperson
 20051110 07:29:33
While googling to see if I could find anything useful, I found this quite good picture:
[Each number represents 1 ÷ radius]
Even if it doesn't help, it's still cool!
 mathsyperson
 20051110 07:11:37
Ooh, you're right. I tried it as a guest, and the box with the image upload option doesn't appear. Maybe it only works for mods.
Back to the question, it seems tough. All I can say by thinking is that the container's radius has to be at least the total of the biggest two circles' radii, but you didn't need me to tell you that.
Calling the number of circles n and the smallest container radius r, I've got this so far:
n  r  1  1 2  3 3  ?
Pretty pathetic, really. I'll try to work out some more stuff, so we can try to find a pattern.
 nbrewer
 20051110 06:27:09
I still dont see any option to upload an image, but did see how to use the [ i m g ] tags. So, here you are:
As you see, the container circle could be a bit smaller. The circles go from radius 1 to radius 5.
 mathsyperson
 20051110 06:18:54
Umm, they do. When you post, there's a bit just below the post box labelled 'Image Upload'. And an image would help immensely.
 nbrewer
 20051110 06:07:31
I am just starting to investige the wonderful world of circle packing and am trying to figure out how to find the smallest circle which will contain multiple smaller circles. The smaller circles range in radius from 1 to n. I've found a way to get real close, but no cigar. My trig skills are a bit rusty, but still intact. I wish this forum allowed files to be uploaded so I could show an image. If anyone needs further clarification or an image, just let me know.
Thanks in advance.
