Clear Filters
Clear Filters

inter distance between point to be more than a certain number

4 views (last 30 days)
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.
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; (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 (x.ev(1)-x.ev(n)).^2 + (y.ev(1)-y.ev(n)).^2 ); % distance from the last to the fist point.
while (>=20) & (>=20)
y.ev=randperm(100,n); (x.ev(q)-x.ev(q+1)).^2 + (y.ev(q)-y.ev(q+1)).^2 );
plot(x.ev, y.ev, 'ok')
Pls, help
Jan on 10 May 2019
Okay, than simply use my code:
[X, Y] = GetPointsRandom(4, 100, 100, 20)

Sign in to comment.

Accepted Answer

Image Analyst
Image Analyst on 10 May 2019
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;
% 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;
% Increment the loop counter.
loopCounter = loopCounter + 1;
% 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)
Image Analyst
Image Analyst on 11 May 2019
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?
0001 Screenshot.png
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.

Sign in to comment.

More Answers (1)

Jan on 10 May 2019
Edited: Jan on 10 May 2019
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;
iLoop = iLoop + 1;
% Stop if too few values have been found:
if nValid < nWant
error('Cannot find wanted number of points in %d iterations.', iLoop)
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.


Find more on Entering Commands in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!