MATLAB: Improve algorithm to fill a rectangle with given number of points

pointsrandomscatter

I have a working code but it´s taking too long if I change some of the parameters. The goal is to fill a rectangle of given size with a given number of points (NumLigands) and a distance restraint between them (LigSpace). Here it is:
tic
W = 200 ;    % Angstrom

H = 200 ;    % Angstrom
dx = 1 ;     % Resolution in x axis
dy = 1 ;     % Resolution in y axis
X = [0:dx:W]' ; % Set of coordinates in x axis
Y = [0:dy:H]' ; % Set of positions in y axis
Area = W*H/10^2 ;    % in nm2
density = 2.67 ;     % #/nm2
NumLigands = density * Area ;
LigSpace = 7.11 ;       % Ligand spacing
keepP(1,:) =  [randsample(X,1) ; randsample(Y,1)]' ;      % Fix this point
add = 2 ;
while add <= NumLigands
    newP = [randsample(X,1) ; randsample(Y,1)]' ;       % try a new point
     %Calculate distance to other points
     Distance = sqrt( (newP(1,1) - keepP(:,1)).^2 + (newP(1,2) - keepP(:,2)).^2 ) ;
     minDistance = min(Distance) ;
     if minDistance > normrnd(LigSpace,1)
         keepP(add,:) = newP ;
              figure(1);plot(keepP(add,1),keepP(add,2),'g*')
              xlim = [0 200];
              ylim = [0 200];
              hold on
         add = add + 1 ;
     end
  end
  toc
With these parameters it takes about 2 min in my computer, which is not too bad, but if I change something like increasing the number of points or reducing the distance constraint it can take up to 10 minutes or more.
I want to keep the positioning of ligands randomly, but is there an heuristic I could use to reduce the computation time? Thanks!

Best Answer

This is 3x faster on my machine.
Your version took 64 sec and the version below takes 21 sec. I made several changes. The biggest change was moving all of the plotting outside of the while-loop. This means you won't be able to see the plot update during the loop but it's a lot faster. I also allocated 'keepP', combined your 'distance' and 'minDistance' lines, and made other smaller changes. Due to the use of random numbers and random permutations, I didn't reduce the while-loop any further.
tic
W = 200 ;    % Angstrom

H = 200 ;    % Angstrom
dx = 1 ;     % Resolution in x axis
dy = 1 ;     % Resolution in y axis
X = (0:dx:W)' ; % Set of coordinates in x axis
Y = (0:dy:H)' ; % Set of positions in y axis
Area = W*H/10^2 ;    % in nm2
density = 2.67 ;     % #/nm2
NumLigands = density * Area ;
LigSpace = 7.11 ;       % Ligand spacing
keepP = NaN(NumLigands, 2); %allocate!
keepP(1,:) =  [randsample(X,1) ; randsample(Y,1)]' ;      % Fix this point
add = 2 ;
while add <= NumLigands
    newP = [randsample(X,1) ; randsample(Y,1)]' ;       % try a new point
    %Calculate distance to other points
    minDistance = min(sqrt( (newP(1,1) - keepP(:,1)).^2 + (newP(1,2) - keepP(:,2)).^2 )) ;
    if minDistance > normrnd(LigSpace,1)
        keepP(add,:) = newP ;
        add = add + 1; 
    end
end
figure(1);
plot(keepP(2:end,1),keepP(2:end,2),'g*')
xlim = [0 200];
ylim = [0 200];
toc
Related Question