MATLAB Answers

1

Fill area with random circles having different diameters

Asked by mikymike89 on 12 Jun 2018
Latest activity Edited by Walter Roberson
on 4 Jul 2019
I should fill the area of a 500x500 square with random circles having random diameters between 10 and 50 (without overlap). Then, I need the output file of the generated coordinates. Can someone help me, please?

  2 Comments

How many number of circles? Any further conditions?
Is this homework? Do you want the circles in a digital image (if so, what resolution), or do you want them in an overlay (graphical plane) like you can do with plot(), scatter(), or viscircles()? Be sure to look at Walter's answer below.

Sign in to comment.

6 Answers

Answer by Anton Semechko on 14 Jun 2018
 Accepted Answer

Hopefully this iteration of code (see below) is the last one.
% Unconstrained circle packing example. Only centroids constrained to the rectangle.
ab=[500 500]; % rectangle dimensions; [width height]
R_min=5; % minimum circle radius
R_max=25; % maximum circle radius
cnst=false;
[C,R]=random_circle_packing_rectangle(ab,R_min,R_max,cnst);
% Constrained circle packing example
ab=[500 500]; % rectangle dimensions
R_min=5; % minimum circle radius
R_max=25; % maximum circle radius
cnst=true;
[C,R]=random_circle_packing_rectangle(ab,R_min,R_max,cnst);
% Example of how to export data
FileName=sprintf('%s%sRandom circle packing data.csv',cd,filesep);
csvwrite(FileName,[C R]);
fprintf('Data saved to %s\n',FileName)
============================================================================================================
function [C,R]=random_circle_packing_rectangle(ab,R_min,R_max,cnst,vis)
% Random circle packing inside a rectangle.
%
% INPUT:
% - ab : 1-by-2 vector specify rectangle dimensions; ab=[width height].
% ab=[500 500] is the default setting. Coordinates of the
% lower-left and upper-right corners of the rectangle are
% (0,0) and (ab(1),ab(2)), respectively.
% - R_min : minimum circle radius. R_min=min(ab)/100 is the default setting.
% - R_max : maximum circle radius. R_max=min(ab)/20 is the default setting.
% - cnst : set cnst=true to ensure all circles fit into the rectangle.
% cnst=false is the default setting, meaning that only circle
% centroids will be constrained to the boundary and interior of
% the rectangle.
% - vis : set vis=false to suppress visualization. vis=true is the
% default setting.
%
% OUTPUT:
% - C : Q-by-2 array of sphere centroids
% - r : Q-by-1 array of sphere radii
%
% Default settings
if nargin<1 || isempty(ab)
ab=[500 500];
elseif numel(ab)~=2 || ~isnumeric(ab) || ~ismatrix(ab) || sum(ab(:)<1E-6 | isinf(ab(:)))>0
error('Invalid entry for 1st input argument (ab)')
else
ab=ab(:)';
end
if nargin<2 || isempty(R_min)
R_min=min(ab)/100;
elseif numel(R_min)~=1 || ~isnumeric(R_min) || R_min>(min(ab)/4-2E-12) || R_min<min(ab)/1E3
error('Invalid entry for 2nd input argument (D_min)')
end
if nargin<3 || isempty(R_max)
R_max=min(ab)/20;
elseif numel(R_max)~=1 || ~isnumeric(R_max) || R_max<R_min || R_max>(min(ab)/4-2E-12)
error('Invalid entry for 3rd input argument (D_max)')
end
if nargin<4 || isempty(cnst)
cnst=false;
elseif numel(cnst)~=1 || ~islogical(cnst)
error('Invalid entry for 4th input argument (cnst)')
end
if nargin<5 || isempty(vis)
vis=true;
elseif numel(vis)~=1 || ~islogical(vis)
error('Invalid entry for 5th input argument (vis)')
end
% Grid used to keep track of unoccupied space inside the rectangle
dx=max(min(ab)/2E3,R_min/50);
x=0:dx:ab(1);
y=0:dx:ab(2);
[x,y]=meshgrid(x,y);
G=[x(:) y(:)];
clear x y
% Start by placing circles along the edges if cnst=false
dR=R_max-R_min;
Cc=bsxfun(@times,ab,[0 0; 1 0; 1 1; 0 1]); % corner vertices
if ~cnst
[Xa,Xb]=deal(Cc,circshift(Cc,[-1 0]));
Rc=dR*rand(4,1)+R_min;
[Rc_a,Rc_b]=deal(Rc,circshift(Rc,[-1 0]));
[C,R]=deal(cell(4,1));
for i=1:4
[Ci,Ri]=SampleLineSegment(Xa(i,:),Xb(i,:),Rc_a(i),Rc_b(i),R_min,R_max);
Ci(end,:)=[];
C{i}=Ci;
Ri(end)=[];
R{i}=Ri;
end
C=cell2mat(C);
R=cell2mat(R);
% Update grid
for i=1:size(C,1), G=update_grid(C(i,:),R(i),G,R_min); end
else
% Remove all grid points less than R_min units from the boundary
G_max=G+R_min+1E-12;
G_min=G-R_min-1E-12;
chk_in=bsxfun(@le,G_max,ab) & bsxfun(@ge,G_min,[0 0]);
chk_in=sum(chk_in,2)==2;
G(~chk_in,:)=[];
clear G_max G_min chk_in
C=[]; R=[];
end
% Begin visualization
if vis
hf=figure('color','w');
axis equal
set(gca,'XLim',[0 ab(1)]+ab(1)*[-1/20 1/20],'YLim',[0 ab(2)]+ab(2)*[-1/20 1/20],'box','on')
hold on
drawnow
Hg=plot(G(:,1),G(:,2),'.k','MarkerSize',2);
t=linspace(0,2*pi,1E2)';
P=[cos(t) sin(t)]; % unit circle
if ~isempty(C)
for i=1:size(C,1)
Pm=bsxfun(@plus,R(i)*P,C(i,:));
h=fill(Pm(:,1),Pm(:,2),'r');
set(h,'FaceAlpha',0.25)
end
drawnow
end
end
f=5:5:100;
fprintf('Progress : ')
fprintf(' %-3u ',f)
fprintf(' (%%complete)\n')
fprintf(' ')
Ng=size(G,1);
f=size(G,1)-round((f/100)*Ng);
% Use rejection sampling to populate interior of the rectangle
flag=true;
n=0; cnt=0; m=0;
while ~isempty(G) && cnt<1E4 && (~vis || (vis && ishandle(hf)))
n=n+1;
% New circle
if flag && (cnt>500 || size(G,1)<0.95*Ng)
flag=false;
Rg=R_max*ones(size(G,1),1);
end
i=[];
if cnt<=500 && flag
X_new=ab.*rand(1,2); % centroid
else
i=randi(size(G,1));
X_new=G(i,:)+(dx/2)*(2*rand(1,2)-1);
X_new=min(max(X_new,[0 0]),ab);
if cnt>1E3
Rg(:)=max(0.95*Rg,R_min);
end
end
if isempty(i)
R_new=dR*rand(1)+R_min; % radius
else
R_new=(Rg(i)-R_min)*rand(1)+R_min;
end
% Check if the circle fits inside the rectangle when cnst=true
if cnst
X_new_max=X_new+R_new+1E-12;
X_new_min=X_new-R_new-1E-12;
chk_in=X_new_max<=ab & X_new_min>=[0 0];
if sum(chk_in)<2
cnt=cnt+1;
continue
end
end
% Does the new circle intersect with any other circles?
if ~isempty(C)
d_in=sqrt(sum(bsxfun(@minus,C,X_new).^2,2));
id=d_in<(R+R_new);
if sum(id)>0
cnt=cnt+1;
if ~isempty(i)
Rg(i)=min(0.95*Rg(i),min(0.99*(R_new+dx/2),R_max));
Rg(i)=max(Rg(i),R_min);
end
continue
end
end
% Accept new circle
cnt=0;
m=m+1;
C=cat(1,C,X_new);
R=cat(1,R,R_new);
[G,id]=update_grid(X_new,R_new,G,R_min);
if ~flag, Rg(id)=[]; end
% Visualization
if vis && ishandle(hf)
Pm=bsxfun(@plus,R_new*P,X_new);
h=fill(Pm(:,1),Pm(:,2),'r');
set(h,'FaceAlpha',0.25)
if mod(m,50)==0
delete(Hg)
Hg=plot(G(:,1),G(:,2),'.k','MarkerSize',2);
drawnow
end
end
% Progress update
if size(G,1)<=f(1)
f(1)=[];
fprintf('* ')
end
end
fprintf('\n')
% Show rectangle
if vis && ishandle(hf)
Cc=[Cc;Cc(1,:)];
plot(Cc(:,1),Cc(:,2),'--k','LineWidth',2)
delete(Hg)
end
if nargout<1, clear C R; end
function [G,id]=update_grid(X_new,R_new,G,R_min)
% Remove grid points within R_new+R_min units of new circle
D=sum(bsxfun(@minus,G,X_new).^2,2);
id=D<(R_new+R_min+1E-12)^2;
G(id,:)=[];
function [C,R]=SampleLineSegment(Xa,Xb,Ra,Rb,R_min,R_max)
% Place circles along line segment between points Xa and Xb
r=Xb-Xa;
L=norm(r);
r=r/norm(L);
dR=R_max-R_min;
C=Xa; R=Ra;
while true
R_new=dR*rand(1)+R_min;
C_new=C(end,:)+r*(R(end)+R_new+R_max*rand(1));
D=L - norm(C_new + r*(R_new+Rb) - Xa); % will there be enough space left for the end point with radius Rb?
if D<2*(R_min+1E-12)
C=cat(1,C,Xb);
R=cat(1,R,Rb);
break
else
C=cat(1,C,C_new);
R=cat(1,R,R_new);
end
end

  6 Comments

