Improve algorithm to fill a rectangle with given number of points
5 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
Eugenio Gil
il 15 Ago 2018
Commentato: Eugenio Gil
il 20 Ago 2018
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!
2 Commenti
dpb
il 15 Ago 2018
Modificato: dpb
il 15 Ago 2018
What's the density of points? I wonder if one were to start with array at the allowed spacing (with a random offset by row/column initially so aren't exactly uniform) and then, instead of generating N, randomly purge M, leaving N? You'd start of with the constraint being satisfied.
Just a thought, not sure how well it might suit needs...
Risposta accettata
Adam Danz
il 15 Ago 2018
Modificato: Adam Danz
il 15 Ago 2018
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
10 Commenti
Adam Danz
il 20 Ago 2018
If you don't want replacement, either use randsample() to create the entire vector of samples or use randperm which might be better. Just note that you can only create as many samples are there are data in X,Y.
Più risposte (0)
Vedere anche
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!