Detect corner coordinates of a non-convex polygon in clockwise order MATLAB

I have some images which includes both convex as well as non-convex polygons. Each image contains exactly one polygon. I need to detect the corner coordinates and need to sort them in clock-wise or counter-clockwise order. For convex polygons, I use Harris corner detection for detecting corners and convexhull for sorting the points. But i dont have any idea on how to sort non-convex polygon. As my inputs are images, i think some Image Processing Technique might help to sort them out by moving alongside the edge of the polygon. Is there any way with least complexity?

Example Image:

I have named the corners randomly.

Expected output:

I expect Corner coordinates in this order 1 3 5 9 4 2 8 7 6 10 or 1 10 6 7 8 2 4 9 5 3. You can start at any point, not necessarily 1

Edit 1:

After rayryeng's solution, which works for all convex polygons as well as for some non-convex polygon, there are some non-convex polygons which doesn't go well with his algorithm.

Here is an example

Another approach is to use bwdistgeodesic to find order the corners by their distance along your edge. This should work for any polygon where you can detect a continuous edge.

We start by loading in the image from Stack Overflow and converting it into a black and white image to make it easier to find the edge

A = imread('https://i.sstatic.net/dpbpP.jpg');
A_bw = im2bw(A,100/255);  %binary image
A_bw1 = imcomplement(A_bw);   %inverted binary image

The bwmorph function provides a lot of options for manipulating black and white images. We're going to use the remove option to find the edge of our polygon, but you could also use another edge detector if you prefer.

%Find the edges
A_edges = bwmorph(A_bw, 'remove');
[edge_x, edge_y] = find(A_edges');

Let's visualize the edges we detected

figure; imshow(A_edges);

Okay, we have a nice clear continuous edge. Now let's find the corners. I use corner, but you could substitute your favorite corner detector

A_corners = corner(A_bw1, 'QualityLevel',.3);

Let's visualize our initial corner ordering

figure; imshow(A_bw1);
hold on
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18)
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

Another thing you might not notice, is that they are not directly on the edges. I'll start by finding the closest point along the edge to each corner point, and then I'll visualize corners in red and the closest edge points in green.

[~, ind] = min(pdist2(A_corners, [edge_x, edge_y]), [], 2);
A_edge_corners = [edge_x(ind), edge_y(ind)];

figure; imshow(A_edges);
hold on;
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18)
plot(A_edge_corners(:,1), A_edge_corners(:,2),'g.', 'MarkerSize', 18)
hold off;

To calculate the distance around the edge for each corner, we'll use the corner point approximation, A_edge_corners (green point) on the edge rather than the corner point itself A_corners (red point).

Now we have all the pieces we need to use bwdistgeodesic. This function finds the distance to a seed point for each non-zero pixel in a black and white image. We are interested in the distance from an initial corner to each point on the edge. Let's try it out.

% Calculate distance from seed corner
first_corner = A_edge_corners(1,:);
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2));
figure; imagesc(D);

We're starting from the right most corner and the pixels moving away from the corner increase in value. But this isn't quite what we want. If we order the corners using these values, we end up with an ordering in distance from the initial point.

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1))));
A_corners_reorder1 = A_corners(corner_order, :);

figure; imshow(A_bw1);
hold on
plot(A_corners_reorder1(:,1), A_corners_reorder1(:,2),'r.', 'MarkerSize', 18)
text(A_corners_reorder1(:,1), A_corners_reorder1(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

To solve this problem, we just have to break the edge so that the ordering only goes in one direction from the initial point. If you are interested in a clockwise or a counter-clockwise ordering, you would need to break the edge according to a set of rules depending on the orientation of the edge. If the direction doesn't matter you can simply find an adjacent pixel to the initial corner, and break the edge there.

%Break the edge into one path by removing a pixel adjacent to first corner
%If the corner is near the edge of the image, you would need to check for
%edge conditions
window = A_edges(first_corner(2)-1:first_corner(2)+1, first_corner(1)-1:first_corner(1)+1);
window(2,2) = 0; %Exclude the corner itself
[x, y] = find(window, 1);
A_edges(first_corner(2)+x-2, first_corner(1)+y-2) = 0;  

figure; imshow(A_edges);
hold on;
plot(first_corner(1), first_corner(2), 'r.', 'MarkerSize', 18)
hold off;

Now the distance from the initial point along the edge can only follow one path

%Find order the pixels along edge
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2));
figure; imagesc(D);

This gives us the desired ordering of edges

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1))));
A_corners = A_corners(corner_order, :);

figure; imshow(A_bw1);
hold on
plot(A_corners(:,1), A_corners(:,2),'r.', 'MarkerSize', 18)
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24);
hold off

This method also works on polygons that are unbalanced with respect to the centroid, such as the second demo image.

For fun, I present a third image, which has a vertex on the opposite side of the centroid, as a clearer example of an unbalanced polygon. My method also correctly parses this image.