Code I posted above had some minor bugs. Attached is the final version of the code, free of bugs, and with improved boundary sampling.
Thanks, works perfectly. But if I add at the end the following code I write an external file having only the coordinate of the circle with x=0. How can I plot all the generated coordinates?
FileName=sprintf('%s%sRandom circle packing data.csv',cd,filesep);
csvwrite(FileName,[C R]);
fprintf('Data saved to %s\n',FileName)
If you have the Image Processing Toolbox,
viscircles(C, R)

Sign in to comment.


Answer by Walter Roberson
on 12 Jun 2018

How do you know when to give up on the random placement?
N = 500;
minr = 10; maxr = 50;
maxtries = 500000;
intcoords = false;
sq = zeros(N, N, 'uint8');
[X, Y] = ndgrid(1:N, 1:N);
nc = 0;
iteration = 0;
trynum = 0;
maxgoodtry = 0;
fmt = 'iteration #%d, nc = %d, try #%d';
fig = gcf;
set(fig, 'Units', 'pixels', 'Position', [0 0 N+30, N+30]);
image(sq);
colormap(jet(2))
axis([0 N+1 0 N+1]);
title(sprintf(fmt, iteration, nc, trynum));
drawnow();
rx = []; ry = []; rr = [];
while trynum <= maxtries
iteration = iteration + 1;
if intcoords
r = randi([minr, maxr]);
cxy = randi([r+1, N-r], 1, 2);
else
r = minr + rand(1,1) * (maxr-minr);
cxy = r + 1 + rand(1,2) * (N - 2*r - 1);
end
mask = (X-cxy(1)).^2 + (Y-cxy(2)).^2 <= r^2;
if nnz(sq & mask) > 0
trynum = trynum + 1;
else
sq = sq | mask;
image(sq);
nc = nc + 1;
rx(nc) = cxy(1); ry(nc) = cxy(2); rr(nc) = r;
title(sprintf(fmt, iteration, nc, trynum));
drawnow();
maxgoodtry = max(maxgoodtry, trynum);
trynum = 1;
end
end
fprintf('finished at iteration %d, hardest success took %d tries\n', iteration, maxgoodtry);
fprintf('Number of circles: %d\n', length(rx));

  6 Comments

