Here is the cellular representation of polygon shown:-
Here is the extracted polygon shown.
We are given the input as a matrix polM
that stores 1 for pink cells and 2 for yellow cells. From the yellow colored cells we want to create a polygon. This is also done using below code derived from here.
clear;
close all;
A=ones(25,25);
indices=[64,65,88,89,90,91,111,112,113,114,115,116,117,135,136,137,138,139,140,141,142,143,158,159,160,161,162,163,164,165,166,167,168,169,182,183,184,185,186,187,188,189,190,191,192,193,194,195,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,282,283,284,285,286,287,288,289,290,291,292,293,294,295,307,308,309,310,311,314,315,316,317,318,319,320,341,342,343,344,345,367,368,369,393,394];
A(indices)=2;
figure
hold on
axis equal
axis ij
xx=10:20:500;
yy=10:20:500;
imagesc(xx,yy,A);
colormap([1.0000 0 0.7931;
1.0000 0.8276 0]);
rt=[0,500];
gcs=0:20:500;
gds=ones(size(rt,2),size(gcs,2));
gds = bsxfun(@times,gds,gcs);
plot(rt,gds,'Color','k','LineStyle','-');
plot(gds,rt,'Color','k','LineStyle','-');
axis([0 350 100 450])
A=A-1;
% we identify patterns with edges over 2x2 patches, describing with
% the first 4 binary values what pixels are set, and with the next 2
% the edge with 2 indices over the 2x2 patch
patterns = [
0,1,0,1, 3,4 % vertical edge at rhe right
1,0,1,0, 1,2 % vertical edge at the left
0,0,1,1, 2,4 % horizontal edge at the bottom
1,1,0,0, 1,3 % horizontal edge at the top
1,0,0,1, 1,4 % diagonal edge
0,1,1,0, 2,3 % diagonal edge
1,0,1,1, 1,4 % diagonal edge, extra pixel set
1,1,0,1, 1,4 % diagonal edge, extra pixel set
1,1,1,0, 2,3 % diagonal edge, extra pixel set
0,1,1,1, 2,3 % diagonal edge, extra pixel set
];
% 2x2 patches (matrix form)
P00 = A(1:end-1,1:end-1);
P10 = A(2:end,1:end-1);
P01 = A(1:end-1,2:end);
P11 = A(2:end,2:end);
% edge unique identifier using powers of 2
id = @(p00,p01,p10,p11) 1*p00 + 2*p10 + 4*p01 + 8*p11;
P = id(P00,P01,P10,P11); % vectorized pattern identification
% edges
e0 = []; % from (i,j)
e1 = []; % to (i,j)
for i = 1:size(patterns, 1) % small loop over the 10 patterns
p = patterns(i, :);
E = (P == id(p(1),p(2),p(3),p(4))); % pattern search, vectorized
[c,r] = ind2sub(size(E), find(E));
[c0,r0] = ind2sub([2,2], p(5));
[c1,r1] = ind2sub([2,2], p(6));
e0 = [e0; c+c0, r+r0];
e1 = [e1; c+c1, r+r1];
end
X = [e0(:,2) e1(:,2)]';
Y = size(A,1) - [e0(:,1) e1(:,1)]';
figure
hold on
axis equal
axis ij
X=X*20;
Y=Y*20; Y=500-Y;
plot(X, Y, '.-')
axis([0 350 100 450])
But the output of this code which represents the polygon is given by arrays X
and Y
. I want to express the output in nx2 matrix form where all rows represent a vertex if the final polygon and the vertices are in a clockwise or counter clockwise order starting from the first vertex. There are methods here that can post-process a jumbled sequence of vertices to an ordered sequence but i want an algorithm to determine the polygonal vertices from input matrix polM
in an ordered sequence only. SO input is polM
and output is a nx2 matrix of polygon vertices in either cw or ccw order only.
Can someone suggest an efficient change to the algorithm?
EDIT:
If you add this piece of code assuming ordered result is already coming you get error:-
newp=[X(1,:)',Y(1,:)'];
figure
hold on
axis([0 350 100 450])
axis equal
axis ij
line(newp(:,1), newp(:,2));
Basically i want to resolve this error.