Thread Subject:

generate random points in any shaped polygon?

hello everybody,
anyone there knows of a way of generating random points
within any shape polygon?.
But not by masking out/deleting the points falling out of the polygon.


Regards

"Edwin " <onest30@gmail.com> wrote in message <hv7gk8$289$1@fred.mathworks.com>...
> hello everybody,
> anyone there knows of a way of generating random points
> within any shape polygon?.
> But not by masking out/deleting the points falling out of the polygon.
>

If you want uniform distribution:
Triangulate the polygon, select the random triangle with pdf proportional to its area, use barycentric coordinates to generate random point of the selected triangle.

Roger Stafford has worked on this problem and I'm sure he can provide you few more details.

Bruno

"Edwin " <onest30@gmail.com> wrote in message <hv7gk8$289$1@fred.mathworks.com>...
> hello everybody,
> anyone there knows of a way of generating random points
> within any shape polygon?.
> But not by masking out/deleting the points falling out of the polygon.
> Regards

  See the discussion on this subject in the June 5, 2008 thread at:

 http://www.mathworks.com/matlabcentral/newsreader/view_thread/170480

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hv7ol1$k3n$1@fred.mathworks.com>...
> "Edwin " <onest30@gmail.com> wrote in message <hv7gk8$289$1@fred.mathworks.com>...
> > hello everybody,
> > anyone there knows of a way of generating random points
> > within any shape polygon?.
> > But not by masking out/deleting the points falling out of the polygon.
> > Regards
>
> See the discussion on this subject in the June 5, 2008 thread at:
>
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/170480
>
> Roger Stafford

first thank you Bruno and Roger
for your help
I just grabbed the code from the post Roger suggested
However I'm having some problems for adapting it.
for example for 9 vertex polygon
Below is the "adapted" code can someone give me a hand.
---------------------------------------------------------------------------------------------------------------------
clear all
clc
A=[271.750000000000,10.6000000000000
    271.750000000000,12.8500000000000
    272.350000000000,12.5000000000000
    272.850000000000,12.1300000000000
    273.380000000000,11.6000000000000
    273.720000000000,11.2000000000000
    274.440000000000,11
    274.570000000000,10.8800000000000
    274.920000000000,10.6000000000000];
n = 4096; % <-- Choose the desired number of points, preferably large
% Randomize
rand('seed',sum(100*clock));
x=[A(:,1);A(1,1)];
y=[A(:,2);A(1,2)];
numpoints=length(x)-1;
numtrian=numpoints-2;
areas=zeros(numtrian-2,1);
cont=1;
for i=1:numtrian
areas(cont) = abs(det([A(i+1,1:2)-A(1,1:2);A(i+2,1:2)-A(1,1:2)])); % Twice the triangles' areas
cont=cont+1;
end
sa = sum(areas);
 % Normalize cumulative areas
cont2=1;
Normalizing=zeros(numtrian-1,1);
 for j=1:numtrian-1
Normalizing(cont2)=sum(areas(1:j))/sa;
 cont2=cont2+1;
 end
 r = rand(n,1); % Use this to select the triangle
 s = sqrt(rand(n,1)); s2 = [s,s]; % Use these to select
 t = rand(n,1); t2 = [t,t]; % points within a triangle
% Generalized vertices
triangles=zeros(n*(numtrian-3),2);
cont3=1;
cont4=1;
ind=1;
for k=2:1:numtrian
 trianglesaux = (r<=Normalizing(1,1))*A(k,1:2) + ((Normalizing(1,1)<r)&(r<=Normalizing(2,1)))*A(k+1,1:2) + (Normalizing(2,1)<r)*A(k+2,1:2);

 if k==2
 ind=0;
 triangles=insertrows(triangles,trianglesaux,ind);
 else
 ind=(n*cont4)+1;
  triangles=insertrows(triangles,trianglesaux,ind);
 cont4=cont4+1;
 end
  cont3=cont3+1;
end
woz=triangles;
woz(~any(triangles,2),:)=[];
triangles=woz;
clear woz
cont5=1;
cont6=1;
pp=zeros(length(triangles),2);
for i=1:numtrian
if i==1
  p = (1-s)*A(1,1:2) + s2.*((1-t2).*triangles(1:n,1:2) + t2.*triangles(n+1:n*2,1:2)); % The random points
  pp=insertrows(pp,p,0);
else
  p = (1-s)*A(1,1:2) + s2.*((1-t2).*triangles((n*2)+1:n*3,1:2) + t2.*triangles(n+1:n*2,1:2)); % The random points'
  pp=insertrows(pp,p,((cont5*n)+1));
  cont5=cont5+1;
end
end
woz=pp;
woz(~any(pp,2),:)=[];
pp=woz;
clear woz
 plot(x,y,'r-',p(:,1),p(:,2),'y.',x,y,'bo') % Plot random points as yellow dots
 axis equal
------------------------------------------------------------------------------------------------------------------

Regards

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hv7ol1$k3n$1@fred.mathworks.com>...
> See the discussion on this subject in the June 5, 2008 thread at:
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/170480
> Roger Stafford

  Added note: If your polygon is divided up into a large number of triangles, you can use the 'histc' function to choose points among them in proportion to their area. Let a = [A1 A2 A3 ... An] be a vector of their areas. Let N be the total number of random points you want to choose.

 c = cumsum([0 a]); c = c/c(end); c(end) = inf;
 b = histc(rand(N,1),c); b(end) = [];

Then b will be a vector with n elements with a total count of N containing the numbers of points selected for each of the respective triangles, and these will have been selected randomly in proportion to their areas.

Roger Stafford