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

Question

Rose Palermo 2018-4-15

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/395088-how-do-you-order-the-vertices-of-a-non-convex-polygon

评论： Leo Carrera 2020-10-30

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

John D'Errico 2018-4-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/395088-how-do-you-order-the-vertices-of-a-non-convex-polygon#answer_315263

在 MATLAB Online 中打开

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.

3 个评论
显示 1更早的评论隐藏 1更早的评论

John D'Errico 2018-4-16

编辑：John D'Errico 2018-4-16

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 2020-10-30