In my testing, I found cases where locations could still be found after 350000 rejections.
The number of circles that can be packed with those radii is generally between 170 and 220, partly dependent upon how persistent you are.
I know a much more efficient method than I used above, but there is no point in implementing it until fundamental questions are answered:
  • are the coordinates of the circle centers intended to be integers or continuous?
  • are the radii intended to be integers or continuous?
  • The question states that overlap is not permitted, but is touching of circles permitted?
  • Is it okay to approximate whether a square is within a circle according to whether the center of the square is within the circle, or is it necessary to be more precise about it? Like if 1% of a square is theoretically occupied by a circle to its left, does that "consume" the whole circle because a small fraction of it is used, forbidding the case where a circle on its right also uses 1%? In this particular left/right example, the infinitely precise versions of the circles would not overlap, but clearly it is also possible for there to be cases where two circles overlap by just a sliver within a unit square, with neither one of them happening to pass over the center of the circle
  • Is it necessary to keep going until every gap is smaller than the minimum radius, to pack as densely as possible, even though a rejection method could take an indefinitely large amount of time to "randomly" locate the last few gaps?
  • Are there conditions on the ratio of circle radii? That is, as you place the larger circles, you quickly get to the point where large circles will no longer fit, but you might be able to fit four-ish times as many circles of half the radii. So if you pack as densely as possible, then a histogram of radii would be highly biased towards the smaller diameters. But some circle packing situations ask for fairly uniform distribution of radii, expecting you to stop when you can no longer keep the distribution relatively equal, even though that would leave gaps that could be filled by more smaller circles
  • some circle packing situations do not expect you to fill every possible gap, recognizing that random selection of coordinates might not be able to locate the gaps. But they do expect you not to give up immediately. If you are not expecting that every possible gap be filled, then how many tries of being rejected is "good enough" ?
