Generate Random Number inside a closed area

52 views (last 30 days)
Armin Mashhadi on 5 Oct 2019
Edited: Armin Mashhadi on 14 Oct 2019
Hi,
There is a closed area, as figure1.We wanna have random number inside it.
figure1. An Area with defined boundry poinst.
Since Code has many different layers, I prefer not to use "WHILE" like below. ("Data" is Attached)
in=0;
while ~in
Point(1)=unifrnd( min(x),max(x) );
Point(2)=unifrnd( min(y),max(y) );
in=inpolygon(Point(1),Point(2),x,y);
end
plot(x,y,Point(1),Point(2),'^');
Do you know any ready-to-go command which takes Boundary of a closed area, and gives a random point within it?

John D'Errico on 5 Oct 2019
Edited: John D'Errico on 5 Oct 2019
Not hard. But it takes a little effort. (I should post a tool for this on the FEX. SIGH. Actually, I have a tool that does this, but it is more complicated to use than I want it to be for me to post it.)
The general idea is to...
1. Triangulate the region. If you have a convex region, bounded by a polygon, then there are many ways to do this.
2. Determine the area of each triangle.
3. Choose a random triangle inside the region, with probability based on the relative fraction of the area of the differfent triangles.
4. Once you have the triangle, then generate a random point that lies uniformly inside the triangle.
Each of the above steps is easy enough in theory, though many users might find them complex. I can't say. In fact, all of the above steps are doable in a way that is fast, efficient, and even vectorized.
So, given a list of points that form a polygon, if the polygon is convex, a simple way to triangulate it is a delaunay triangulation. I'll want a list of vertices for later, so do it like this:
XY = [x(:),y(:)];
tri = delaunay(XY);
Or, you could do it using the delaunayTriangulation function. Or, you can do it by starting with the convex hull of the points, and then add on point at the centroid of the polygon. Then connect each edge of the convex hull to the centroidal point. Or, given a polygon, you could use ear clipping to create a triangulation. As I said, lots of ways to do it.
Next, we can compute the area of each triangle simply enough. In fact, this is easily done as a vectorized computation.
% use a 2x2 determinant, in a vectorized form
v1 = XY(tri(:,1),:);
v2 = XY(tri(:,2),:);
v3 = XY(tri(:,3),:);
% translate
v1 = v1-v3;
v2 = v2-v3;
% vectorized determinant
% divide by factorial(2) for the area
areas = (v1(:,1).*v2(:,2) - v1(:,2).*v2(:,1))/2;
% normalize the areas to sum to 1
areas = areas/sum(areas);
Now, pick a random triangle, proportional to the relative area of each triangle. You can do this for many points at once, using the discretize tool. I'll assume you want to generate nsample points. I'll do these computations for the data provided, here, for 1000 points.
nsample = 1000;
R = rand(nsample,1);
tind = discretize(R,cumsum([0;areas]));
Next, for each triangle chosen, we will find ONE point that lives inside that triangle. Again, a vectorized computation.
v1 = XY(tri(tind,1),:);
v2 = XY(tri(tind,2),:);
v3 = XY(tri(tind,3),:);
R1 = rand(nsample,1);
xyrand = v1.*repmat(R1,[1 2]) + v2.*repmat(1-R1,[1 2]);
R2 = sqrt(rand(nsample,1));
xyrand = xyrand.*repmat(R2,[1 2]) + v3.*repmat(1-R2,[1 2]);
I used repmat above, but it is also easily done using scalar dimension expansion as found in R2016b or later, or using bsxfun.
Did it work?
plot(xyrand(:,1),xyrand(:,2),'.')
hold on
plot(x,y,'r-')
Of course. Uniformly generated samples in a polygonal region. Fully vectorized too.

1 Comment

Armin Mashhadi on 14 Oct 2019
Hi, Your idea was really genuene and wonderful. It workes for me, Thank you very very much for your helping. I think you did a good service to Matlab community.
For others who visited and have no idea about above calculation, I have some Tips:
1. Area of a triangular with given coordinates of vertices is :
Area=
for vectorizing we can replace that with:
Area= []
So:
d1 = v1-v3;
d2 = v2-v3;
Area = (d1(:,1).*d2(:,2) - d1(:,2).*d2(:,1))/2
2. Finding a Point inside the triangle, Assume there is a triangle like the picture and we are about to find a random number inside it, We can do it by choosing two random number:
a) finding two random number in [0,1] called and
b) finding a point at lower side of triangle
c) connect the new point to the other vertex to create a chord, then find another random number on this chord using :
This code will do it:
R1 = rand(nsample,1);
D1=v2-v1;
xyrand = v1 + D1.*repmat(R1,[1 2]) ;
R2 = rand(nsample,1);
D2=v3-xyrand;
xyrand = xyrand + D2.*repmat(R2,[1 2]);
or briefly :
R1 = rand(nsample,1);
xyrand = v1.*repmat(R1,[1 2]) + v2.*repmat(1-R1,[1 2]);
R2 = sqrt(rand(nsample,1));
xyrand = xyrand.*repmat(R2,[1 2]) + v3.*repmat(1-R2,[1 2]);

Dimitris Kalogiros on 5 Oct 2019
Run your code many times and store the resulting point ( variable Point) into a file. Then every time you need a random point from the wanted area, you can have you choose randomly a point from this file.

1 Comment

Armin Mashhadi on 5 Oct 2019
Hi,
It's not about just this area,
In every loop a new one is created which a randomn number has to generate inside it.
I mean this area was an example and it's not consistent.
but thank you for your time..