Есть многоугольник внутри которого разрешено перемещение. Есть 2 точки А

Question

Есть многоугольник внутри которого разрешено перемещение. Есть 2 точки А

и Б. Из точки А нужно попасть в точку Б кротчайшим возможным путем , который обозначается как а->х13у13->x14y14->x15y15->x16y16->B
Как такое решить? Я понимаю как например вдоль многоугольника обойти, но как вот точку х13у13 найти я не понимаю. Если что в проекте уже есть библиотека shapely с помощью которой строится многоугольник

#backend #programming #python #russian

0

13.11.2021

4 ответов

21 просмотр

evgeniy

Думаю, надо хранить все линии, составляющие контур многоугольника и при попытке добраться из точки А в точку В проверять не произошло ли пересечения одной из линий. Если произошло, значит этот путь закрыт, ищем другой.

0

13.11.2021

evgeniy

Например, Дейкстрой. У тебя задача найти кратчайший путь между точками, с дополнительным условием - без пересечений линий. Строишь матрицу смежности каждой точки со всеми остальными, там где есть пересечения связи между точками не ставишь. Затем запускаешь для полученного графа Дейкстру и ищешь кратчайший путь.

0

13.11.2021

first last Автор вопроса

evgeniy
Например, Дейкстрой. У тебя задача найти кратчайши...

ого спасибо

0

13.11.2021

Александр Попов · Accepted Answer

Александр Попов

Хватит уже постить задачи в чат по помощи. Это не чат по решению задач

0

13.11.2021

170 похожих чатов

Есть многоугольник внутри которого разрешено перемещение. Есть 2 точки А

4 ответов

Похожие вопросы