1st,2nd point- the coordinates and radii can be continuous 3rd point- the touch is permitted 4th,5th,6th,7th point- I don't need a more precise code. It is already excellent for my goal. It doesn't matter if the filling is not so much accurate and remain some space.
I have extra requests if you can do it and I'm sorry if I do it just now.
Before creating circles on the surface, can I generate random circles also in the 4 corners and then on the 4 edges (having the center of the circle along the edge)?
Could it be possible to change the code to generalize it even in the case of a rectangular shape?
Generalization to rectangle, and also puts a circle in each corner and a circle on each of the four edges.
%M x N, height by width
M = 480;
N = 640;
minr = 10; maxr = 50;
maxtries = 500000;
sq = zeros(M, N, 'uint8');
[Y, X] = ndgrid(1:M, 1:N);
nc = 0;
iteration = 0;
trynum = 0;
maxgoodtry = 0;
fmt = 'iteration #%d, nc = %d, try #%d';
fig = gcf;
set(fig, 'Units', 'pixels', 'Position', [0 0 N+30, M+30]);
image(sq);
colormap(jet(2))
axis equal
axis([0 N+1 0 M+1]);
title(sprintf(fmt, iteration, nc, trynum));
drawnow();
rx = []; ry = []; rr = [];
while trynum <= maxtries
iteration = iteration + 1;
r = randin(minr, maxr);
switch nc
case 0
cx = 1; cy = 1;
case 1
cx = 1; cy = M;
case 2
cx = N; cy = 1;
case 3
cx = N; cy = M;
case 4
cx = randin(r, N-r);
cy = 1;
case 5
cx = randin(r, N-r);
cy = M;
case 6
cx = 1;
cy = randin(r, M-r);
case 7
cx = N;
cy = randin(r, M-r);
otherwise
cx = randin(r, N-r);
cy = randin(r, M-r);
end
mask = (X-cx).^2 + (Y-cy).^2 <= r^2;
if nnz(sq & mask) > 0
trynum = trynum + 1;
else
sq = sq | mask;
image(sq);
nc = nc + 1;
rx(nc) = cx; ry(nc) = cx; rr(nc) = r;
title(sprintf(fmt, iteration, nc, trynum));
drawnow();
maxgoodtry = max(maxgoodtry, trynum);
trynum = 1;
end
end
fprintf('finished at iteration %d, hardest success took %d tries\n', iteration, maxgoodtry);
fprintf('Number of circles: %d\n', length(rx));
And you will need
function r = randin(minval, maxval, varargin)
r = rand(varargin{:}) * (maxval - minval) + minval;
end
To reduce computation time, you can use a lower maxtries limit. In my tests, it sometimes takes over 390000 tries to randomly place a circle in one of the few remaining gaps.
Note: this code does not implement my improved algorithm at all.

