Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > преобразование дорожной сети в граф

Автор: motorway 30.9.2009, 18:01

Есть карта дорожной сети, на которой показаны улицы. Их можно определить по цвету. Точнее, если не серый, то в данном месте проходит улица. Правда, еще нужно учитывать толщину. Как можно преобразовать всю эту сеть в граф, чтобы можно было определить расстояния между 2 точками по улицам, и как найти потом самое короткое расстояние среди всех возможных маршрутов между 2 точками?

Автор: Toktik 30.9.2009, 22:01

Исползуй алгоритм Дейкстры.

Автор: motorway 30.9.2009, 22:37

Спасибо. Сложнее будет преобразовать саму сеть в граф. Можно попиксельно перебирать картинку и что-то строить, но способ довольно муторный. Может, есть идеи? Особенно проблема с кривыми улицами

Автор: Pavia 30.9.2009, 23:26

Цитата(motorway @ 30.9.2009, 22:37

)

Поиск в графе вы все равно при помощи волны будете делать так что особого смысла переводить в граф я не вижу. И сразу использовать волновой алгоритм на картинке. А если хотите строить граф то опять таки волновой алгоритм(в сети глянь волновой алгоритм скелетизации).

Автор: motorway 30.9.2009, 23:55

Цитата

И сразу использовать волновой алгоритм на картинке

Примерный смысл поясните, как предлагается это делать. Допустим, у вас есть такая карта улиц.

Добавлено через 5 минут и 29 секунд
Похоже, этот алгоритм весьма сложен. И для моей задачи можно обойтись чем-то другим. Просто усредненное что-то брать (расстояния и т.п.). В общем, граф долго делать...

Автор: Pavia 1.10.2009, 11:32

motorway, Обычный алгоритм волны который в интернете сто раз описан.
Берем точку на карте смотрим если желтого цвета то начинаем выполнять алгоритм.
Помечаем эту точку как пройденную ставим время 0. пробуем 4 соседних точек если они желтые и не помеченные то заносим в массив.
Рекурсивно вызываем нашу функцию поиска. Она перебирает все точки смотрит для каждой есть ли соседи уже помеченные и выбирает с наименьшим числом заносим это число+1. и тд пока не дойдем до конечной.

Обход в глубину получается.