3
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

Shortest Path algorithms

Dijkstra's algorithm

enter image description here 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.

$\endgroup$
2
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.