Sign in to comment.


Answer by Anton Semechko on 12 Jun 2018
Edited by Anton Semechko on 12 Jun 2018

Here is a demo that uses rejection sampling and Delaunay triangulation
function [C,r]=random_circle_packing_demo
%
% - C : Q-by-2 array of sphere centroids
% - r : Q-by-1 array of sphere radii
%
% Problem settings
a=500; % size of the square
D_min=10; % min diameter of inscribed circle
D_max=50; % max diameter of inscribed circle
% Start by placing randomply spaced points along the boundary
d_min=D_min/a;
d_max=D_max/a;
d=d_max-d_min;
Xb=cell(4,1);
for i=1:4
t=[];
t_net=0;
while t_net<1
t=cat(1,t,d*rand(1)+d_min);
t_net=t_net+t(end);
end
t=t/t_net;
[t_min,id_min]=min(t);
while t_min<d_min
t_new=d*rand(1)+d_min;
if t_new>t_min
dt=t_new-t_min;
if t_new>t_min*(1+dt)
t(id_min)=t_new;
t=t/(1+dt);
[t_min,id_min]=min(t);
end
end
end
t=cat(1,0,t);
t(end)=[];
Xi=ones(numel(t),2);
if i==1
Xi(:,1)=a*cumsum(t);
Xi(:,2)=0;
elseif i==2
Xi(:,1)=a;
Xi(:,2)=a*cumsum(t);
elseif i==3
Xi(:,1)=a*(1-cumsum(t));
Xi(:,2)=a;
else
Xi(:,1)=0;
Xi(:,2)=a*(1-cumsum(t));
end
Xb{i}=Xi;
if i==1
figure('color','w')
axis equal
set(gca,'XLim',[0 a]+a*[-1/20 1/20],'YLim',[0 a]+a*[-1/20 1/20],'box','on')
hold on
drawnow
end
plot(Xi(:,1),Xi(:,2),'.k','MarkerSize',10)
end
Xb=cell2mat(Xb);
% Use rejection sampling to populate interior of the square
X=Xb;
D=D_max-D_min;
n=0; cnt=0;
while cnt<100 % terminate when no additional points can be inserted after 100 iterations
n=n+1;
%disp([n size(X,1) cnt])
% New point
X_new=a*rand(1,2);
% Randomly chosen distance threshold, D_thr, between D_min and D_max. The point
% process being simulated depends on how this parameter is chosen. If
% you want the spheres to be packed closer together, bias D_thr towards
% D_min.
D_thr=D*rand(1)+D_min;
% Reject new point if it is closer to X than D_thr
d_out=sum(bsxfun(@minus,X,X_new).^2,2);
if min(d_out)<D_thr^2
cnt=cnt+1;
continue
end
% Accept new point
cnt=0;
X=cat(1,X,X_new);
plot(X_new(:,1),X_new(:,2),'.k','MarkerSize',10)
if mod(n,10)==0, drawnow; end
end
% Delaunay triangulation
DT=delaunayTriangulation(X);
triplot(DT)
[C,r]=incenter(DT);
id=r<D_min/2 | r>D_max/2;
C(id,:)=[];
r(id)=[];
plot(C(:,1),C(:,2),'.r','MarkerSize',10)
N=size(C,1);
% Plot the spheres
figure('color','w')
axis equal
set(gca,'XLim',[0 a]+a*[-1/20 1/20],'YLim',[0 a]+a*[-1/20 1/20],'box','on')
hold on
t=linspace(0,2*pi,1E2)';
P=[cos(t) sin(t)];
for i=1:N
Pi=bsxfun(@plus,r(i)*P,C(i,:));
plot(Pi(:,1),Pi(:,2),'-k')
if mod(i,10)==0, drawnow; end
end

  4 Comments

