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



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

кратчайший путь визуализируется красными узлами

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

отмечены синими кругами

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

cropped_image

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

#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: вот выходные данные, которые обеспечивают поворотные точки и узлы отдельно выход

184   1  

1 ответ:

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

В зависимости от того, каково ваше фактическое определение для этих точек, метод может заключаться в упрощении пути с помощью алгоритма Дугласа-Пекера, используя 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
    Ничего не найдено.

Добавить ответ:
Отменить.