поиск кратчайшего пути на карте, представленной в виде двумерных фигур

Question

У меня есть небольшая библиотека нескольких алгоритмов поиска кратчайшего пути. Они были разработаны для простых неориентированных графов (нормальное представление - вершины и ребра). Теперь я хотел бы как-то применить их в немного другом сценарии - где карты представлены в виде двухмерных фигур, соединенных общими ребрами (то есть ребрами многоугольников). В этом случае поиск может начинаться / заканчиваться либо на объекте карты, либо в некоторой точке (x, y). Какой будет лучший подход? Попробуйте применить алгоритмы к фигурам? или попытаться извлечь «нормальный» график из фигур (у меня есть время предварительной обработки)? Любой совет будет высоко ценится, так как я действительно не уверен, каким путем идти, и у меня нет достаточно времени (и навыков), чтобы изучить много вариантов ...

Большое спасибо

Answer 1

Какой «путь» вы ищете? Список фигур для прохождения? (В противном случае вы просто проводите прямую линию между начальной и конечной точками.)

Легко предварительно обработать его в формате, где фигуры являются вершинами и соединены ребрами, когда фигуры имеют общую сторону многоугольника. Затем просто передайте его существующей библиотеке, чтобы получить ответ.