Show 1 older comment
Change 100 to a bigger number to give it more trials to find a diameter that fits:
while cnt<100
Alternatively you could use the Euclidean Distance Transform to immediately locate where the largest circle that can fit would like. However computing the EDT does take some time so you wouldn't want to do it when the field is mostly empty but when you get to where you're rejecting a large number of circles before finding a "good" one, then it may be advantageous to use the EDT.
To better fill in the area, set 'D_thr' variable inside the while loop to D_min:
D_thr=D_min;
Simplest way to "export" results of the simulation is to call
[C,r]=random_circle_packing_demo;
from command window. Once the simulation is complete, right click on the 'C' variable (centroids) in the workspace, select "Copy", then paste "C" into spreadsheet. Repeat the same for 'r' variable (radii).
Actually, setting D_thr to D_min will not produce tighter packing of the circles. After sampling is completed I think that the Voronoi cells corresponding to circles with radii below D_min will have to be modified locally using Lloyd's relaxation algorithm to get tighter packing. I don't really have time to experiment with this. Maybe someone else on here can help you.

Sign in to comment.


Answer by Anton Semechko on 12 Jun 2018

Here is another implementation of random circle packing. This version produces much tighter packing than my previous demo thanks to Walter's idea of using a grid to keep track of unoccupied space inside the square.
function [C,R]=random_circle_packing_demo2
%
% - C : Q-by-2 array of sphere centroids
% - r : Q-by-1 array of sphere radii
%
% Problem settings
a=500; % size of the square
D_min=10; % min circle diameter
D_max=50; % max circle diameter
% Unit circle
t=linspace(0,2*pi,1E2)';
P=[cos(t) sin(t)];
% Sampling grid
x=linspace(0,a,2E3);
dx=x(2)-x(1);
[x,y]=meshgrid(x);
G=[x(:) y(:)];
clear x y
% Begin visualization
hf=figure('color','w');
axis equal
set(gca,'XLim',[0 a]+a*[-1/20 1/20],'YLim',[0 a]+a*[-1/20 1/20],'box','on')
hold on
drawnow
f=5:5:100;
fprintf('Progress : ')
fprintf(' %-3u ',f)
fprintf(' (%%complete)\n')
fprintf(' ')
f=size(G,1)-round((f/100)*size(G,1));
% Use rejection sampling to populate interior of the square
C=[]; R=[];
D=D_max-D_min;
flag=true;
n=0; cnt=0; m=0;
while ~isempty(G) && ishandle(hf)
n=n+1;
% New circle
if cnt>500, flag=false; end
if cnt<500 && flag
X_new=a*rand(1,2); % centroid
else
i=randi(size(G,1));
X_new=G(i,:)+(dx/2)*(2*rand(1,2)-1);
end
R_new=(D*rand(1)+D_min)/2; % radius
% Does the new circle intersect with any other circles?
if n>1
d_in=sqrt(sum(bsxfun(@minus,C,X_new).^2,2));
id=d_in<(R+R_new);
if sum(id)>0
cnt=cnt+1;
continue
end
end
% Accept new circle
cnt=0;
m=m+1;
C=cat(1,C,X_new);
R=cat(1,R,R_new);
G=update_grid(X_new,R_new,G,D_min/2);
% Visualization
if ishandle(hf)
Pm=bsxfun(@plus,R_new*P,X_new);
h=fill(Pm(:,1),Pm(:,2),'r');
set(h,'FaceAlpha',0.25)
if mod(m,10)==0, drawnow; end
end
% Progress update
if size(G,1)<=f(1)
f(1)=[];
fprintf('* ')
end
end
fprintf('\n')
if nargout<1
clear C R
end
function G=update_grid(X_new,R_new,G,R_min)
% Remove grid points within R_new+R_min units of new circle
D=sum(bsxfun(@minus,G,X_new).^2,2);
id=D<(R_new+R_min+1E-12)^2;
G(id,:)=[];

  10 Comments

