Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

• Index
•  » Help Me !
•  » Finding the container circle of multiple circles (A circle packing Q)

Write your message and submit
|
Options

Topic review (newest first)

MathsIsFun
2005-11-11 07:55:37

Well found. And the authors say "No significant published research appears to exist addressing this problem, except ..."

Is this an NP-Complete (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
2005-11-11 01:25:53
nbrewer
2005-11-10 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 1-5.
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
2005-11-10 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
2005-11-10 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
2005-11-10 08:07:07

Got it!

Thanks!

MathsIsFun
2005-11-10 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
2005-11-10 07:33:10

That is only true on smaller n's, and only if the two circles are touching. But, the circles could have any coordinates. Basically I need to find a container circle with it's center at origin, and it's radius large enough to contain all circles 1 -> n.

Example:

Yes... now you are seeing why this is tripping me up....

mathsyperson
2005-11-10 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
2005-11-10 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
2005-11-10 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
2005-11-10 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
2005-11-10 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.