[已解決]請教關於QGIS道路路徑尋找 主要為Python語言


目前接觸QGIS
雖然有內建的工具能找到路徑
但畢竟是公司所需 自己的代碼後續如有其他功能比較好調整

問題敘述:
圖片上的黑色英文字母為該紅色線段的ID
紅色圓圈為點交接的位置
黃色點不管
紅色線段有可能有兩頭交接點的值抑或是只有一頭交接點的值

需要的功能:
給定一個起點跟終點分別為圖片上的A跟H
輸出為A–>C–>E–>H
路徑不可返回
不需要最佳路徑

#這是紅色線段的來源資料
#KEY表示ID 意旨圖片上黑色字母
#VALUE表示交接點接觸到的線段
#以圖片上B來說 只有一頭接到A跟C 所以VALUE為[['A','C']]
#以圖片上C來說 一頭交接點上有A跟B交接 另一頭交接點上有E,F,G交接 
#所以VALUE為[['A','B'],['E','F','G']]
line_dict={
'A':[['B','C']],
'B':[['A','C'],
'C':[['A','B'],['E','F','G']],
'E':[['C','F','G'],['I','H']],
'F':[['C','E','G']],
'I':[['H','E']],
'H':[['I','E']],
'G':[['E','F','C']],
}
#如果說有更簡易的方式
#來源資料我這邊可以調整資料格式

有嘗試過但是會將所經過的線加入OUTPUT或是說可以順利排除經過的點
但是始終跑不到H點寫到後面有點摸不著頭緒

這裡先說聲感謝!

Jason990420
最佳答案

只用 Python 代码来求解, 交点以各分支点的列表来表示.

from copy import deepcopy

def search(start, stop, passed=[], route=[]):
    print(f'start:{start}, stop:{stop}, passed:{passed}, route:{route}')
    passed = deepcopy(passed)
    route = deepcopy(route)
    route.append(start)
    if start == stop:
        return route
    lines = line_dict[start]
    for line in lines:
        path = line.copy()
        path.append(start)
        path.sort()
        path = tuple(path)
        if path in passed:
            continue
        passed.append(path)
        for point in line:
            if point in route:
                continue
            result = search(point, stop, passed, route)
            if result:
                return result
    return []

line_dict={
    'A':[['B','C']],
    'B':[['A','C']],
    'C':[['A','B'],['E','F','G']],
    'E':[['C','F','G'],['I','H']],
    'F':[['C','E','G']],
    'I':[['H','E']],
    'H':[['I','E']],
    'G':[['E','F','C']],
}

result = search('A', 'H')

print(result)
start:A, stop:H, passed:[], route:[]
start:B, stop:H, passed:[('A', 'B', 'C')], route:['A']
start:C, stop:H, passed:[('A', 'B', 'C')], route:['A']
start:E, stop:H, passed:[('A', 'B', 'C'), ('C', 'E', 'F', 'G')], route:['A', 'C']
start:I, stop:H, passed:[('A', 'B', 'C'), ('C', 'E', 'F', 'G'), ('E', 'H', 'I')], route:['A', 'C', 'E']
start:H, stop:H, passed:[('A', 'B', 'C'), ('C', 'E', 'F', 'G'), ('E', 'H', 'I')], route:['A', 'C', 'E']
['A', 'C', 'E', 'H']
1周前 评论
Jason990420 (作者) 1周前
a1016233 (楼主) 1周前
a1016233 (楼主) 1周前
讨论数量: 5

说个题外的话,对你们那边生活有影响吗?

1周前 评论
Jason990420

只用 Python 代码来求解, 交点以各分支点的列表来表示.

from copy import deepcopy

def search(start, stop, passed=[], route=[]):
    print(f'start:{start}, stop:{stop}, passed:{passed}, route:{route}')
    passed = deepcopy(passed)
    route = deepcopy(route)
    route.append(start)
    if start == stop:
        return route
    lines = line_dict[start]
    for line in lines:
        path = line.copy()
        path.append(start)
        path.sort()
        path = tuple(path)
        if path in passed:
            continue
        passed.append(path)
        for point in line:
            if point in route:
                continue
            result = search(point, stop, passed, route)
            if result:
                return result
    return []

line_dict={
    'A':[['B','C']],
    'B':[['A','C']],
    'C':[['A','B'],['E','F','G']],
    'E':[['C','F','G'],['I','H']],
    'F':[['C','E','G']],
    'I':[['H','E']],
    'H':[['I','E']],
    'G':[['E','F','C']],
}

result = search('A', 'H')

print(result)
start:A, stop:H, passed:[], route:[]
start:B, stop:H, passed:[('A', 'B', 'C')], route:['A']
start:C, stop:H, passed:[('A', 'B', 'C')], route:['A']
start:E, stop:H, passed:[('A', 'B', 'C'), ('C', 'E', 'F', 'G')], route:['A', 'C']
start:I, stop:H, passed:[('A', 'B', 'C'), ('C', 'E', 'F', 'G'), ('E', 'H', 'I')], route:['A', 'C', 'E']
start:H, stop:H, passed:[('A', 'B', 'C'), ('C', 'E', 'F', 'G'), ('E', 'H', 'I')], route:['A', 'C', 'E']
['A', 'C', 'E', 'H']
1周前 评论
Jason990420 (作者) 1周前
a1016233 (楼主) 1周前
a1016233 (楼主) 1周前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!