Someone please could tell me how works the ishandle function, I don't undesrtand the matlab available explanation
ishandle(hf)
is testing to see whether hf is still a valid handle to something. The case where it would not be a valid handle to something is the case where somehow the figure has stopped existing, such as if the user clicked on the border X to close the figure while the code was running.
i want to change the rectangle to circle or semi-circle . . how to do that ?

Sign in to comment.


Answer by jahanzaib ahmad on 16 Feb 2019
Edited by jahanzaib ahmad on 16 Feb 2019

can some one do such packing with polygons ? without using delauny triagulation

  7 Comments

i m trying to fix polygons first i give them random position and then i check intersection if intersect then again i translate them to random position .if i increase the number of polygons the time is increase very much high . on the other hand thanslating them to +rand take them to (1,1) as translate function add to previous co-ordinates . i tried to translate them negative random number .but still i m not happy with this ..so futher sugestion required .plus i m beginner so i make code of everything instead of functions . .i m using polyxpoly function .
i m not trying to implement this paper but just for an idea .
There is a notable difference between what the paper talks about and what you are talking about. In the paper, they are permitted to rotate the object at need, but your requirements appear to be that the polygons are to be at random orientations. The algorithms in the paper are permitted to use heuristics and computations to figure out where to best put a piece, whereas your requirements appear to be that pieces are added at random locations if they fit.
The paper deals with packing algorithms. Your question appears to deal with a situation similar to if you were to pour a bunch of objects into a box, remove the ones that overlap something beneath it, pour those removed ones on top, remove the ones that overlap, and so on, until finally no more pieces can possibly fit.
yes.. Walter Roberson i cant see any material like polygon packing or random placement on mathworks .so i m doing that . i have made code just trying to improve it and i will post it ..
i m trying is randomly placing it and then checking overlap and placeing it to new position. but such a method is slow .can u please suggest any good way e.g i m trying now it that if a polygon has occupied some place in square i dont want to produce random number in that place so that new polygons has few chances to goto that place again so nimber of overlaps/intersections will reduce .? what do u say ? or any other method i can search for free space in a box and place new ploygono there in random way ?

Sign in to comment.


Answer by Mohammad Faris on 20 Feb 2019

Hey everybody.
i have some issue in 3d dimension
i wanna fill a cylinder with some spherical glasses. can we rework this method for 3d dimension?

  4 Comments

