How do you order the vertices of a non-convex polygon?

I have a polygon defined by a logical cellular grid, 'polygon', and the cells that have an edge or corner touching the polygon, 'edges'. I need the vertices of the perimeter ('edges') in order going around the polygon, either cw or ccw. The way I find them now does not put them in order.

I've tried to use bwboundaries & bwtraceboundary. I attached the closest that I've come up with, but you'll see that a couple of vertices are missing.

Answer 1

[John D'Errico]

Simplest is to use a traveling salesman solver.

theta = linspace(pi/2,-pi/2,10)';
xy = [0 0; 1 1; 0 1; 1 0;1 - cos(theta)/3,.5 + sin(theta)/3];
xy = xy(randperm(14),:); % just to make it worse.
plot(xy(:,1),xy(:,2),'o-')

Now just find a TSP solver. Anyone will do. tspo_ga (written by Joseph Kirk) just happens to be one I had downloaded from the FEX recently.

points.XY = xy;
P = tspo_ga(points);

plot(xy(P.optRoute,1),xy(P.optRoute,2),'o-')

This is an open TSP solver, so you could connect the first and last points to create a closed polygon.

[Rose Palermo]

Unfortunately, I don't think a traveling salesmen solution will work for this problem. I'm using these polygons to represent lakes (polygon) and shorelines (edges), so line segments cannot cross. So there is a unique solution that might not be captured by the TSP solver.

[John D'Errico]

In general, a TSP solution (once the optimal solution has been found) will not cross edges. If there were edges that would cross, then there is a better solution that does not cross. You can probably prove this. So a solution that has crossed edges should not be truly optimal.

[Leo Carrera]

Get the center of mass of all the points you have (with mean() )

Then, calculate the angle (with atan2) between each point and the center of mass (in x and y)

Sort the angles from the smallest to the greatest and get the indexes

Finally, sort your vertices with the indexes and plot normally

Answer 2

[Walter Roberson]

Have you tried boundary() and changing the alpha value to make a tighter fit?