Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my programming project I need to evenly distribute various sized circles in ellipse shaped area.

enter image description here

  • The ellipse area is defined by major and minor axis (4 points).
  • There is finite number of various sized circles that will all fit into the ellipse.
  • The order of the circles does not matter.

What is the criterion that will make them look evenly distributed? I don't think it's same distance between them, this can not even be achieved, can it? What algorithm will make them look as homogeneously distributed as possible?

Thanks for any help.

share|improve this question

3 Answers 3

I would resize the circles by a factor $k$ (in the figure $k=2$) so that the maximum number of circles is tangent to the ellipse and among them. To determine their centers I would try to solve this complex packing problem by trial and error, starting with the biggest circle (corresponding to the light blue one in the figure) and proceeding with the smaller ones (corresponding to the dark blue and the two equal sized black ones). The original circles would have the same centers.

enter image description here

share|improve this answer
    
I will think about this ... meanwhile could you please give it a new tag "packing problem"? I don't have enough reputation to create new tags. Thanks. –  daniel.sedlacek Feb 9 '11 at 18:27
    
Done. [packing-problem] –  Américo Tavares Feb 9 '11 at 18:50

maybe you can use this formula: http://onlinelibrary.wiley.com/doi/10.1111/itor.12006/full

Also you can find the code in fortran: http://www.ime.usp.br/~egbirgin/packing/ellipses/

share|improve this answer
    
Bit too heavy math for my mini project but definitely thanks for sharing! –  daniel.sedlacek Jul 25 '13 at 11:04

"Evenly distributed" almost sounds like an aesthetical criterion. But I guess this could be achieved by picking points randomly. Say, you pick a point within the ellipse and attribute it as a center for a circle (take the biggest circle such that it still is within the ellipse). Then repeat the procedure, but now, taking into account that the new circle must not overlap with circles that are already present. Whenever no circle satisfies the criteria and you are not done yet with distributing all the circles, pick a new random point.

I guess the method is not very efficient if you're stuck with a big circle at the end of the day and all other circles have been distributed. One way to overcome that is to start with the biggest circle, determine the ellipse of points within which the center of that bigger circle can be placed and choose a random point from that. Then, pick the next biggest circle and go over the same procedure: determining an ellipse of points that can be possible centers and pick a random point again, but now you have to see that there is no overlap with the already placed circle. Etc...

share|improve this answer
    
sorry that is not what I am looking for. The gaps between circles should be as similar as possible, not random. –  daniel.sedlacek Feb 9 '11 at 16:55
    
I see, I misinterpreted what you were looking for. Américo's answer seems to be what you need then. –  Raskolnikov Feb 9 '11 at 17:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.