Dijkstra.py

It takes significant time to compute. hahaha...

import bmesh
import math


class VDijkstra:
    def __init__(self, vert):
        self.id = vert.index
        self.v = vert
        self.bestParent = None
        self.dist2start = float('inf')
        self.distances = {}
        # init peers
        self.peers = set()
        for e in self.v.link_edges:
            v_other = e.other_vert(self.v)
            self.peers.add(v_other.index)
            dX = v_other.co[0] - self.v.co[0] 
            dY = v_other.co[1] - self.v.co[1] 
            dZ = v_other.co[2] - self.v.co[2] 
            d = math.sqrt(dX*dX + dY*dY + dZ*dZ) 
            self.distances[v_other.index] = d
        print('vds['+str(self.id)+'].peers = '+str(self.peers))
 
def getDistance(v0, v1):
    dX = v0.co[0] - v1.co[0] 
    dY = v0.co[1] - v1.co[1] 
    dZ = v0.co[2] - v1.co[2] 
    return math.sqrt(dX*dX + dY*dY + dZ*dZ) 

#def procDijkstra(vds, H, A, start, goal):
def procDijkstra(vds, H, A, start, goal, depth=0):
    print('---------------------------------------------')
    print('depth: '+str(depth))
    if vds[goal].bestParent is not None:
        print('alreadily reached the goal.')
        return
    #
    d_min_i = None
    d_min_p = None
    d_best = float('inf')
    for i in A:
        vd = vds[i]
        w = vd.peers.intersection(H)
        #print('w = '+str(w))
        for p in w:
            vp = vds[p]
            d = vd.distances[p] + vp.dist2start
            if d < d_best:
                print('found best')
                d_best = d
                d_min_i = i
                d_min_p = p
    vds[d_min_i].dist2start = d_best
    vds[d_min_i].bestParent = d_min_p
    if d_min_i == goal:
        vds[goal].bestParent = d_min_p
        return
    #
    H.add(d_min_i)
    A.remove(d_min_i)
    A = A.union(vds[d_min_i].peers - H)
    #
    print('d_min_i = '+str(d_min_i))
    print('d_min_p = '+str(d_min_p))
    print('H = '+str(H))
    print('A = '+str(A))
    procDijkstra(vds, H, A, start, goal, depth+1)
    return

def djk(start, goal):
    bpy.ops.object.mode_set(mode="OBJECT")
    o = bpy.context.scene.objects.active
    b = o.data
    bm = bmesh.new()
    bm.from_mesh(b)
    bm.verts.index_update()
    #
    nVerts = len(bm.verts)
    vds = []
    for i in range(len(bm.verts)):
        vds.append(VDijkstra(bm.verts[i]))
    #
    print("num verts = "+str(len(vds)))
    #
    H = set()
    A = set()
    # 
    H.add(vds[start].id)
    H = H.union(vds[start].peers)
    s = set()
    for i in H:
        s = s.union(vds[i].peers)
        vds[i].dist2start = getDistance(vds[i].v, vds[start].v)
        vds[i].bestParent = start
    print('H = '+str(H))
    A = s - H
    print('A = '+str(A))
    #
    procDijkstra(vds, H, A, start, goal)
    i = goal
    while True:
        bpy.context.object.data.vertices[i].select = True
        if start == i:
            break
        print(str(i)+' -> '+str(vds[i].bestParent))
        i = vds[i].bestParent
    bpy.ops.object.mode_set(mode="EDIT")