Поиск кратчайшего пути

[Asphyxis]

Добрый день.

Получил задачу: создание утилиты для mapinfo, написать утилиту поиска кратчайшего маршрута на mapbasic.
Маршрут должен быть "привязан" к существующим дорогам (отрисованы линиями).

Подскажите пожалуйста как это реализовать? или что почитать?

Спасибо.

[Boris]

Если вы знаете самим используемым продуктам, то в Гугле наберите "алгоритм поиска кратчайшего пути на Basic" или "Алгоритм Дейкстры".
Во всем мире это нехилая коммерческая задача. Требующая и неплохих компьютерных ресурсов. Задачи оптимизации разреженных графов, то же требуют не слабой изворотливости. А так же кропотливого создания и актуализации исходных данных - ребер в правильном порядке, а не "как отрисовалось, так и хорошо", обязательных вершин в местах ветвления дорог и т.п.

[bim2010]

http://www.directionsmag.com/files/index.php/view/661
Про литературу здесь:
viewtopic.php?f=2&t=4193&p=18432#p18432

[Asphyxis]

http://www.directionsmag.com/files/index.php/view/661
Про литературу здесь:
viewtopic.php?f=2&t=4193&p=18432#p18432

спасибо! очень полезные ссылки

а существуют ли в природе исходники этого Route_Walker?
обидно что утилита скомпилирована

[bim2010]

http://www.routeware.dk/download/routef ... apinfo.pdf

http://www.analygis.com/pdfs_apps/great ... routes.zip
MapBasic утилита рассчитывает кратчайшее расстояние между двумя точками на сферической поверхности.

[bim2010]

Масса ссылок
http://masters.donntu.edu.ua/2006/ggeo/ ... /index.htm

Ряд решений
http://www.digimap.com/pdf/ChronoVia%20 ... ochure.pdf
http://www.theexmiles.com/routeoptimiza ... fopro.html
http://www.routeware.dk/download.php
http://www.ifp.uni-stuttgart.de/lehre/s ... eutle.html
http://www.paper.edu.cn/en/paper.php?se ... 200806-590

Масса решений на других языках (см предыдущие ссылки)
http://www.gis-mapinfo.cn/post/22093.html
Может пора уже перевести на Mapbasic и выложить?
Вот частично:
http://ciren.vn/forums/archive/index.php/t-816.html
http://www.gisdevelopment.net/applicati ... yt0003.htm

Нужно больше информации по задаче:
1. Обязательно ли это делать на MB и MI?
2. Данные в какой проекции (географическая / не географическая)?
3. Реализация транспортного графа, слоя домов. Проще выложить кусок Ваших данных. чтоб не гадать ...
4. Задача учебная (диплом/курсяк) или real ? Какие еще условия и ограничения Вы собираетесь учитывать?

[Asphyxis]

За ссылки спасибо)

1. да
2. географическая
3. слой домов задан точками (в таблице название и координата широты и долготы), дороги отдельным слоем (заданы полилиниями)
4. задача реальная, сначала надо реализовать простейший случай без всяких ограничений (ну естественно, что путь должен быть привязан к дорогам), остальное я думаю дело техники...

[Asphyxis]

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

почему то в массив заносится лишь координаты одной точки для каждой полилинии...
надо как-то все узлы считать для каждой полилинии...

Код: Выделить всё

For j1=1 To ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS)
	For i1=1 To ObjectInfo (road.obj, OBJ_INFO_NPOLYGONS+j1)
		node_pol(j1).x1=ObjectNodeX(road.obj, j1, i1)
		node_pol(j1).y1=ObjectNodeY(road.obj, j1, i1)
	 cur_size = UBound(node_pol)
             ReDim node_pol(cur_size + 1) 
	Next
Next

подскажите что в коде поправить?

[Boris]

ReDim node_pol(cur_size + 1)

зачем столько раз память перераспределять? нельзя заранее посчитать размерность?
здесь и ошибка - нарастающий индекс пишется в номер сегмента полигона.

[Asphyxis]

ReDim node_pol(cur_size + 1)

зачем столько раз память перераспределять? нельзя заранее посчитать размерность?
здесь и ошибка - нарастающий индекс пишется в номер сегмента полигона.

в том и дело что нельзя...
но ведь код вида (при заданной размерности):

Код: Выделить всё

For j1=1 To ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS)
   For i1=1 To ObjectInfo (road.obj, OBJ_INFO_NPOLYGONS+j1)
      node_pol(j1).x1=ObjectNodeX(road.obj, j1, i1)
      node_pol(j1).y1=ObjectNodeY(road.obj, j1, i1)
   Next
Next

выдаёт такой же массив, как в предыдущей реализации... т.е. по всем узлам не пробегает...
или я недопонял )

поправьте пожалуйста в коде, если я не прав

[Boris]

Код: Выделить всё

dim arr_Size as Integer,N as Integer,M as Integer

arr_Size=0
N=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS)

For j1=1 To N
  M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1)
   For i1=1 To M
      arr_Size = arr_Size + 1
   Next
Next
ReDim node_pol(arr_Size)  '' память перераспределяется только 1 раз

cur_size = 0 '' массивы в MapBasic'е начинаются только с 1-цы
For j1=1 To N
   M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1)
   For i1=1 To M
      cur_size = cur_size + 1 '' массивы в MapBasic'е начинаются только с 1-цы
      node_pol(cur_size).x1=ObjectNodeX(road.obj, j1, i1)
      node_pol(cur_size).y1=ObjectNodeY(road.obj, j1, i1)
   Next
Next

[Asphyxis]

ругается на ObjectNodeX(road.obj, j1, i1) , пишет, что аргумент 3 вышел за заданные пределы...

[reasonat]

M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1) - в обоих случаях

[Boris]

M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1) - в обоих случаях

Спасибо. Код - поправил.