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

i have images includes both convex non-convex polygons. each image contains 1 polygon. need detect corner coordinates , need sort them in clock-wise or counter-clockwise order. convex polygons, use harris corner detection detecting corners , convexhull sorting points. dont have idea on how sort non-convex polygon. inputs images, think image processing technique might sort them out moving alongside edge of polygon. there way least complexity?

example image:

i have named corners randomly.

expected output:

i expect corner coordinates in order 1 3 5 9 4 2 8 7 6 10 or 1 10 6 7 8 2 4 9 5 3. can start @ point, not 1

edit 1:

after rayryeng's solution, works convex polygons non-convex polygon, there non-convex polygons doesn't go algorithm.

here example

another approach use bwdistgeodesic find order corners distance along edge. should work polygon can detect continuous edge.

we start loading in image stack overflow , converting black , white image make easier find edge

a = imread('http://i.stack.imgur.com/dpbpp.jpg'); a_bw = im2bw(a,100/255);  %binary image a_bw1 = imcomplement(a_bw);   %inverted binary image 

the bwmorph function provides lot of options manipulating black , white images. we're going use remove option find edge of our polygon, use edge detector if prefer.

%find edges a_edges = bwmorph(a_bw, 'remove'); [edge_x, edge_y] = find(a_edges'); 

let's visualize edges detected

figure; imshow(a_edges); 

okay, have nice clear continuous edge. let's find corners. use corner, substitute 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 might not notice, not directly on edges. i'll start finding closest point along edge each corner point, , i'll visualize corners in red , 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 distance around edge each corner, we'll use corner point approximation, a_edge_corners (green point) on edge rather corner point a_corners (red point).

now have pieces need use bwdistgeodesic. function finds distance seed point each non-zero pixel in black , white image. interested in distance initial corner each point on edge. let's try out.

% calculate distance seed corner first_corner = a_edge_corners(1,:); d = bwdistgeodesic(a_edges, first_corner(1), first_corner(2)); figure; imagesc(d); 

we're starting right corner , pixels moving away corner increase in value. isn't quite want. if order corners using these values, end ordering in distance 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 problem, have break edge ordering goes in 1 direction initial point. if interested in clockwise or counter-clockwise ordering, need break edge according set of rules depending on orientation of edge. if direction doesn't matter can find adjacent pixel initial corner, , break edge there.

%break edge 1 path removing pixel adjacent first corner %if corner near edge of image, need check %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 corner [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 distance initial point along edge can follow 1 path

%find order pixels along edge d = bwdistgeodesic(a_edges, first_corner(1), first_corner(2)); figure; imagesc(d); 

this gives 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 works on polygons unbalanced respect centroid, such second demo image.

for fun, present third image, has vertex on opposite side of centroid, clearer example of unbalanced polygon. method correctly parses image.