shortest_path_select - Return vertices sorted

Question

I could select a couple of vertices and get the path by calling this:

bpy.ops.object.mode_set(mode = 'EDIT') 
bpy.ops.mesh.select_mode(type="VERT")
bpy.ops.mesh.select_all(action = 'DESELECT')
bpy.ops.object.mode_set(mode = 'OBJECT')
obj.data.vertices[0].select = True
obj.data.vertices[3].select = True
bpy.ops.object.mode_set(mode='EDIT')
bpy.ops.mesh.shortest_path_select()

Then I would get the path of vertices properly selected, I could get them in python by iterating through all of them and check if .select = True.

The problem I have is that I need the list of vertices sorted following the path, from the initial one to the last one, not the list sorted by the vertex index.

Is that possible with shortest_path_select ?

Answer 1

As of 3.5.1, there is no built-in function to fully handle this task. However, using v.link_edges to obtain the edges connected to a vertex offers significant utility. Summarizing how the code works, this method:

• uses bm.verts instead of obj.data.vertices and selects the shortest path

• enters a while loop to append to a sorted list (terminates when it reaches the final index)

• within the while loop I

  1. get the connected edge to the vertex in question (starts at initial vertex), which is the only linked edge that is also selected

  2. get the connected vertex to the vertex in question

  3. append the connected vertex to the sorted list and assign vertex in question to the freshly found connected vertex to use for the next iteration

  4. deselects the current connected edge so that the next connected edge can be found within the next iteration.

Note: Upon obtaining the vertices of the next edge, it's unknown whether verts[0] or verts[1] of this edge is truly the next connected vertex. Therefore, if the 0th vert is found to have already been sorted, the true next connected vert is guaranteed to be the 1st vert, otherwise it's the 0th vert.

import bpy
import bmesh

# get the mesh object 
obj = bpy.context.object

# choose initial and final indices
initial = 137
final  = 37

# select shortest path between starting and ending points
bpy.ops.object.mode_set(mode = 'EDIT')

# create sphere bmesh
me = obj.data
bm = bmesh.from_edit_mesh(me)

# make sure the BMesh is up-to-date
bm.verts.ensure_lookup_table()

# get bmesh verts
verts = bm.verts

# set mode to vert select 
bpy.ops.mesh.select_mode(type= 'VERT')

# deselect all
bpy.ops.mesh.select_all(action = 'DESELECT')

# select verts at these indices
v = verts[initial]
v.select = True
verts[final].select = True

# select shortest path
bpy.ops.mesh.shortest_path_select()

# initialize sorted vertices list
sorted_verts = [v]

# initialize set of indices that have already been sorted
sorted_indices = {initial}

# while loop to append to sorted verts
while v.index != final:

    # get connected edge as a single-element generator
    connected_edge = (e for e in v.link_edges if e.select)

    # get the edge itself
    e = next(connected_edge)

    # get 0th vert of the edge
    v = e.verts[0]
    
    # not gauranteed that verts[0] is the "next" vertex. It could just as well be verts[1]
    # rather check if index is in set of already sorted indices compared to checking if v is in sorted_verts list
    if v.index in sorted_indices:
        v = e.verts[1]
    
    # append to list and add to set
    sorted_verts.append(v)
    sorted_indices.add(v.index)
    
    # deselect connected edge
    e.select = False
 
print('\n------ sorted vertex indices --------')
for v in sorted_verts:
    print(v.index)

# may be of benifit to again select the shortest path for visualizations after the script has already ran   
#verts[initial].select = True
#verts[final].select = True
#bpy.ops.mesh.shortest_path_select()

As you can see, the magnitude of the printed indices decrease between some indices and increase between other indices in the sorted list, indicating this list is not sorted by the magnitude of the indices.

Image addressing the mistake I made caught by @MarkusVonBroady

Answer 2

This is how I would code it:

start = 0
end  = 3

import bpy, bmesh

bm = bmesh.from_edit_mesh(bpy.context.object.data)
bpy.ops.mesh.select_all(action = 'DESELECT')
bm.verts[start].select = True
bm.verts[end].select = True
bpy.ops.mesh.shortest_path_select()

indices = [start]
v = bm.verts[start]
edge = None
for _ in range(len(bm.verts)):  # protect from hanging
    edge = next(e for e in v.link_edges if e.select and e!=edge)
    v = edge.other_vert(v)
    indices.append(v.index)
    if v.index == end:
        break
print("Shortest Path - Vertex indices:", *indices, sep="\n")