Как определить параметры источника и цели как массив для кратчайшего пути?

Я использую NetworkX, opencv, numpy и python, чтобы найти shortest_path на графике. Он не всегда дает то, что мне нужно. Функция shorttest_path находит путь от верха изображения до низа. Мой путь всегда меняется. Начальная точка и целевая точка всегда известны для каждого изображения. Таким образом, я хочу найти кратчайший путь между этими точками (начало и цель). Однако, когда исходная и целевая точки не являются узлами и не находятся в G, это не дает того, что мне нужно.

shortest_path(G, source=None, target=None, weight=None)

Как мне найти shortest_path между двумя конкретными координатными точками на изображении? Более того, как я могу назначить координаты пикселя в качестве источника и цели? Например, источником является [45 66], а целью - [250 350].

Для достижения результата можно использовать skimage.graph. Обратитесь к этому ответу

Sreekiran 14.06.2020 12:43

@Sreekiran Ахах, спасибо, эта ссылка также принадлежит члену моей команды. Мы ее решили. Спасибо хоть.

Ender Ayhan 15.06.2020 08:08
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
2
207
1

Ответы 1

Что касается второй проблемы, узел может иметь сколько измерений вы хотите. Например, рассмотрим следующую сетку.

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

Ender Ayhan 05.09.2018 00:15

Есть много способов добавления узлов и ребер, вы можете выбрать тот, который вам больше нравится. Мне неясен ваш последний вопрос, но если узел является координатой (x, y) в возвращенном кратчайшем пути, у вас будут эти точки, которые вы можете использовать напрямую.

abc 05.09.2018 00:18

Нет, к сожалению, координата (x, y) не является кратчайшим путем. Таким образом, хотя кратчайший путь и приводит к верному решению технически, это не мой путь. Мой путь должен быть между (X1, Y1) и (X2, Y2). От (X1, Y1) до (X2, Y2). В общем, я хочу найти кратчайший путь между этими точками.

Ender Ayhan 05.09.2018 00:25

Другие вопросы по теме