Алгоритм преобразования дорожной сети в граф, для поиска пути - PHP

motorway · 30.09.2009, 19:06

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

SkyM@n · 01.10.2009, 00:06

Нет, тут надо устанавливать отдельный программный комплекс:
mapserver. Очень мощная штука, сам пользуюсь активно. Советую применять его с OpenLayers

SkyM@n · 01.10.2009, 00:06

Нет, тут надо устанавливать отдельный программный комплекс:
mapserver. Очень мощная штука, сам пользуюсь активно. Советую применять его с OpenLayers

motorway · 01.10.2009, 15:53

Конечно, хорошо, но долго ли в ней нужно разбираться, чтобы сделать мою задачу? В общем, может придется обойтись другими методами, или вообще упростить задачу, не строя граф. Например, для получения времени проезда можно обойтись средними расстояниями.

SkyM@n · 01.10.2009, 17:06

Цитата:

Сообщение от motorway

Конечно, хорошо, но долго ли в ней нужно разбираться, чтобы сделать мою задачу? В общем, может придется обойтись другими методами, или вообще упростить задачу, не строя граф. Например, для получения времени проезда можно обойтись средними расстояниями.

Покопаться таки придется в ней.
Но если вам не нужно такого функционала - то пробуйте другие методы

motorway · 01.10.2009, 22:04

По идее, если все четко делать, он мог бы быть нужен, функционал этот. Но можно зашиться. А все-таки было бы интересно автоматизированно преобразовывать, напр. Яндекс карту Москвы в граф

wall66 · 01.10.2009, 22:09

Цитата:

Сообщение от motorway

напр. Яндекс карту Москвы в граф

яндекс карты уже имеют развитую систему прокладывания путей по дорогам, так что делать это, опятьже, бессмысленно

надеюсь, вы когда-нибудь сможете отличить полезные дела от таковыми не являющихся

motorway · 02.10.2009, 18:53

в данном случае Яндекс карты - просто полигон для опробования алгоритма преобразования. Можно и на других пробовать

30.09.2009, 19:06	#1
motorway Участник клуба Регистрация: 28.06.2009 Сообщений: 1,950	Алгоритм преобразования дорожной сети в граф, для поиска пути Есть карта дорожной сети, на которой показаны улицы. Это файл jpg. Их можно определить по цвету. Точнее, если цвет не серый, то в данном месте проходит улица. Правда, еще нужно учитывать толщину. Как можно преобразовать всю эту сеть в граф, чтобы можно было определить расстояния между 2 точками по улицам, и как найти потом самое короткое расстояние среди всех возможных маршрутов между 2 точками? Планирую это сделать на PHP. Задача в целом в общем алгоритме. Пока нужно понять идею, как это сделать. Есть функции Image Processing and GD. Скрипты PHP, VBA. Skype:ktmtramway Расписание электричек Быстрый проверенный хостинг.

01.10.2009, 15:53	#4
motorway Участник клуба Регистрация: 28.06.2009 Сообщений: 1,950	Конечно, хорошо, но долго ли в ней нужно разбираться, чтобы сделать мою задачу? В общем, может придется обойтись другими методами, или вообще упростить задачу, не строя граф. Например, для получения времени проезда можно обойтись средними расстояниями. Скрипты PHP, VBA. Skype:ktmtramway Расписание электричек Быстрый проверенный хостинг.

01.10.2009, 22:04	#6
motorway Участник клуба Регистрация: 28.06.2009 Сообщений: 1,950	По идее, если все четко делать, он мог бы быть нужен, функционал этот. Но можно зашиться. А все-таки было бы интересно автоматизированно преобразовывать, напр. Яндекс карту Москвы в граф Скрипты PHP, VBA. Skype:ktmtramway Расписание электричек Быстрый проверенный хостинг.

02.10.2009, 18:53	#8
motorway Участник клуба Регистрация: 28.06.2009 Сообщений: 1,950	в данном случае Яндекс карты - просто полигон для опробования алгоритма преобразования. Можно и на других пробовать Скрипты PHP, VBA. Skype:ktmtramway Расписание электричек Быстрый проверенный хостинг.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Задача поиска мнимального пути	delete	Общие вопросы C/C++	2	24.12.2008 20:56
программы для поиска пути в лабиринте. Пролог	loshara_de_kontara	Помощь студентам	2	19.11.2008 21:46
применить Алгоритм Дейкстры для поиска кратчайшего пути в графе	Эдгар	Microsoft Office Excel	13	24.10.2008 21:01
Алгоритм для поиска max Label.Top	Airou	Общие вопросы Delphi	4	28.04.2008 15:13
алгоритмы поиска пути	Iceman	Gamedev - cоздание игр: Unity, OpenGL, DirectX	5	29.10.2007 20:47

01.10.2009, 00:06	#2
SkyM@n Laravel/Vue expert Старожил Подтвердите свой е-майл Регистрация: 08.08.2007 Сообщений: 2,832	Нет, тут надо устанавливать отдельный программный комплекс: mapserver. Очень мощная штука, сам пользуюсь активно. Советую применять его с OpenLayers