Is there a built-in function that determines whether X/Y coordinates give valid polygon?

8 views (last 30 days)
Dr. Seis
Dr. Seis on 18 Jul 2012
If I have a vector of X-coordinates and a vector of Y-coordinates, is there a function that determines whether a valid polygon is created based on the order of the X/Y coords (i.e., lines connecting points do not criss-cross). I envision it would work something like this:
Valid polygon would be:
>> xy = [0,0; 1,0; 1,1; 0,1; 0,0];
>> ispoly(xy)
ans =
1
Not a valid polygon:
>> xy = [0,0; 1,0; 0,1; 1,1; 0,0];
>> ispoly(xy)
ans =
0
If nothing exists... no worries I'll sit down and work out my own function.

Answers (3)

Image Analyst
Image Analyst on 19 Jul 2012
Elige, you need to search for "detect self-intersecting polygon". You can add MATLAB if you want to the search terms. You'll get lots of hits, including this one from Buno Luong which has MATLAB code:
  1 Comment
Dr. Seis
Dr. Seis on 19 Jul 2012
Thanks IA, that example was a bit too complicated for my brain to digest, but I think I came up with a simple way of determining what I need... see my answer

Sign in to comment.


Star Strider
Star Strider on 18 Jul 2012
I'm not certain this does what you want, but experimenting with ‘convhull’ might provide a solution:
xy1 = [0,0; 1,0; 1,1; 0,1; 0,0];
xy2 = [0,0; 1,0; 0,1; 1,1; 0,0];
[K1,V1] = convhull(xy1(:,1), xy1(:,2));
[K2,V2] = convhull(xy2(:,1), xy2(:,2));
dK1 = diff(K1);
dK2 = diff(K2);
The list in ‘K1’ is in order, the list in ‘K2’ is not, so ‘dK1’ has only one (-)ve element while ‘dK2’ has two. You'll likely have to write your own ‘ispoly’ function, but ‘convhull’ may make that easier.
  2 Comments
Dr. Seis
Dr. Seis on 19 Jul 2012
Yeah, as IA said. I found several examples where "K" is ordered (except the last point, which is a repeat of the first point) but is self-intersecting. Good idea, though.

Sign in to comment.


Dr. Seis
Dr. Seis on 19 Jul 2012
Edited: Dr. Seis on 19 Jul 2012
My attempt:
% Assume polygon is valid
answer = 1;
% Set tolerance
tol = 0.001;
% Random set of X/Y coordinates
xycoords = randn(6,2);
% Make sure first/last coordinate are same
if sum((xycoords(1,:) - xycoords(end,:)).^2) > tol
xycoords(end+1,:) = xycoords(1,:);
end
% Determine number of sides (n)
n = size(xycoords,1)-1;
k = 2;
% Figure out all line segment combinations to check
lines = nchoosek(1:n,k);
for i = 1 : size(lines,1)
% Determine coordinates of two line segment combinations
xy1 = xycoords(lines(i,1):lines(i,1)+1,:);
xy2 = xycoords(lines(i,2):lines(i,2)+1,:);
% Consider "origin" as first X/Y pair in each line segment
xy01 = [xy1(1,:);xy1(1,:)]; % 1st line segment is reference
xy02 = [xy2(1,:);xy2(1,:)]; % 2nd line segment is reference
% Subtract "origin" such that ref. line segment begins at [0,0]
xy11 = xy1-xy01;
xy21 = xy2-xy01;
xy12 = xy1-xy02;
xy22 = xy2-xy02;
% Determine angle needed to rotate reference line segment parallel
% to the x-axis
theta1 = 2*pi-atan2(xy11(2,2),xy11(2,1));
theta2 = 2*pi-atan2(xy22(2,2),xy22(2,1));
% Determine rotation matricies
rot1 = [cos(theta1), sin(theta1); -sin(theta1),cos(theta1)];
rot2 = [cos(theta2), sin(theta2); -sin(theta2),cos(theta2)];
% Rotate line segments to coordinate system where reference line
% segment is parallel to x-axis
xy11 = xy11*rot1;
xy21 = xy21*rot1;
xy12 = xy12*rot2;
xy22 = xy22*rot2;
% Determine if line segments intersect
% Criteria - if the y-values associated with one non-reference line
% segment is either all positve or all negative (or one
% of the y-values is 0), then there is no intersection
if sign(xy21(1,2)) ~= sign(xy21(2,2))
if abs(xy21(1,2)) > tol && abs(xy21(2,2)) > tol
if sign(xy12(1,2)) ~= sign(xy12(2,2))
if abs(xy12(1,2)) > tol && abs(xy12(2,2)) > tol
answer = 0;
break;
end
end
end
end
end

Tags

Community Treasure Hunt

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

Start Hunting!