Determine angular coordinates of a non-convex polygon clockwise MATLAB

Question

I have some images that include both convex and non-convex polygons. Each image contains exactly one polygon. I need to determine the angular coordinates and sort them clockwise or counterclockwise. For convex polygons, I use Harris corner detection to detect angles and convexhull to sort points. But I do not know how to sort a non-convex polygon. Since my inputs are images, I think some of the image processing methods can help you figure them out by moving along the edges of the polygon. Is there a way with the least difficulty?

Image example:

I called the angles randomly.

Expected Result:

I expect that the angular coordinates in this order are 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 time, not necessarily 1

Change 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 that don't go well with its algorithm.

Here is an example

Answer 1

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

We start by loading an image from Qaru and converting it to a black and white image to make it easier to find the 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 many possibilities for processing black and white images. We will use the remove option to find the edge of our polygon, but you can also use a different edge detector if you want.

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

Let us visualize the edges we discovered.

 figure; imshow(A_edges); 

Ok, we have a nice clear continuous rib. Now find the corners. I use corner , but you can replace your favorite angle detector

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

Let us visualize our initial angular 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 

Another thing that you might not notice is that they are not directly at the edges. To begin with, I will find the closest point along the edge to each corner point, and then visualize the corners in red and the closest border 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 will use the corner point approximation, A_edge_corners (green dot) on the edge, and not the A_corners corner dot (red dot) itself.

Now we have all the parts that we need to use bwdistgeodesic . This function finds the distance to the starting point for each non-zero pixel in a black and white image. We are interested in the distance from the starting angle to each point on the edge. Give it a try.

 % 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 start from the right-most corner, and pixels moving away from the corner increase. But this is not exactly what we want. If we order angles using these values, we get ordering at a distance from the starting 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 need to break the edge so that the ordering takes place only in one direction from the starting point. If you are interested in ordering clockwise or counterclockwise, you will need to split the edge according to a set of rules depending on the orientation of the edge. If the direction does not matter, you can just find the neighboring pixel in the starting corner and break it 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 starting point along the edge can follow only 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 edge order.

 [~, 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 with polygons that are not balanced with respect to the centroid, for example, in the second demo image.

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

Answer 2

This is a common problem when processing images. The typical answer is to find the center of gravity of the shape and find the angle between the centroid and each corner point. You must make sure that the angles are presented so that they are in the range of [0,360) degrees. When you have this, you sort the corners, then use the resulting order to determine the order of the points.

The image presented requires a bit of pre-processing, so I can start working on it. I read the image directly from StackOverflow, then invert the image so that the black star turns white. I also need to remove numbers, so I use bwareaopen to remove any small areas of text. After that, I perform angular detection on this image through corner , and I set QualityFactor to 0.3 so that I can detect 10 angles. In particular:

 %// Read image from StackOverflow im = rgb2gray(imread('http://i.stack.imgur.com/dpbpP.jpg')); %// Threshold the image and area open it im_thresh = im <= 100; im_open = bwareaopen(im_thresh, 50); %// Detect corner points out = corner(im_open, 'QualityLevel', 0.3); %// Show the image with the corner points imshow(im_open); hold on plot(out(:,1), out(:,2), 'r.') 

im_open contains our final processed image. This is what I get:

---

Now find the center of gravity. This can simply be done by finding the coordinates of non-zero locations and finding the average value for each dimension:

 [rows, cols] = find(im_open); cenX = mean(cols); cenY = mean(rows); 

cenX and cenY contain the locations (x,y) center of gravity of the image. To be sure that everything is in order with us:

 imshow(im_open); hold on; plot(cenX, cenY, 'r.', 'MarkerSize', 18); 

We get:

Very nice. Now out in the earlier code contains (x,y) points of corner points. All you have to do is determine the angle from the centroid to each corner point, and then sort the angles. You must use this sort order to rearrange the corner points to give you your ordered points. If you want to clockwise , you will need to sort the values ​​in ascending order . If you want counterclockwise , you need to sort it in descending order . I will leave it to you on what you want to solve, but I will write a code that will allow you to do both. So just do the following:

 %// Determine angles (in degrees) angles = atan2d(out(:,2) - cenY, out(:,1) - cenX); %// Any negative angles, add 360 degrees to convert to positive angles(angles < 0) = 360 + angles(angles < 0); %// Sort the angles [~,ind] = sort(angles); %// clockwise %[~,ind] = sort(angles, 'descend'); %// counter-clockwise %// Re-arrange the corner points to respect the order out_reorder = out(ind,:); 

Now the final test is to draw these points, and also make a number next to each point to see if we understood it correctly. It can be done:

 %// Show image imshow(im_open); hold on; %// Show points plot(out_reorder(:,1), out_reorder(:,2), 'r.', 'MarkerSize', 18); %// Place a textbox at each point and show a sequence number for idx = 1 : size(out_reorder,1) text(out_reorder(idx,1), out_reorder(idx,2), num2str(idx), 'FontSize', 24, 'Color', 'green'); end 

We get:

Looks nice! So out_reorder gives you corner points to execute either clockwise or counterclockwise. Each line that you come across sequentially gives you the next point, which naturally follows the clockwise or counterclockwise direction you are looking for.

Also note where the numbering starts. Angle 0 is defined by a horizontal line that points east relative to the center of gravity. Therefore, the closest point to 0, when we start in ascending order, is the number where you see number 1. After 1, you see that it scrolls clockwise until we finish the corner points.