Как найти конкретные точки / координаты в shorttest_path?

Question

Я использую модуль NetworkX, numpy и sknw , чтобы найти shortest_path лабиринта. Алгоритм кратчайшего пути дает то, что я хочу, и я могу нарисовать путь с помощью узлов. Однако есть и другие моменты, которые я хочу найти на этом пути, но они не являются узлами в кратчайшем пути. Вот кратчайший путь, указанный только что найденными узлами:

Вот что мне нужно:

Вот оригинальное изображение:

Как найти эти точки и нарисовать их в виде красных узлов на изображении? Вот код (отредактированный):

#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

«Угловые» точки, которые вы хотите найти, не определены как «пересечения», используемые для построения графика. Поэтому их нельзя найти одним и тем же методом.

В зависимости от того, что вы на самом деле определяете для этих точек, можно было бы упростить путь, используя алгоритм Дугласа-Пекера , используя approximate_polygon в skimage ( см. демоверсию здесь ). Для этого необходимо выбрать допуск.

Из примера , приведенного в файле readme sknw, я попытался воссоздать ваш:

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()

, который дает: (пурпурные точки являются «угловыми» точками)

Я думаю, что это будет работать намного лучше на изображении лабиринта.

edit, пример кода для итерации по пути:

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