Code covered by the BSD License  

Highlights from
Growbubbles - maximum radius packing


4.5 | 5 ratings Rate this file 23 Downloads (last 30 days) File Size: 2.21 KB File ID: #33213
image thumbnail

Growbubbles - maximum radius packing



Growbubbles takes centroid points and returns the maximum radius circles or spheres without overlap

| Watch this File

File Information

%GROWBUBBLES packs maximum radius circles at given central locations
% PTRADS = GROWBUBBLES(PTS) returns the radius of circles at coordinates in PTS with all radii
% maximised but without any circles overlapping. PTS is a P-by-N matrix of P "N-dimensional"
% points.
% If no output argument is given, PTSIN will be plotted as circles (2D) or spheres (3D) to the
% current figure.
% Example:
% % Find the maximum packed radius of 20 random points
% x = rand(20, 2);
% ptRads = growbubbles(x);

MATLAB release MATLAB 7.13 (R2011b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (15)
27 Oct 2014 Jingjing Meng


13 May 2014 Sven

Hi John, the algorithm used was aimed at being simple and iterative (ie, not needing the optimisation toolbox). I'm afraid if you want to bias radii towards a particular distribution then you'd probably need to run an optimisation using constraints that circles cannot intersect and that distribution built into your objective function.

09 Mar 2014 John

This is really nice, but is there any way to control the distribution of the radii i.e. maximise the radii to give a normal or log-normal distribution?

12 Apr 2013 Sven

It's actually a 3D picture, it's just that by default it has no shading and is looking from the XY direction. Try this:
pts = rand(10,3) * 10 ;
view(3), axis image, camlight

12 Apr 2013 CUP

I have tried the following example:
pts = rand(10,3) * 10 ;
But I can't get the 3D bubbles picture right side as you pasted on, what I got seems like a 2D picture, that's why?could you help me?

22 Jun 2012 Kevin Claytor

Perfect and snappy, meshgrid surprises me with a new use every day! Thanks Sven.
The one thing I would add to that for anyone else is to match up the points with the meshgrid size, something like;
pts = rand(10,3) * M

21 Jun 2012 Sven

Cheers Kevin.

Try this one:

pts = rand(10,3) * 10
rads = growbubbles(pts)
[II,JJ,KK] = meshgrid(1:M,1:M,1:M);
BW = false(size(II));
for i=1:size(pts,1)
BW = BW | ( (II-pts(i,2)).^2 + (JJ-pts(i,1)).^2 + (KK-pts(i,3)).^2 ) <= rads(i)^2;

21 Jun 2012 Kevin Claytor

Does what it says it does.

What I would really like is a quick way of generating an MxMxM matrix of say binary values: 1 = in a sphere, 0 = otherwise. Is there a quick way of doing this? I can think of some ways, but they're all bracketed in far too many for loops;
for a=1:M
for b=1:M
for c=1:m
[code to check to see if this point is in a sphere]
kind of structure.

24 Nov 2011 Sven

What would you do in the following instances:

1. You only have two circles. (If their centers moved, they would grow to infinity)

2. You have many circles. (All the outside circles would grow very close to infinity)

24 Nov 2011 Sven

Yes Yuri, this entry grows bubbles with a *known* center. To make all bubbles grow more would require that they *break* this constraint. I get 3 stars because it doesn't solve a different problem entirely? Ouch! :)

24 Nov 2011 Yuri

Ok, I red the code and found answer: the code is fast, simple, but... can not produces "connected media". It's a pity

24 Nov 2011 Yuri

Well well well, but why some spheres have no contact with others? Even in your plot we see this.

24 Nov 2011 Yuri

Thanks! Now it works!

23 Nov 2011 Sven

Ah... that's the tricky little tilde (~) operator. It was introduced in version 2009b. If you use an earlier version, just change the line:

[~,idx] = min(openPtMinGap);


[dummyVariable,idx] = min(openPtMinGap);

and it should run just fine.

23 Nov 2011 Yuri

Your program looks very interesting, but when I run it, I got the error message:

??? Error: File: growbubbles.m
Line: 42 Column: 7
Expression or statement is incorrect--possibly unbalanced (, {, or [.

for which versions did you test it?

Contact us