How do you order the vertices of a non-convex polygon?
19 ビュー (過去 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 件)
John D'Errico
2018 年 4 月 15 日
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 件のコメント
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 日
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
Walter Roberson
2018 年 4 月 15 日
Have you tried boundary() and changing the alpha value to make a tighter fit?
0 件のコメント
参考
カテゴリ
Help Center および File Exchange で Elementary Polygons についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!