inter distance between point to be more than a certain number

Hi, I want to randomnly deploy points on region. The randomn deployment should continue until the points are at a certain distance apart (say >=20m) to all other points.

I used the code below, but the code only ensures adjacent points are >=20m. i.e distance (point 1 to point 2)>=20, distance (point 2 to point 3)>=20 etc.

BUT

I want distance from piont 1 to all other point >=20, same applies to point 2,3 and 4.

n=4;  % number of ponts
 x.ev=randperm(100,n); % x coordinate of point
 y.ev=randperm(100,n);%  y coordinate of point

 for i= 2:1:n;
    d.you(i)=sqrt( (x.ev(i)-x.ev(i-1)).^2 + (y.ev(i)-y.ev(i-1)).^2 );                         % calculate inter-distance btw points starting from the second point
 end
 d.you(1)=sqrt( (x.ev(1)-x.ev(n)).^2 + (y.ev(1)-y.ev(n)).^2 );                    % distance from the last to the fist point.
 
q=2;
while (d.you(q)-d.you(q-1)>=20) & (d.you(q)-d.you(q+1)>=20) 
  
    x.ev=randperm(100,n);
    y.ev=randperm(100,n);
   
    d.you(q)=sqrt( (x.ev(q)-x.ev(q+1)).^2 + (y.ev(q)-y.ev(q+1)).^2 );
     q=q+1;
    
end
%display(d.you)
plot(x.ev, y.ev, 'ok')

Pls, help

[Jan]

I'm not sure, what this means: "The randomn deployment should continue until the points are at a certain distance apart (say >=20m) to all other points."

Is there an lower and upper limit for the values? Is the problem solved, if you have found 2 points with >= 20?

[Shamsuddeen Abdullahi]

[Shamsuddeen Abdullahi]

the randomn deployment should continue until the points are at least 20m apart from each other as depicted in the above figure

[Jan]

It is confusing, that you mix 10, 20, meters and centimeters.

The definition is still not clear: Two points at [0,0] and [20,0] satisfy "the points are at least 20m apart from each other" already. So is the problem solved as soon as you have 2 points? In your code the detail "n=4" occurs. So do you have a fixed number of points?

Are the positions limited? Otherwise you could simply determine n random points and multiply the all positions such, that the minimal distance is 20.

[Shamsuddeen Abdullahi]

Sorry, I mean 20m . in a 100m by 100 field, I simly want to deploy a fixed number of points (say 4) such that inter distances of all points to all other points is atleast 20m.

[Shamsuddeen Abdullahi]

the deployment needs to be at random

[Jan]

Okay, than simply use my code:

[X, Y] = GetPointsRandom(4, 100, 100, 20)

Answer 1

[Image Analyst]

You can try my demo, that I've posted before. It's a pretty simple "try and reject or accept" method, but it's intuitive and well commented. Adapt as needed:

clc;    % Clear the command window.
close all;  % Close all figures (except those of imtool.)
clear;  % Erase all existing variables. Or clearvars if you want.
workspace;  % Make sure the workspace panel is showing.
format short g;
format compact;
fontSize = 20;

% Define how many points you want to place.
maxPoints = 500;
% Define counter for how many actually get placed.
numberOfPoints = 0;
% Define fail safe, how many iterations you want to keep trying before quitting.
maxIterations = 1000 * maxPoints;
loopCounter = 1;
% Define how close points can come to other points before being rejected.
minClosestDistance = 0.1;
% Declare arrays to hold the x and y coordinate values.
x = nan(1, numberOfPoints);
y = nan(1, numberOfPoints);
while numberOfPoints < maxPoints && loopCounter < maxIterations
	% Get a random point.
	xPossible = rand();
	yPossible = rand();
	if numberOfPoints == 0
		% First point automatically is valid.
		numberOfPoints = numberOfPoints + 1;
		x(numberOfPoints) = xPossible;
		y(numberOfPoints) = yPossible;
		continue;
	end
	% Find distances between this point and all others.
	distances = sqrt((x-xPossible) .^ 2 + (y - yPossible) .^ 2);
	if min(distances) >= minClosestDistance
		% It's far enough away from all the other points, or it's the first point.
		% Include it in our list of acceptable points.
		numberOfPoints = numberOfPoints + 1;
		x(numberOfPoints) = xPossible;
		y(numberOfPoints) = yPossible;
	end
	% Increment the loop counter.
	loopCounter = loopCounter + 1;
end
% Crop away points we were not able to get.
x = x(1:numberOfPoints); % Crop to valid points.
y = y(1:numberOfPoints); % Crop to valid points.
% Plot the points we were able to get.
plot(x, y, 'b.', 'MarkerSize', 15);
grid on;
xlabel('X', 'FontSize', fontSize);
ylabel('Y', 'FontSize', fontSize);
caption = sprintf('Demo of Placing %d Random Points with Min Distance of %.2f', numberOfPoints, minClosestDistance);
title(caption, 'FontSize', fontSize);

% Set up figure properties:
% Enlarge figure to full screen.
set(gcf, 'Units', 'Normalized', 'OuterPosition', [0 0 1 1]);
% Get rid of tool bar and pulldown menus that are along top of figure.
% set(gcf, 'Toolbar', 'none', 'Menu', 'none');
% Give a name to the title bar.
set(gcf, 'Name', 'Demo by ImageAnalyst', 'NumberTitle', 'Off') 

% Tell user what we were a ble to achieve.
message = sprintf('Found %d points in %d tries', numberOfPoints, loopCounter)
helpdlg(message);

[Shamsuddeen Abdullahi]

[Shamsuddeen Abdullahi]

This is a sample for certain parameters. maximum value for x-axis is 1.5, while that of y axis is 2. I want the total size of region to be 100 by 100, i.e x-axis=100 in length, y-axis =100 in length

[Image Analyst]

I guess I don't understand. So when I asked you to adapt my code by plugging in your numbers, and you put in

maxPoints = 4;

minClosestDistance = 20;

xPossible = 100 * rand();

yPossible = 100 * rand();

Are you saying it didn't work and you did NOT get something like this?

I don't see a question in your comment but I'm assuming it didn't work for you, so I'm attaching a working example ("test3.m"), at least what I think "works". Let's figure out why your adapted code didn't work. Please attach the code of mine where you put in the right parameters and I'll get it fixed.

[Shamsuddeen Abdullahi]

Thank u very much. it is working

Answer 2

[Jan]

I'm not sure if this helps. It finds nWant random points inside [XWidth, YWidth] with a minimum distance between all points.

function [X, Y] = GetPointsRandom(nWant, XWidth, YWidth, Dist)
X       = zeros(nWant, 1);
Y       = zeros(nWant, 1);
Dist2   = Dist ^ 2;     % Squared once instead of SQRT each time
iLoop   = 1;            % Security break to avoid infinite loop
nValid  = 0;
while nValid < nWant && iLoop < 1e6
  newX = randi(XWidth);
  newY = randi(YWidth);
  if all(((X(1:nValid) - newX).^2 + (Y(1:nValid) - newY).^2) > Dist2)
    % Success: The new point does not touch existing points:
    nValid    = nValid + 1;  % Append this point
    X(nValid) = newX;
    Y(nValid) = newY;
  end
  iLoop = iLoop + 1;
end

% Stop if too few values have been found:
if nValid < nWant
  error('Cannot find wanted number of points in %d iterations.', iLoop)
end
end

This checks for each new point, if it is far enough from all existing points.

The method uses a limit for the number of iterations. If the density is too high, it will fail because the random search cannot find valid locations anymore. If you need high densities, you need a constructive method instead of this simple rejection approach.