Create random points in a rectangular domain, but with minimum separation distance

Hello,

I am not a regular user of this program. Hence this query.

I am interested to create random points in a 2D rectangular space, to start with, a uniform distribution. I know how to do this. However, I want to ensure that each of these points are separated by a certain minimum distance.

Can anyone help me with the script please.

Thank you.

Suresh

Answer 1

[Image Analyst]

You basically have to try and see. If it's too close, reject that point and get a new one.

x = rand(1, 10000);
y = rand(1, 10000);
minAllowableDistance = 0.05;
numberOfPoints = 300;
% Initialize first point.
keeperX = x(1);
keeperY = y(1);
% Try dropping down more points.
counter = 2;
for k = 2 : numberOfPoints
  % Get a trial point.
  thisX = x(k);
  thisY = y(k);
  % See how far is is away from existing keeper points.
  distances = sqrt((thisX-keeperX).^2 + (thisY - keeperY).^2);
  minDistance = min(distances);
  if minDistance >= minAllowableDistance
    keeperX(counter) = thisX;
    keeperY(counter) = thisY;
    counter = counter + 1;
  end
end
plot(keeperX, keeperY, 'b*');
grid on;

[SS]

Hi,

Thanks a lot. This is perfect. You have saved a lot of my time. I see the trick was in the variable "distances", where you have performed vector operation. This is something I did not know and I was doing it point by point, which was ridiculous.

If you don't mind extending your help again, what I was finally interested is to draw randomly (e.g. uniform distribution of angle theta, randomly varying between 0 to 180 degrees) inclined line segments (of fixed length and also if possible variable length, in which case the variable length follows some distribution) through these random points, these points acting as the center of the line segments.

Suresh

[Image Analyst]

See this code:

% Creates a random pattern of points with no point closer to another than some specified distance.
% Also puts a ray emanating from each point at random angle and random length.
% Initialize some things.
x = rand(1, 10000);
y = rand(1, 10000);
minAllowableDistance = 0.05;
numberOfPoints = 300;
rMax = 0.25;
% Initialize first point.
keeperX = x(1);
keeperY = y(1);
% Try dropping down more points.
counter = 2;
for k = 2 : numberOfPoints
  % Get a trial point.
  thisX = x(k);
  thisY = y(k);
  % See how far is is away from existing keeper points.
  distances = sqrt((thisX-keeperX).^2 + (thisY - keeperY).^2);
  minDistance = min(distances);
  if minDistance >= minAllowableDistance
    keeperX(counter) = thisX;
    keeperY(counter) = thisY;
    % Draw a line from it.
    % First get a random angle
    angle = 2*pi*rand(1);
    % Next get a random length
    r = rMax * rand(1);
    % Now get endpoint of the ray.
    x2 = thisX + r * cos(angle);
    y2 = thisY + r * sin(angle);
    % Plot the point
    plot(keeperX(counter), keeperY(counter), 'bo', 'LineWidth', 3);
    hold on;
    % Draw the line.
    line([thisX x2], [thisY, y2], 'Color', 'r', 'LineWidth', 3);
    counter = counter + 1;
  end
end
grid on;
% Enlarge figure to full screen.
set(gcf, 'Units', 'Normalized', 'OuterPosition', [0 0 1 1]);

[SS]

Hi,

Once again, perfect and exactly what I wanted. In the meantime, I achieved the same as above but through another approach, wherein I solved an equation of a line and a circle with the random points acting as the centre of a circle and the line passing through the centre. But I like your approach the most.

Thank you for taking time to help me. Much appreciated.

S

[Prashant Katiyar]

Is there anyway we can replace points to small circles of variable diameters? Also if we can variate the distance between each of these circles? Some thing like below?

[William Harvie]

ngl this is probably the least effecient way to do this but it works

[Image Analyst]

@William Harvie, please post a more efficient way to do it if you know of one.

@Prashant Katiyar, try this:

%============================================================================================================================================
% Initialization Steps.
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 long g;
format compact;
fontSize = 25;
% Get a list of trial (x,y) circle centers.
x = 100 * rand(1, 1000000);
y = 100 * rand(1, 1000000);
% Specify how many circles are desired.
numberOfCircles = 300;
minRadius = 1;
maxRadius = 5;
% Specify how close the centers may be to each other.
% Should be at least twice the max radius if they are not to touch.
minAllowableDistance = max([11, 2 * maxRadius]);
% Initialize first point.
keeperX = x(1);
keeperY = y(1);
radii = minRadius;
% Try dropping down more points.
counter = 2;
for k = 2 : length(x)
    % Get a trial point.
    thisX = x(k);
    thisY = y(k);
    % See how far is is away from existing keeper points.
    distances = sqrt((thisX-keeperX).^2 + (thisY - keeperY).^2);
    minDistance = min(distances);
    if minDistance >= minAllowableDistance
  	  % This trial location works.  Save it.
      keeperX(counter) = thisX;
      keeperY(counter) = thisY;
  	% Get a random radius.
    radii(counter) = minRadius + (maxRadius - minRadius) * rand;
    % Quit if we have enough or ran out of circles to try
    if counter >= numberOfCircles
        break;
    end
    counter = counter + 1;
    end
end
% Plot a dot at the centers
plot(keeperX, keeperY, 'b+', 'MarkerSize', 9);
viscircles([keeperX(:), keeperY(:)], radii, 'Color', 'b');
grid on;
axis equal
numCirclesPlaced = length(keeperX);
caption = sprintf('Could place %d circles', numCirclesPlaced);
title(caption, 'fontSize', fontSize)
g = gcf;
g.WindowState = 'maximized'

[Joan]

@Image Analyst, thank you very much for your code. It is showing me some direction. However, I am a bit stuck. Please add some code that would make the circles enclosed inside a polyshape of coordinates say,

xv=[0 0 20 35 66 85 105 105]; % X-Coordinates

yv=[0 20 20 40 40 20 16 0]; % Y-Coordinates

Answer 2

[SS]

Hi,

If I may bother you once again please. I am looking to generate random ellipsoids in a cube, given the volume fraction of ellipsoids (say 40%), non-overlapping (can touch), and they must follow certain particle size distribution. One instance could be, 60% of 2mm, 20% of 4 mm, 15% of 8 mm and 5% of size 16 mm. These sizes (2mm, 4 mm...) are the lengths of the largest semi-principal axes.

Thank you for your time.

S

[Image Analyst]

I suggest you post this in a brand new question. But try the ellipsoid function first using the "try and keep/reject" concept. If you can't get it working, post your code in a new question since it's a different topic than this one.

Answer 3

[SS]

Hi,

Thank you, I have posted it as a separate question. Thank you for the hint, in the meantime, I am also trying.

S

[Image Analyst]

Yeah but I see you didn't take my advice, so expect a lot of questions like "Do the axes of the ellipsoids have to align with the xyz axes?", "What have you tried?", "Have you seen the ellipsoid function?", "Is this a homework problem?", and so on.

[SS]

Hi,

I take your point. Once I formulate the code, I will put it up in the discussions. The idea for posting in advance was to know if someone has already done it.

There should be six degrees of freedom (three rotations and three axes). Indeed I was looking at ellipsoid function, where in I use random function for all the six variables. I am figuring out the best way to determine minimum distance, placing the particles, etc. not yet there. It is not a homework problem, but needed for a small element of my own research work.

Thanks again. S