How to produce a number of random coordinates within a square grid ensuring that the distance between points is no more than a specified value?

51 views (last 30 days)
Oliver Wilkins on 4 May 2020
Commented: Oliver Wilkins on 6 May 2020
Hi, currently I am trying to use the rand function to produce an N by 2 matrix to give random coordinates within a 1 by 1 square which works seeing as the rand function uniformly takes values inbetween 0 and 1. I then take each row of this matrix as the x and y coordinates on the square grid. I am looking for help to find a way so that each of these coordinates is at least some distance,a, from the nearest neighbour.
For example if specifies the position of 1 coordinate then the nearest neighbour should have the coordinate where .
This is meant to represent the radius of solid circles and how they shouldn't overlap.
Currently I am only using the basic rand function:
xy=rand([N 2])
I have tried looking online for a specific solution but have not found one yet. Is there a way to set these kind of conditions on the rand function?
Any help is appreciated :)

Cam Salzberger on 5 May 2020
Edited: Cam Salzberger on 5 May 2020
There are three ways that I can think of to address this, and all are iterative:
1. Generate N random points, remove any that aren't sufficiently "near" to neighbors, generate new random points and repeat.
2. Generate one random piont, generate the next one in a square (sides = 2*a) centered on the first point, and repeat until you get N points.
3. Generate random points to sufficiently cover your space and then remove points that aren't "unique" enough to be worth keeping (maybe something like removing those that aren't any neighbor's only neighbor, have at least two neighbors, and those neighbors are sufficiently "opposite" each other), and repeat until down to N points.
Number 2 will be largely clustered around the first point. Number 1 will be more distributed around the area, though there will still certainly be clusters. Pick your preferred method for your application. Number 3 would probably best cover the area, but the algorithm would be complicated and hard to guarantee you cover the area and get down to N points, though there are probably existing algorithms in sampling based methods for something like this.
If you need more advice, knowing your application (like a particle filter or whatever) helps to direct in one way or another.
-Cam

1 Comment

Oliver Wilkins on 6 May 2020
Thanks a lot for the solutions. The first option you gave seems best for my situation. I'm trying to create random configurations of wave scatterers and determine how waves propagate through the array. The condition is just that the scatterers cannot overlap but placement of scatterers can be clustered together or spaced apart so option 1 definitely fits the bill.