Finding face vertices of a polygon

consider the following 5 by 2 matrix that contains the indices of the nodes of a polygon:

N = [...
    5 12
    5 11
    6 8
    12 8
    11 6];

each row in N contains the node indices of the polygon's edges, but they are not ordered. For example, the first edge of the polygon connects the nodes number 5 and 12 and the 4th edge connects nodes number 12 and 8.

I am looking for the closed loop in this matrix without any further considerations,i.e. the starting point is not important nor is the direction of the path (clockwise or counterclockwise).

For N, a good possible answer is:

p = [5 12 8 6 11]

Also any cyclic permutation of p and its fliped version are acceptable.

My actual problem involves lots of these polygons, but non of them has more than 10 edges.

I have tried for loops for each polygon, but it turns out to be time consuming. Is there any better way to do so, timewisely? what would be the best approach to this problem?

Answer 1

[Bruno Luong]

If you have R2021a or later, there is a new method allcycles that can achieve the goal

N = [...
    5 12
    5 11
    6 8
    12 8
    11 6];
G = graph(N(:,1),N(:,2));
G.allcycles

ans = 1×1 cell array
    {[5 11 6 8 12]}

Answer 2

[Matt J]

My spatialgraph2D class might be applicable, assuming the polygon edges are non-intersecting:

https://www.mathworks.com/matlabcentral/fileexchange/73630-spatialgraph2d

In particular the polyshape method will return the index list of all polygon tiles in the graph, in counter-clockwise order.

[~,p]=polyshape(obj)

[saeed oveisi]

thank you

that works fine. I am implementing the idea behind this class and employ it into my cod to make the best out of it. I will share the final Idea if I make any important changes.

thanks alot

[Matt J]

You're quite welcome, but please Accept-click the answer if you consider the question resolved.

[Oskar Cheong]

hello @Matt J,

thank you again for the code. I also have the same problem as saeed and your code helped me resolve it. However I still have problems when it comes to bigger polygons >10. I disregarded any x and y coordinates as I already have all nodes and vertices and only interested in the connection.

However as you can see in the figure attached, while in the picture (though I did not put any x or y coordinates) it shows that 1-->5--> 8-->23-->17-->16-->25-->13-->9-->7-->2 are connected (which is correct.) But the code does not give me any polygon of that order or size.

Is it because the cooridnates are necessary?

Thank you!:)

Best,

Oskar

[Oskar Cheong]

Also does it work for periodic boundary conditions? :)

[Matt J]

@Oskar Cheong I'm not sure what periodic boundary conditions means, but I would guess that it does not.

Answer 3

[Matt J]

You cannot do what you propose with just a list of vertex indices. You need the x,y coordinates of the vertices themselves. Given that, convhull will readily provide you the index list in sorted order.

p = convhull(x,y)

[Bruno Luong]

Abstractly the problem is equivalent to "just" finding cycles in a graph. No need for coordinates.

I would suggest an idea: using adjacent matrix, using "and-operator" to avoid using the same edge twice (regarless the direction) and iterate dultiplication 10 times and see if element on the diagonal appears (back to the same node).

[saeed oveisi]

thanks for your answer

actually I have that already. but thats not my concern. I only want to reorder the nodes and find the closed path that is enforced by the list. I am not looking for the convex hull.

[Matt J]

I only want to reorder the nodes and find the closed path that is enforced by the list. I am not looking for the convex hull.

Then your polygons are not convex? If they are convex, then it is irrelevant that you are not looking for the convex hull. The point is that convhull() will reorder the vertices for you in a cyclic ordering.