File Exchange

Growbubbles - maximum radius packing

version 1.0.0.0 (2.21 KB) by
Growbubbles takes centroid points and returns the maximum radius circles or spheres without overlap

Updated 10 Oct 2011

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

Cite As

Sven (2021). Growbubbles - maximum radius packing (https://www.mathworks.com/matlabcentral/fileexchange/33213-growbubbles-maximum-radius-packing), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (19)

Ettore Barbieri

Hello, thank you, Sven, for your submission - I really like the algorithm - 5 stars!
However, when the number of points grows, the code becomes really slow.
The bottleneck is in computing the centre-to-centre distance.
You're using essentially a "brute force" approach that, even using bsxfun, becomes problematic for a large number of spheres, say more than 10,000.
I have modified it, although I have used the Statistics and Machine Learning Toolbox, which I understand not everyone has.
For those using the toolbox, one can use the KDTreeSearcher class, and either nearest neighbour search or range search.
I've tested the Nearest Neighbour with 50 neighbours and it works for up to 100,000 particles.
For me "working" means that the minimum gap between the surfaces of the spheres is zero, and not negative (overlap).

I would be happy to share it, not for being a "know-it-all', but for the benefit of the community :)

Thanks again

Brice Kabore

jie wang

Woojin Ahn

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

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

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

@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

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

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

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

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

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

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

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

Yuri

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

Yuri

Thanks! Now it works!

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

into:

[dummyVariable,idx] = min(openPtMinGap);

and it should run just fine.

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?

MATLAB Release Compatibility
Created with R2011b
Compatible with any release
Platform Compatibility
Windows macOS Linux