File Exchange

## Growbubbles - maximum radius packing

version 1.0 (2.21 KB) by

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

Updated

%GROWBUBBLES packs maximum radius circles at given central locations
%
% 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);

jie wang

Woojin Ahn

### Woojin Ahn (view profile)

This is awesome. One thing that I want to do is putting one large sphere and then generate spheres. Will that be also possible? I am trying to modify the code but can't figure out which part I should start with.

Jingjing Meng

perfect

Sven

### Sven (view profile)

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.

John

### John (view profile)

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?

Sven

### Sven (view profile)

@CUP:
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 ;
growbubbles(pts)
view(3), axis image, camlight

CUP

### CUP (view profile)

I have tried the following example:
pts = rand(10,3) * 10 ;
growbubbles(pts)
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?

Kevin Claytor

### Kevin Claytor (view profile)

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

Sven

### Sven (view profile)

Cheers Kevin.

Try this one:

pts = rand(10,3) * 10
[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;
end

Kevin Claytor

### Kevin Claytor (view profile)

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]
end
end
end
kind of structure.

Sven

### Sven (view profile)

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)

Sven

### Sven (view profile)

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! :)

Yuri

### Yuri (view profile)

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

Yuri

### Yuri (view profile)

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

Yuri

### Yuri (view profile)

Thanks! Now it works!

Sven

### Sven (view profile)

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);

into:

[dummyVariable,idx] = min(openPtMinGap);

and it should run just fine.

Yuri

### Yuri (view profile)

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?

##### MATLAB Release
MATLAB 7.13 (R2011b)