Pseudo-random distribution of points with minimum distance

Question

Florian 2019-3-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453169-pseudo-random-distribution-of-points-with-minimum-distance

编辑： Bruno Luong 2021-5-20

采纳的回答： Torsten

在 MATLAB Online 中打开

Hi all,

I use the following code to generate an exact number of points (650 in this case) within a one hectar area:

numPoints = 650; % number of points to be generated
width = 100; % length in m of one square side
x = 0;
y = 0;
figure('Position', [300 300 900 900])
rectangle('Position', [x, y, width, width],'LineWidth',2,'LineStyle','--');
grid on;
hold on;
xRandom = 50 + (width * rand(1, numPoints) - width / 2);
yRandom = 50 + (width * rand(1, numPoints) - width / 2);
plot(xRandom, yRandom, 'b.', 'MarkerSize', 8);
hold on;
plot(xRandom, yRandom, 'ro', 'MarkerSize', 20);
title(['',num2str(numPoints),' points inside one hectar'], 'Interpreter', 'None');
xlabel('length in meters');
ylabel('length in meters');
axis equal tight;

What I would like to achieve is that the minimum distance between these points is 3 meters. This condition is fulfilled if the red circles (with 3 m diameter - only approximated here using MarkerSize) only touch each other but don't overlap as they currently do (see image below).

Does anybody know how to accomplish this?

PS: at a completely regular spacing of 650 points in one hectar there would be 4 m distance between each point. Maybe a possible solution would be to create a regular spacing first and then add or substract a smaller random increment?

3 个评论
显示 1更早的评论隐藏 1更早的评论

Florian 2019-3-28

编辑：Florian 2019-3-28

I need to end up with the exact number, so eliminating offenders (as proposed in previous solutions) is not an option. Maybe 'rand' is not the best function to start with...

James Tursa 2019-3-28

I wasn't suggesting eliminating the offenders, but pushing them away from each other until they are not offending anymore.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Torsten 2019-3-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453169-pseudo-random-distribution-of-points-with-minimum-distance#answer_368079

See Bruno Luong's code under

https://de.mathworks.com/matlabcentral/answers/432516-model-of-a-crowd-on-concert-venue-or-how-to-distribute-random-points-according-to-the-2d-window-dist

6 个评论
显示 4更早的评论隐藏 4更早的评论

Bruno Luong 2019-3-29

编辑：Bruno Luong 2019-9-26

在 MATLAB Online 中打开

For reference I put here the code with uniform distribution

L = 100; % <-- Choose length of square sides
x0 = 0; y0 = 0; % <-- Choose center of square
n = 300; % <-- Choose number of points
% Generate uniform-distribution on the square
X = rand(n,2)*L - (L/2*[1,1]+[x0,y0]);
XYR = [x0,y0]+[[-1;1;1;-1;-1],[-1;-1;1;1;-1]]*L/2;
XB = interp1((0:4)'*L,XYR,linspace(0,4*L,200));
XB(end,:) = [];
nrepulsion = 500;
% Repulsion of seeds to avoid them to be too close to each other
n = size(X,1);
Xmin = [x0-L/2,y0-L/2];
Xmax = [x0+L/2,y0+L/2];
% Point on boundary
XR = x0+[-1,1,1,-1,-1]*L/2;
YR = y0+[-1,-1,1,1,-1]*L/2;
cla;
hold on
plot(XR,YR,'r-');
h = plot(X(:,1),X(:,2),'b.');
axis equal
dmin = 3; % minima distance between 2 objects
d2min = dmin*dmin;
beta = 0.5;
for k = 1:nrepulsion
    XALL = [X; XB];
    DT = delaunayTriangulation(XALL);
    T = DT.ConnectivityList;
    containX = ismember(T,1:n);
    b = any(containX,2);
    TX = T(b,:);
    [r,i0] = find(containX(b,:));
    i = mod(i0+(-1:1),3)+1;
    i = TX(r + (i-1)*size(TX,1));
    T = accumarray([i(:,1);i(:,1)],[i(:,2);i(:,3)],[n 1],@(x) {x}); 
    maxd2 = 0;
    R = zeros(n,2);
    move = false(n,1);
    for i=1:n
        Ti = T{i};
        P = X(i,:) - XALL(Ti,:);
        nP2 = sum(P.^2,2);
        if any(nP2<4*d2min)
            move(i) = true;
            move(Ti(Ti<=n)) = true;
        end
        maxd2 = maxd2 + mean(nP2);
        b = Ti > n;
        nP2(b) = nP2(b)*5; % reduce repulsion from each point of the border
        R(i,:) = sum(P./max((nP2-d2min),1e-3),1);
    end
    if ~any(move)
        break
    end  
    if k==1
        v0 = (L*5e-3)/sqrt(maxd2/n);
    end
    R = R(move,:);
    v = v0/sqrt(max(sum(R.^2,2)));
    X(move,:) = X(move,:) + v*R;
    
    % Project back if points falling outside the rectangle
    X = min(max(X,Xmin),Xmax);
    
    set(h,'XData',X(:,1),'YData',X(:,2));
    pause(0.01);
end
theta = linspace(0,2*pi,65);
xc = dmin/2*sin(theta);
yc = dmin/2*cos(theta);
% plot circles f diameter dmin around random points
for i=1:n
    plot(X(i,1)+xc,X(i,2)+yc,'k');
end

Florian 2019-3-31

Perfect. Thanks Bruno!

请先登录，再进行评论。

Answer 2

Image Analyst 2019-3-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/453169-pseudo-random-distribution-of-points-with-minimum-distance#answer_368017

random_min_spacing.m

See my attached demo that I've posted before.

10 个评论
显示 8更早的评论隐藏 8更早的评论

Image Analyst 2021-5-19

在 MATLAB Online 中打开

With a Gaussian distribution, and a finite number of samples drawn from it, it's certainly possible to not encounter any negative values. For example if the mean were 10 and the SD were 0.5 and you drew 10 thousand samples, it's possible that none of those 10,000 numbers would be negative.

% Get 10 thousand numbers from a Gaussian Distribution
r = 10 + 0.5 * randn(10000, 1);
% Find out what the min and max are
fprintf('Min r = %f\nMax r = %f\n', min(r), max(r));
fprintf('Mean r = %f\nStd Dev r = %f\n', mean(r), std(r));
% Fit data, r, to a Gaussian/Normal distribution 
% even though there are no negative numbers.
pd = fitdist(r, 'Normal')

Min r = 7.783199

Max r = 12.011163

Mean r = 10.002350

Std Dev r = 0.497673

pd =

Normal distribution

mu = 10.0011 [9.99139, 10.0108]

sigma = 0.495396 [0.488625, 0.502359]

That said @Jeroen Houwen, looking at my Fry Plot demo below you can see the distribution for distances bounded in a rectangle looks more log normal than normal.

Bruno Luong 2021-5-20

编辑：Bruno Luong 2021-5-20

"With a Gaussian distribution, and a finite number of samples drawn from it, it's certainly possible to not encounter any negative values."

Fine but that has nothing to do my comment, which is one can NEVER generate a Gaussian random distribution with a positive values. I'm not talking about the reverse.

请先登录，再进行评论。