# Given a grouping of selected vertices in a mesh, how do I test if they form a contiguous edge loop?

I'd like to be able to run a a test on a grouping of selected vertices in a mesh. The function would return a boolean result based on whether all the vertices in the grouping are connected in a linear fashion, thereby forming an edge loop.

To the best of my knowledge, there is no IsEdgeLoop operator in the API at this time. Bmesh seems to have some better mesh tools, but I don't see a solution as of yet. I'm thinking some clever algorithm to traverse an array of vertex indices is required, but could use some input from others.

I'd implement the following algorithm:

1. Give each vertex a unique ID.
2. Choose one of your grouping's vertices, and add its ID to a set() S.
3. Check all vertices ID that are connected by an edge to (2). Add these IDs to S.
4. Are any of the IDs in (3) the same as the ID in (2)? If yes, Return True.
5. If not, for each in (3), recursively do steps 2-5. If you run out of edges/vertices, return False.

Note: you use the vertices IDs in S to avoid choosing already processed vertices in step 5.

EDIT:

Pseudo-code could be something like:

grouping = [ selected vertices in a mesh ]

S = set()

for v in grouping.vertices():
for vv in v.edges().vertex():
if vv.id in S:
return True
else:
return False

• Thanks for the suggestion. I'm just trying to process your method. It might be easier to grok if written in pseudocode? Just a thought. – Todd McIntosh Jun 1 '15 at 18:10
• Doesn't every vertex already have a unique numeric ID just as a function of being in the mesh matrix? – Todd McIntosh Jun 1 '15 at 19:26
• Ok, thanks, I'm going to try to create a working python operator and see if this works. – Todd McIntosh Jun 2 '15 at 5:08
• neat, its basically the OSPF algorithm! edit: I guess I meant Dijkstra's algorithm – Kevin Milner Jan 3 '19 at 21:00

I did something similar for this addon and edited it.

import bpy
import bmesh

def is_edge_loop(bm):
nof_verts = 0
nof_leafs = 0
start = None

#maybe iterate over edges instead since edge count < vertex count
for vertex in bm.verts:
if vertex.select:
nof_verts += 1
vertex.tag = False

count = 0
if edge.select:
count += 1

if count == 1:
nof_leafs += 1
if start is None:
start = vertex
elif nof_leafs > 2:
return "More than two leaves"

elif count == 2:
if not vertex.is_boundary and not len(vertex.link_edges) == 4:
return "Not boundary and not linked to four edges"
if nof_leafs == 0 and start is None:
start = vertex

else:
return "Invalid edge count: %d" % count
if nof_leafs == 1:
return "Only one leaf"

#there might be additional independent cyclic loops

vertex = start
vertex.tag = True
prev_edge = None
count = 0

while(count < nof_verts - 1):
if edge.select:
w = edge.other_vert(vertex)
if not w.tag:
if count and edges_share_face(edge, prev_edge):
return "edges share face"
vertex = w
vertex.tag = True
prev_edge = edge
count += 1
break
else:
return "Can not find vertex to advance to"
return True

def edges_share_face(e1, e2):
return any(f1 == f2