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

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.

Answer 1

[Image Analyst]

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:

http://www.mathworks.nl/matlabcentral/newsreader/view_thread/301564

[Dr. Seis]

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

Answer 2

[Star Strider]

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.

[Image Analyst]

I don't see how convhull() would help. It's not hard to think of several examples where the convex hull of an ordered set of points would have no knowledge of whether interior points were looping/crossing each other or not.

[Dr. Seis]

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.

Answer 3

[Dr. Seis]

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