Basically I am trying to replace a call to bpy.ops.mesh.shortest_path_select()
in an Add-on of mine. While many bpy.ops.mesh
operations have a bmesh
equivalent, the selection of the shortest path between two verts is something I haven't found anywhere in the bmesh documentation. Maybe I just missed it, but nothing sticks out to me as an obvious solution.
-
1$\begingroup$ en.wikipedia.org/wiki/Shortest_path_problem#Algorithms $\endgroup$ – batFINGER Jul 11 '20 at 17:51
Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbours.
Here is a bmesh
take on this. The algorithm calculates the shortest path from source vert to all verts.
To clean this up would prob make a class of the method, that once built would return this info
import bmesh
import bpy
from math import inf
class Node:
@property
def edges(self):
return (e for e in self.vert.link_edges if not e.tag)
def __init__(self, v):
self.vert = v
self.length = inf
self.shortest_path = []
def dijkstra(bm, v_start, v_target=None):
for e in bm.edges:
e.tag = False
d = {v : Node(v) for v in bm.verts}
node = d[v_start]
node.length = 0
visiting = [node]
while visiting:
node = visiting.pop(0)
if node.vert is v_target:
return d
for e in node.edges:
e.tag = True
length = node.length + e.calc_length()
v = e.other_vert(node.vert)
visit = d[v]
visiting.append(visit)
if visit.length > length:
visit.length = length
visit.shortest_path = node.shortest_path + [e]
visiting.sort(key=lambda n: n.length)
return d
# test call select two verts edit mode
context = bpy.context
ob = context.object
me = ob.data
bm = bmesh.from_edit_mesh(me)
v1, v2 = bm.select_history[-2:]
# calc shortest paths to one vert
nodes = dijkstra(bm, v1)
# specific target vert (quicker)
#nodes = dijkstra(bm, v1, v_target=v2)
# results of other vert
node = nodes[v2]
print(node.length, node.shortest_path)
for e in node.shortest_path:
e.select_set(True)
bmesh.update_edit_mesh(me)
Notes. Added option to target a destination vert to yield when the result for that vert is reached.
Another addition would be to save the alternative route when the distances match. Multiplying each node in the resultant path will give the combinations of possible routes.
-
1$\begingroup$ Awesome answer as always! From first tests, this seems to be the algorithm that Blender uses internally as well, though I can't really tell from browsing the source code, my C++ Voodoo isn't sufficient to tell. $\endgroup$ – aliasguru Jul 12 '20 at 17:59
-
$\begingroup$ Thanks. It's fun coding these things. Leads to a question re the persistence of bmesh tags. Had a fiddle with adding alternate paths and global edge lengths. $\endgroup$ – batFINGER Jul 12 '20 at 18:24