Distribute points evenly in rectangle

Hey guys, I'm trying to tackle the next problem: I have a rectangle with known dimensions and I need to distribute n points inside of it randonmly, but evenly. By evenly I mean that there must be some minimum (or even constant) distance between the points. After some search on the internet I haven't found some algorithm that helps me with this problem. Would appreciate some insights.

Thanks in advance.

Answer 1

[Walter Roberson]

https://www.mathworks.com/matlabcentral/answers/142322-find-n-random-points-with-a-minimum-distance-r-inside-a-2d-rectangular-box

Answer 2

[Image Analyst]

Did you try to write it yourself? It's not hard. Just get a point and see if it's too close to any prior points. If it's not too close, then place it. This code works.

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.
numPoints = 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, numPoints);
y = nan(1, numPoints);
while numPoints < maxPoints && loopCounter < maxIterations
  % Get a random point.
  xPossible = rand();
  yPossible = rand();
  if numPoints == 0
    % First point automatically is valid.
    numPoints = numPoints + 1;
    x(numPoints) = xPossible;
    y(numPoints) = 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.
    numPoints = numPoints + 1;
    x(numPoints) = xPossible;
    y(numPoints) = yPossible;
  end
  % Increment the loop counter.
  loopCounter = loopCounter + 1;
end
% Crop away points we were not able to get.
x = x(1:numPoints); % Crop to valid points.
y = y(1:numPoints); % 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);
title('Demo by Image Analyst', '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', numPoints, loopCounter)
helpdlg(message);

Bonus challenge for you: construct the "Fry plot" of it. Compare its Fry plot to that of a Poisson distribution, and of an aggregated distribution.

[Walter Roberson]

As you get closer to the "carrying capacity" of the rectangle then you can run into problems.

[Image Analyst]

Good point that can't be overemphasized enough. That's why all my while loops have a failsafe where I check to make sure the number of interations doesn't approach infinity. So my while checks loopCounter < maxIterations to prevent an infinite loop. As the plane gets filled up with dots, it will become harder and harder to find a point that will fit, and at some point it will become impossible, hence the importance, no - the necessity - of having a failsafe.

[victor isarov]

Hey Image Analyst, Thank you for your answer. Yes, I have tried it myself. However, I need an efficient solution for this problem as it is going to be part of a program. And to generate points until it answers the criteria (especially if I need constant distance) seems inefficient solution.

[Walter Roberson]

In a 2D rectangle, the maximum number of points that can be at constant distance from each other is 3.

[Image Analyst]

So just get the location of the first point at random, and use simple trig formulas to get the location of the second point, which can be at a random or specified angle to the first.

If you need a third point, again it's simple trig to find the location of the third point. If the third point is outside the rectangle, flip it on the other side of the line between the first two so that it lands inside the rectangle.

Like Walter said, there will be no solution if your number criteria is anything other than 2 or 3.

If you are going to allow non-uniform spacing, then just how many points were you planning on placing? If it's just a few thousand, perhaps less than a million, the code I gave is pretty fast - the smaller the min spacing the faster it will be since there will be fewer "rejects". A faster way would be to generate the points on a perfectly regular rectangular grid, and then just generate perturbations - delta X's and delta Y's - to slightly move each point. Kind of like Perlin Noise, if you're familiar with that.