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

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

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:
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

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 CommentsShowHide 1 older comment
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.

Dr. Seis on 19 Jul 2012
Edited: Dr. Seis on 19 Jul 2012
My attempt:
% Assume polygon is valid
% 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
break;
end
end
end
end
end