3

I have to create highway scenario in MATLAB. I have to generate random points (i.e. vehicles) on highway. By using randn() command, random points are overlapping on each other. I want to generate random points such that a minimum distance between random points is maintained.

Could anybody help me in generating this kind of scenario..

Daniel
  • 36,610
  • 3
  • 36
  • 69
reena
  • 55
  • 4
  • For R² I am not aware of any approach better than [rejection sampling](https://en.wikipedia.org/wiki/Rejection_sampling) if you want to maintain a pure uniform distribution. Is a uniform distribution required? How large is your scenario? For large scenarios rejection sampling might be to slow. – Daniel Sep 27 '15 at 20:03
  • Scenario: A highway of length L (L value can vary from 3000 m to 10,000 m). Highway can have multiple lanes. I have to generate vehicles randomly on highway so that minimum distance between two vehicles is maintained. Number of vehicles can vary from 10 to 500. I think vehicles will be distributed uniformly. If we can use some other distribution for vehicles, please tell me. – reena Sep 28 '15 at 04:18

2 Answers2

2

You might consider Poisson disc (a.k.a. disk) sampling. Basically, Poisson-disc sampling produces points that are tightly-packed, but no closer to each other than a specified minimum distance, resulting in a more natural pattern.

My matlab is rusty, sorry, no code, but links

http://www.cs.sandia.gov/~samitch/papers/cccg-present.pdf

https://www.jasondavies.com/poisson-disc/

Severin Pappadeux
  • 18,636
  • 3
  • 38
  • 64
  • That's probably the way to go for very large problems. – Daniel Sep 27 '15 at 20:36
  • @severin: Danial is right.Poisson disk is for large problems. I tried poisson disk given on link http://cusacklabcomputing.blogspot.ca/2013/07/poisson-disc-2d-in-matlab.html. Its generating large numbers which i dont need. I need to vary numbers of vehicles keeping simulation area constant. – reena Sep 28 '15 at 04:06
1

This is not an elegant solution, but it satisfies your minimum distance constraint.

% Highway dimensions
lx = 1000;
ly = 1000;

% Minimum distance
d = 100;

% Number of points to generate
n = 50;

points = [rand(1, 2) .* [lx ly]];
d2 = d ^ 2;

% Keep adding points until we have n points.
while (size(points, 1) < n)

    % Randomly generate a new point
    point = rand(1, 2) .* [lx ly];

    % Calculate squared distances to all other points
    dist2 = sum((points - repmat(point, size(points, 1), 1)) .^ 2, 2);

    % Only add this point if it is far enough away from all others.
    if (all(dist2 > d2))
        points = [points; point];
    end
end

plot(points(:,1), points(:,2), 'o')
Jeff Irwin
  • 1,041
  • 8
  • 12
  • 1
    That's not the rejection method and it does not generate all possible events with the same probability, but it probably comes very close to it. Rejection method would reject and regenerate all points until one set matches the requirements. – Daniel Sep 27 '15 at 20:29
  • @Danial Thanks for the clarification. Correct me if I'm wrong, but true rejection sampling would be much slower than my approach. – Jeff Irwin Sep 27 '15 at 20:36
  • 1
    Especially when the probability for a rejection is high, it would be much slower. – Daniel Sep 27 '15 at 20:40
  • @Jeff Irwin: This code will work perfectly if lx and ly are equal. If i give lx=1000 and ly=10, the code is not giving expected result. – reena Sep 28 '15 at 16:39
  • What are the values of `d` and `n`? Depending on the input, it may be impossible to pack a certain number of vehicles into a given area. I did test my code with `lx = 1000; ly = 700; d = 100; n = 50;` and it works as expected. – Jeff Irwin Sep 28 '15 at 21:58
  • @Jeff Irwin::d=10 and n=100 – reena Sep 29 '15 at 04:23
  • Can you be more specific about how the results are unexpected? Does the program take too long to run, or are the points too close together, or something else? Just looking at the figure to judge distances can be misleading, as the aspect ratio may be very distorted. – Jeff Irwin Sep 29 '15 at 22:16
  • @Jeff Irwin:: You were right. I was judging distances by just looking at the figure. Code given by you is working. – reena Oct 01 '15 at 06:53