File Exchange

image thumbnail

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

17 Downloads

Updated

View License

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

Comments and Ratings (17)

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

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

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

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)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video