Как разложить карту в ячейке?

Question

После того, как было возможно рассчитать кратчайшее расстояние, используя алгоритм Диджстры, подающий ручную вершину (получение lat и long от карт google), я ищу более динамичный способ сделать то же самое. Предполагая, что у меня есть файл формы, представляющий мою карту (с границами и препятствиями), какой алгоритм я могу использовать для ее разложения? Поймать немного, я нашел, что должен делать «декомпозицию клеток», но, честно говоря, я не понял, как это сделать?

спасибо.

Answer 1

Если у вас есть только препятствия в файле формы, вы можете построить график видимости и использовать dijkstra на этом.

Если у вас есть регионы с различным passabilities, чем вы должны использовать некоторые более сложные методы, например, покрой его с некоторой сеткой (rectangualr или треугольным), чем триангуляции, назначить весы это кромки, и чем использование Дейкстрой тоже