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

2 次查看（过去 30 天）
Dr. Seis
Dr. Seis 2012-7-18
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.

请先登录，再回答此问题。

回答（3 个）

Image Analyst
Image Analyst 2012-7-19
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
  1 个评论
Dr. Seis
Dr. Seis 2012-7-19
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
Star Strider 2012-7-18
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 个评论
Image Analyst
Image Analyst 2012-7-19
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
Dr. Seis 2012-7-19
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
Dr. Seis 2012-7-19
编辑：Dr. Seis 2012-7-19
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

类别

在 Help Center 和 File Exchange 中查找有关 Blocked Images 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by