Show 1 older comment
i made this using random take and place method very conventional method .but computational time is very high .
1- generating
2-placing
3 finding interrsection
4 translating ( or rotating ) and again finding intersection
@ Walter Roberson i m trying this way to make polygons packing .generating a random centroid and making a convex polygon and then using scale function i place that polygon at that centroid position .and then generating till the required area percentage condition fullfilled .please guide me for improvement and i want to avoid polyxpoly function i think it make the code slow. 50 percent area is easy but 70 percent takes alot of time ..plus if there is intersection i m reducing the size of the polygon thats again not a good way because i want polygon between two min and max size .
to measure the size of the polygon i m using minboudrect funciton .(attached )
rA=0.5; % 50 percent area
m=1;
N=9;
x=rand; % random centroid x and y
y=rand;
X=rand(N,2);
XX=X(:,1);
XY=X(:,2);
K=convhull(XX,XY);
AB=[XX(K),XY(K)];
polyin = polyshape(AB);
seivesize=[4.75 9.5]; % reuired size of polygon
D=(seivesize(1)+((seivesize(2)-(seivesize(1))).*rand))/100; % random size of polygon
[rx,ry] = minboundrect(AB(:,1),AB(:,2));
side1=sqrt(((rx(1)-rx(2))^2)+(ry(1)-ry(2))^2);
side2=sqrt(((rx(2)-rx(3))^2)+(ry(2)-ry(3))^2);
sizeofpolygons1=min(side1,side2);
FACTOR=D/sizeofpolygons1; % reducing the size of the polygon by factor
poly1 = scale(polyin,FACTOR,[x,y]);
%plot(poly1);
area2=area(poly1);
AC=[poly1.Vertices(:,1),poly1.Vertices(:,2);poly1.Vertices(1,1),poly1.Vertices(1,2)];
A{m}=AC;
rA=rA-area2; Sarea=0;
%m=m+1;
while rA >= area2
chk3=1;
while (chk3)~=0
x=rand;
y=rand;
P=[x,y];
chk2=[];
for i=1:length(A)
AD=A{i};
AD1=polyshape(AD);
chk1=isinterior(AD1,P);
chk2=[chk2,chk1];
end
chk3=any(chk2);
end
N=9;
X=rand(N,2);
XX=X(:,1);
XY=X(:,2);
K=convhull(XX,XY);
AB=[XX(K),XY(K)];
polyin = polyshape(AB);
seivesize=[4.75 9.5];
D=(seivesize(1)+((seivesize(2)-(seivesize(1))).*rand))/100;
[rx,ry] = minboundrect(AB(:,1),AB(:,2));
side1=sqrt(((rx(1)-rx(2))^2)+(ry(1)-ry(2))^2);
side2=sqrt(((rx(2)-rx(3))^2)+(ry(2)-ry(3))^2);
sizeofpolygons1=min(side1,side2);
FACTOR=D/sizeofpolygons1;
poly1 = scale(polyin,FACTOR,[x,y]);
%area1=area(poly1);
AC=[poly1.Vertices(:,1),poly1.Vertices(:,2);poly1.Vertices(1,1),poly1.Vertices(1,2)];
for j=1:length(A)
AF=A{j};
[Cx,Ca] = polyxpoly(AF(:,1), AF(:,2),AC(:,1),AC(:,2));
while ~isempty(Cx)
polyin1 = polyshape(AC);
FACTOR1=.9;
poly1 = scale(polyin1,FACTOR1,[x,y]);
AC=[poly1.Vertices(:,1),poly1.Vertices(:,2);poly1.Vertices(1,1),poly1.Vertices(1,2)];
[Cx,Ca] = polyxpoly(AF(:,1), AF(:,2),AC(:,1),AC(:,2));
end
end
m=m+1;
A{m}=AC;
polyin1 = polyshape(AC);
area2=area( polyin1);
Sarea=Sarea+area2;
rA=rA- area2;
end
axis equal
axis([-0.1 1.1 -0.1 1.1]);
figure(2);
for i =A
plot(i{:}(:,1), i{:}(:,2),'k');
hold on;
end

Sign in to comment.