Creating random points along polygon boundary?

7 views (last 30 days)
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:
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

Accepted Answer

Kelly Kearney
Kelly Kearney on 4 Jun 2014
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.');
  4 Comments
Eric
Eric on 4 Jun 2014
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
John D'Errico on 4 Jun 2014
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.

Sign in to comment.

More Answers (2)

Roger Stafford
Roger Stafford on 4 Jun 2014
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.')
  1 Comment
John D'Errico
John D'Errico on 4 Jun 2014
Were I going to write it (without benefit of the interparc trick), this is the way I had thought of originally.

Sign in to comment.


Matt J
Matt J on 4 Jun 2014
Edited: Matt J on 4 Jun 2014
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

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!