Creating random points along polygon boundary?

Hello. I am trying to write a script that will create random points along the boundary of an input polygon.

Right now I have a script that is able to generate random points within a polygon - it uses the same process here:

http://blogs.mathworks.com/videos/2008/01/21/practical-example-generating-points-inside-a-polygon/

What it essentially does is employs a loop that creates random points and then checks if they are within the polygon, if not then it continues until it finds a point that is within and loops over it again.

The function inpolygon is able to identify whether or not a point is inside a polygon, on the border of a polygon, or niether. From its helpfile:

[IN ON] = inpolygon(X,Y,XV,YV) returns a second matrix, ON, which is the size of X and Y.

ON(p,q) = 1 if the point (X(p,q), Y(p,q)) is on the edge of the polygonal region; otherwise ON(p,q) = 0.

Using the second output, ON, to check if one of the randomly generated points is on the border is not very efficient.

Can anyone think of a better way to generate random points along the border of a polygon?

My polygon is essentially a 2 x 894 array with the first row being all of the x coordinates and the second row being all of the y coordinates with each column making up a point.

Here is the script for generating random points within a polygon. M.X and M.Y serve as the X and Y vectors of the polygon points.

for j=1:iterate
    n=2;
    PX = zeros(1,n);
    PY = zeros(1,n);

      for i=1:n
          flagIsIn = 0;

          while ~flagIsIn
              PX(1,i) = (b-a).*rand(1,1) + a;
              PY(1,i) = (d-c).*rand(1,1) + c;
              [IN ON] = inpolygon(PX(1,i),PY(1,i),M.X,M.Y);
              if ON == 1
                  flagIsIn = 1
              end

          end
     end
end

Answer 1

[Kelly Kearney]

The interparc function in the FEX makes this pretty easy:

pt = interparc(rand(10,1), x, y, 'linear');
plot(x,y,'b', pt(:,1), pt(:,2), 'r.');

[John D'Errico]

Funny. I did not think of that application of interparc, and I wrote it. LOL

[Kelly Kearney]

Ha ha! I use it all the time to upsample and downsample polygons... might be an overly-powerful hammer for this particular nail, but it works great and saves me some typing (over the multiple interp1 calls I used prior to it).

[Eric]

Thank you for your answer - I think this will work.

Thank you John for writing this script - I can already see many other uses.

[John D'Errico]

One thing I like about the FEX is I so often see the code I've posted used in ways one never would have imagined when I wrote them.

Answer 2

[Roger Stafford]

Only after I worked out a solution did I see Kelly's/John's solution. Well, I'll give mine anyway just for the heck of it.

Let G be the 2 x 894 matrix for the polygon and let n be the number of desired random points.

 G = [G,G(:,1)]; % Connect the first and last vertices of polygon
 D = G(:,2:end)-G(:,1:end-1);
 L = [0,cumsum(sqrt(sum(D.^2,1)))];
 [~,ix] = histc(rand(1,n),L/L(end));
 P = G(:,ix)+bsxfun(@times,rand(1,n),D(:,ix)); % <-- The random points
 plot(G(1,:),G(2,:),'r*',P(1,:),P(2,:),'y.')

[John D'Errico]

Were I going to write it (without benefit of the interparc trick), this is the way I had thought of originally.

Answer 3

[Matt J]

If the rows of V are the vertices sorted in clock-wise or counter-clockwise order, you could do as follows. The example is for the unit square,

    V=[0 0; 0 1; 1 1; 1 0]; %ordered vertices
    n=7; %number of points to generate

    %%engine

    idx=randi(size(V,1),1,n);
    V=[V;V(1,:)];

    P1=V(idx,:);  %select random pair of adjacent vertices
    P2=V(idx+1,:); 

    edgePoints=bsxfun(@times,rand(n,1), P1-P2)+P2, %select random convex comb

[Eric]

I think this would also work.

Thank you for your answer.