How do I generate pair of random points in a circle using Matlab?

Question

Let a circle of known radius be plotted in MATLAB.

Assume a pair of random points whose location has to be determined in terms of coordinates (x1,y1) (x2,y2)..(xn,yn). Pairs should be close to each other. For example T1 and R1 should be near.

As shown in figure, there are four random pairs (T1,R1)..(T4,R4). There coordinates need to be determined wrt to center (0,0).

How can I generate this in MATLAB?

Answer 1

(Complete edit after the question was edited).

To complete this task, I think that you need to combine the different approaches that have been mentioned before your edit:

• To generate the centers T1,T2,T3,... in the green torus, use the polar coordinates. (Edit: this turned out to be wrong, rejection sampling must also be used here, otherwise, the distribution is not uniform!)
• To generate the points R1,R2,R3,... in the circle around T1,T2,T3,... but still in the torus, use the rejection sampling.

With these ingredients, you should be able to do everything you need. Here is the code I wrote:

d=859.23;
D=1432.05;
R=100;
N=400;

% Generate the angle
theta = 2*pi*rand(N,1);

% Generate the radius
r = d + (D-d)*rand(N,1);

% Get the centers of the circles
Tx = r.*cos(theta);
Ty = r.*sin(theta);

% Generate the R points
Rx=zeros(N,1);
Ry=zeros(N,1);
for i=1:N
    while true
        % Try
        alpha = 2*pi*rand();
        rr = R*rand();

        Rx(i) = Tx(i) + rr*cos(alpha);
        Ry(i) = Ty(i) + rr*sin(alpha);

        % Check if in the correct zone
        if ( (Rx(i)*Rx(i) + Ry(i)*Ry(i) > d*d) && (Rx(i)*Rx(i) + Ry(i)*Ry(i) < D*D) )
           break
        end
    end
end

% Display
figure(1);
clf;
angle=linspace(0,2*pi,1000);
plot( d*cos(angle), d*sin(angle),'-b');
hold on;
plot( D*cos(angle), D*sin(angle),'-b');
for i=1:N
    plot(Tx(i),Ty(i),'gs');
    plot(Rx(i),Ry(i),'rx');
    plot([Tx(i) Rx(i)],[Ty(i) Ry(i)],'-k');
end
hold off;

Answer 2

Generate the random points as @PheuVerg suggested (with a slight vectorized tweak)

n = 8; %must be even!
x = rand(n, 1)*2*R - R; 
y = rand(n, 1).*sqrt(R^2 - x.^2).*2-sqrt(R^2 - x.^2);

Then use kmeans clustering to get n/2 centers

[~ c] = kmeans([x y], n/2);

now you have to loop through each center and find it's distance to each point

dists = zeros(n, n/2);
for cc = 1:n/2
    for pp = 1:n
        dists(pp, cc) = sqrt((c(cc,1) - x(pp))^2 + (c(cc,2) - y(pp))^2);
    end
end

now you must find the smallest 2 values for each columns of dists

[sorted, idx] = sort(dists);

so now the top two rows of each column are the two nearest points. But there could be clashes! i.e. points that are nearest to two different centers. So for repeated values you have to loop through and choose swap for the point that will give you the smallest extra distance.

Example data:

x =

    0.7894
   -0.7176
   -0.5814
    0.0708
    0.5198
   -0.2299
    0.2245
   -0.8941

y =

   -0.0800
   -0.3339
    0.0012
    0.9765
   -0.4135
    0.5733
   -0.1867
    0.2094

sorted =

    0.1870         0         0    0.1555
    0.2895    0.5030    0.5030    0.2931
    0.3145    1.1733    0.6715    0.2989
    1.0905    1.1733    0.7574    0.7929
    1.1161    1.2326    0.8854    0.9666
    1.2335    1.2778    1.0300    1.2955
    1.2814    1.4608    1.2106    1.3051
    1.4715    1.5293    1.2393    1.5209

idx =

     5     4     6     3
     7     6     4     2
     1     3     3     8
     6     7     8     6
     3     8     7     7
     2     1     2     4
     4     5     1     5
     8     2     5     1

So now it's clear that 5 and 7 are pairs, and that 3 and 2 are pairs. But 4 and 6 are both repeated. (in this case it is clear that they are pairs too I guess!) but what I would suggest is to leave point 4 with center 2 and point 6 with center 3. Then we start at column 2 and see the next available point is 8 with a distance of 1.2326. This would leave point 1 paired with point 6 but then it's distance from the center is 1.2106. Had we paired point 6 with 8 and point 4 with 1 we would have got distances of 0.7574 and 1.2778 respectively which is actually less total distance. So finding 'close' pairs is easy but finding the set of pairs with the globally smallest minimum is hard! This solutions gets you something decent quite easily but fi you need the global best then I'm afraid you have quite a bit of work to do still :(

Finally let me add some visualisation. First lets (manually) create a vector that shows which points are paired:

   I = [1 2 2 1 3 4 3 4];

Remember that that will depend on your data! Now you can plot is nicely like this:

gscatter(x, y, I)

Hope this gets you close and that you can eliminate the manual pairing of mine at the end by yourself. It shouldn't be too hard to get a crude solution.

Answer 3

Here is a low quality solution that is very easy to use with uniformly distributed points. Assuming the number of points is small efficiency should not be a concern, if you want better quality you can use something more powerfull than nearest neighbor:

1. While you have less than n points: Generate a random point
2. If it is in the circle, store it else go to step 1
3. While there are unpaired points: check which point is nearest to the first unpaired point, make them a pair

As a result most pairs should be good, but some can be really really bad. I would recommend you to try it and perhaps add a step 4 with k-opt or some other local search if required. And if you really have little points (e.g. less than 20) you can of course just calculate all distances and find the optimum matching.

---

If you don't really care about the uniform distribution, here is an even easier solution:

1. While you have less than n points: Generate a random point
2. If it is in the circle, store it else go to step 1
3. For each of these points, generate a point near it
4. If it is in the circle, store it else go to step 3

Answer 4

The simplest approach to pick a point from a uniform distribution over a circle with reduce R is using Gibbs sampling. Here is the code:

function [x y] = circular uniform (R)
while true
   x = 2*R*rand() - R
   y = 2*R*rand() - R
   if (x*x + y*y) > R*R
       return
   end
end

The loop runs 4/π times on average.

Answer 5

let R be radious of (0;0) centered circle.
(x,y) : x^2+y^2<=R^2 (LE) to be inside the circle

x = rand()*2*R - R;  

y should be in interval (-sqrt(R^2 - x^2);+sqrt(R^2 - x^2))
so, let it be

y = rand()*sqrt(R^2 - x^2)*2-sqrt(R^2 - x^2);  

Hope, that's right, i have no matlab to test.
Hope, you'll manage to find close pairs your self.
Ok, i'll spend a bit more time for a hint. To find a random number k in interval [a,b] use

k = rand()*(b-a)+a  

Now it should really help if i still remember the matlab syntaxis. Good luck.