如何在shortest_path中找到特定点/坐标？

Question

我正在使用NetworkX，numpy和sknw module来寻找迷宫的shortest_path。最短路径算法得到我想要的结果，我可以画出包含节点的路径。然而，我想在这条路径上找到另一个点，但它们不是最短路径中的节点。下面是使用just found nodes指定的最短路径：

​

​

这是我需要的：

​

​

原图如下：

​

​

找到这些点并将它们绘制为图像中的红色节点的方法是什么？以下是代码(编辑后)：

#Skeletonize the Thresholded Image
skel = skeletonize(threshold2)
#Build Graph from skeleton
graph = sknw.build_sknw(skel, multi=False)
G = nx.Graph(graph)
#Find the shortest path
path = nx.shortest_path(G,source=0,target=len(G)-1)
path_edges = zip(path,path[1:])
plt.imshow(img, cmap='gray') 

def nodes_edges(G,n):

    for (s,e) in path_edges:
        ps = graph[s][e]['pts']
        plt.plot(ps[:,1], ps[:,0], 'green')
        # Find the "corner points" and plot:
        tolerance = 30
        simple_polyline = approximate_polygon(ps, tolerance)
        plt.plot(simple_polyline[1:-1, 1], simple_polyline[1:-1, 0], '.m')
    node = G.node
    ps = np.array([node[i]['o'] for i in path])
    plt.plot(ps[:,1], ps[:,0], 'r.')
    plt.axis('equal')
    plt.show()

    print(ps)
    print('Number of Element = ',len(ps))
    print('Number of Step = ', 
    nx.shortest_path_length(G,source=0,target=len(G)-1))
    print('Path Edges = ', path_edges)
    print('Shortest Path = ', path)
    return(n)

nodes_edges(graph,skel)

编辑:以下是分别提供转折点和结点的输出

​

Answer 1

您要查找的“角度”点并未定义为用于构建图形的“交叉点”。因此，不能使用相同的方法找到它们。

根据您对这些点的实际定义，一种方法可能是使用Douglas-Peucker algorithm简化路径，在skimage中使用approximate_polygon (请参阅demo here)。为此，必须选择公差参数。

从sknw自述文件中给出的example，我尝试重新创建您的：

import numpy as np
import matplotlib.pylab as plt

from skimage.morphology import skeletonize
from skimage import data
import sknw
import networkx as nx
from skimage.measure import approximate_polygon

# open and skeletonize
img = data.horse()
ske = skeletonize(~img).astype(np.uint16)

# build graph from skeleton
graph = sknw.build_sknw(ske)

# draw image
plt.imshow(img, cmap='gray')

# draw edges by pts
for (s,e) in graph.edges():
    polyline = graph[s][e]['pts']
    plt.plot(polyline[:,1], polyline[:,0], 'green', alpha=.6)

    # Find the "corner points" and plot:
    tolerance = 5
    simple_polyline = approximate_polygon(polyline, tolerance)
    plt.plot(simple_polyline[1:-1, 1], simple_polyline[1:-1, 0], '.m')


# draw node by o
node, nodes = graph.node, graph.nodes()
ps = np.array([node[i]['o'] for i in nodes])
plt.plot(ps[:,1], ps[:,0], 'r.')

# title and show
plt.title('Build Graph')
plt.show()

这就给出了：(洋红色的点是“角”点)

​

​

我认为它在迷宫图像上会工作得更好。

编辑，遍历路径的示例代码：

one_path = nx.shortest_path(graph, source=0, target=8)

full_line = []
for source, target in zip(one_path, one_path[1:]):
    polyline = graph[source][target]['pts']

    # Find the "corner point":
    tolerance = 5
    simple_polyline = approximate_polygon(polyline, tolerance)
    full_line.extend(simple_polyline[:-1])

full_line.append(simple_polyline[-1]) # add the last point
full_line = np.array(full_line)  # convert to an array