Rectangle Packed with Randomly Generated Circles

Hey guys and gals,

I'm trying to pack a rectangle (0.5 x 1.0) with circles whose centers are randomly placed.

I believe I fully understand the idea and the strategy behind how to execute the program, something just seems to keep going wrong. I've gone and restructured the code at least 3 times now with some progress. I'll get three circles placed without conflict but the code runs without end and I have to CTRL+C to break it; a lot better than the previous no circle and infinite loop.

I just thought it was time to seek out help. I've included my 127 lines of code for you guys to go over. While writing it, I've attempted to comment on each part to ensure and reader knows what I was trying to do.

Any fixes or tips is greatly appreciated!

Kris

%Random Packing of Circles in A Rectangle
%By Kris Meche, LSU
%2015
%
%This particular code is being used to simulate a 50 micron deep
%layer of particles with radii between 16 and 20 microns.

%wipe the slate clean
clear,clc

%set the axis to a simple unit square
axis([0 1 0 1])

%draw an outline of the layer parameters to help visualize
rectangle('Position',[0,0,1,.5])

%declare necessary variables
area = zeros(0,1);                  %an array to track individual ball areas
totarea = 0;                        %the total area occupied by all balls
rectarea = .5;                      %the area of the ball holding region
density = 0;                        %the density of balls in the rectangle
numballs = 1;                       %a counter to track the number of balls
posxtracker = zeros(0,1);           %an array to track all the x-coordinates
posytracker = zeros(0,1);           %an array to track all the y-coordinates
radtracker = zeros(0,1);            %an array to track all the radii
WRONG = 0;                          %how mny times the program failed to place a ball

%A loop to establish the first ball
%Looping based on totalarea occupied by the balls
%allows for failures due to boundary conditions
while totarea == 0

    %randomly selecting a single integer
    %dividing by 100 to ensure ratio with the screen size
    posxrand = randi([0,100],1);
    posyrand = randi([0,50],1);
    radirand = randi([16,20],1);
    posx = posxrand/100;
    posy = posyrand/100;
    rad = radirand/100;

    %boundary check
    %the boundaries are adjusted .15 to make up for some distribution
    %error in which balls are not generating close to the left boundary
    if ((posx + rad) <= 1.15 && (posx - rad) >= 0 && (posy + rad) <= .5 && (posy - rad) >= 0)
        rectangle('Position',[posx-.15,posy,rad,rad],'Curvature',[1,1],'FaceColor', [.7 .7 .7]);

        %updating trackers
        posxtracker(1) = posx;
        posytracker(1) = posy;
        radtracker(1) = rad;            

        %updating area to exit loop
        area(1) = rad*rad*pi;
        totarea = totarea + area(1);
    else
        WRONG = WRONG + 1
    end

    %record the new density to update the while loop
    density = totarea/rectarea;
  end

%Loop to generate every ball past the first one
%the parameter for generation should be the area density
%Monte Carlo simulations have shown a optimal limit of 0.7
while density < 7.7 && WRONG < 4000      

        %declaring the bool statement for boundary checks
        %ensures the value resets each time a ball is added
        itshouldfit = true;

        %randomly selecting a single integer
        %dividing by 100 to ensure ratio with the screen size
        posxrand = randi([0,100],1);
        posyrand = randi([0,50],1);
        radirand = randi([16,20],1);
        posx = posxrand/100;
        posy = posyrand/100;
        rad = radirand/100;                

        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        %%boundary check + overlap check                           %%
        %%if it clears both, it gets drawn and trackers get updated%%
        %%if it fails either, gets recorded as a failed attempt    %%
        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

        %overlap check
        i = 1;
        while i <= numballs
            S = sqrt((posxtracker(i) - posx)^2 + (posytracker(i) - posy)^2);

            if S < (radtracker(i)+ rad)
                itshouldfit = false;
                i = numballs;
            end
            i = i + 1;
        end

        %boundary check
        %the boundaries are adjusted .15 to make up for some distribution
        %error in which balls are not generating close to the left boundary
        if ((posx + rad) <= 1.15 && (posx - rad) >= 0 && (posy + rad) <= .5 && (posy - rad) >= 0 && itshouldfit == true)
            rectangle('Position',[posx-.15,posy,rad,rad],'Curvature',[1,1],'FaceColor', [.7 .7 .7]);

            %updating counter
            numballs = numballs + 1;

            %updating trackers
            posxtracker(numballs) = posx;
            posytracker(numballs) = posy;
            radtracker(numballs) = rad;
            area(numballs) = rad*rad*pi;
            totarea = totarea + area(numballs);
        else
            WRONG = WRONG + 1
        end

        %record the new density to update the while loop
        density = totarea/rectarea;

end

%display the number of failed attempts
WRONG

[Kristopher]

Say, I had some spare time between classes and went back over the code again. I ran it multiple times until I noticed that on multiple occasions, it was generating 3 balls while having a true value, which should signal no overlap would occur if another ball was placed.

This means that it is something with the boundaries checker. I tinkered with the boundaries a bit and ran a few times and generated anywhere from 2 to 6 balls.

I really don't know how to interpret what happened, I just wanted to let you guys know in case it helps to figure it out any!

Answer 1

[Image Analyst]

That's because it's not robustly written with a failsafe. You should add a failsafe to any while loop. Check that the loop counter is less than some number or else bail out. It doesn't look like you have a loop counter but maybe you can use WRONG (not sure since I didn't dig into the code). So your while might look like this:

while density < 7.7 && WRONG < 1000  % or whatever.

Sorry, but I didn't delve in enough to figure out why you have an infinite loop in the first place but you can do that once you learn how to use the debugger.

[John D'Errico]

Excellent advice on all counts.

[Kristopher]

Thanks for the bit about the fail-safe! I went and added that into both loops. I was more focused on figured out why it's infinitely looping so I just disregarded it haha. But it does make it easier and quicker than CTRL+C'ing!

[Image Analyst]

Can you explain these two lines:

%Monte Carlo simulations have shown a optimal limit of 0.7
while density < 7.7 && WRONG < 4000

Do you want to keep going while the density is less than 0.7 or 7.7? WHich is it?