Как найти конкретные точки / координаты в кратчайшем пути?

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)

Edit: вот выходные данные, которые обеспечивают поворотные точки и узлы отдельно

636 1

numpy matplotlib python-2.7 networkx

1 ответ:

Comments

Ничего не найдено.

xdze2 · Accepted Answer · 2018-09-01 21:53:37

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

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

Из примера , приведенного в sknw readme, я пытался воссоздать ваш:
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