Code covered by the BSD License

### Highlights from Growbubbles - maximum radius packing

4.6
4.6 | 6 ratings Rate this file 22 Downloads (last 30 days) File Size: 2.21 KB File ID: #33213 Version: 1.0

# Growbubbles - maximum radius packing

by

### Sven (view profile)

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

File Information
Description

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

MATLAB release MATLAB 7.13 (R2011b)
01 Apr 2015 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.

27 Oct 2014 Jingjing Meng

perfect

13 May 2014 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.

Comment only
09 Mar 2014 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?

12 Apr 2013 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

Comment only
12 Apr 2013 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?

Comment only
22 Jun 2012 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

Comment only
21 Jun 2012 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

Comment only
21 Jun 2012 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.

24 Nov 2011 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)

Comment only
24 Nov 2011 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! :)

Comment only
24 Nov 2011 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

24 Nov 2011 Yuri

### Yuri (view profile)

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

Comment only
24 Nov 2011 Yuri

### Yuri (view profile)

Thanks! Now it works!

23 Nov 2011 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.

Comment only
23 Nov 2011 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?

Comment only