Я использую NetworkX, opencv, numpy и python, чтобы найти shortest_path
на графике. Он не всегда дает то, что мне нужно. Функция shorttest_path находит путь от верха изображения до низа. Мой путь всегда меняется. Начальная точка и целевая точка всегда известны для каждого изображения. Таким образом, я хочу найти кратчайший путь между этими точками (начало и цель). Однако, когда исходная и целевая точки не являются узлами и не находятся в G, это не дает того, что мне нужно.
shortest_path(G, source=None, target=None, weight=None)
Как мне найти shortest_path
между двумя конкретными координатными точками на изображении? Более того, как я могу назначить координаты пикселя в качестве источника и цели? Например, источником является [45 66]
, а целью - [250 350]
.
@Sreekiran Ахах, спасибо, эта ссылка также принадлежит члену моей команды. Мы ее решили. Спасибо хоть.
Что касается второй проблемы, узел может иметь сколько измерений вы хотите. Например, рассмотрим следующую сетку.
import networkx as nx
g = nx.grid_2d_graph(2,2)
print(g.nodes()) #[(0, 0), (0, 1), (1, 0), (1, 1)]
print(g.edges()) #[((0, 0), (1, 0)), ((0, 0), (0, 1)), ((0, 1), (1, 1)), ((1, 0), (1, 1))]
print(nx.shortest_path(g, source=(0, 0), target=(1,0))) #[(0, 0), (1, 0)]
или с еще большими размерами:
g = nx.grid_graph(dim=[2,2,2,2])
g.nodes()
#[(0, 0, 0, 0), (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1), (1, 0, 1, 0), (0, 1, 1, 0), (1, 0, 1, 1), (0, 1, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1)]
По остальным вопросам:
Мой путь всегда меняется: это зависит от веса на ребрах, если кратчайший путь не уникален, это нормально, что он изменяется
когда исходная и целевая точки не являются узлами и не находятся в G: networkx находит кратчайший путь между 2 узлами G, если узлы не в G, это не сработает
Извините за неправильное выражение. За высказывание «Мой путь всегда меняется»: он меняется, потому что меняются образы. Я пытался сказать, что мой путь может начинаться справа налево, сверху вниз и наоборот. Я просто подумал, что могу использовать G.add_nodes_from()
для получения начальных и целевых точек в качестве узлов в G, не так ли? Наконец, как я могу использовать ваше решение для назначения координат начала и цели в качестве источника и цели? Насколько я понимаю, ваше решение просто находит кратчайший путь между случайными точками.
Есть много способов добавления узлов и ребер, вы можете выбрать тот, который вам больше нравится. Мне неясен ваш последний вопрос, но если узел является координатой (x, y) в возвращенном кратчайшем пути, у вас будут эти точки, которые вы можете использовать напрямую.
Нет, к сожалению, координата (x, y) не является кратчайшим путем. Таким образом, хотя кратчайший путь и приводит к верному решению технически, это не мой путь. Мой путь должен быть между (X1, Y1) и (X2, Y2). От (X1, Y1) до (X2, Y2). В общем, я хочу найти кратчайший путь между этими точками.
Для достижения результата можно использовать
skimage.graph
. Обратитесь к этому ответу