дано карта города на чертежном формате ( рисунка .jpg) , надо найти наикратчайший путь по дороги от точки А до В . Программу надо написать на Visual basic, но если кто то сможет написать на другие языки, я не против, буду очень благодарен....
Ну и задачку Вам задали.
Хотите посоревноваться с ведущими мировыми фирмами занимающимися электронной картографией ???
Что бы решить Вашу задачу, карта населенного пункта должна быть выполнена в векторной графике, а не в растровом JPG.
В векторной карте дорога - это набор линий (векторов) . И найти кратчайший путь от А до Б просто (почти просто... )
Координаты и длина каждого вектора известна. Достаточно сделать перебор и учесть масштаб.
А JPG картинка - это набор пикселей разного цвета. И все.. .
Для этого и веторизируют растровые изображения http://ru.wikipedia.org/wiki/Векторизация_(графика)
>> Ну можно перенарисовать дорогу, чтоб цвет дороги отличился от других цветов карты.
Ага.. .Это же JPG !!!Просто так не возьмешь в Paint и не зальешь всю дорогу от сих, и до границ.
Попробуйте. Там же не один белый цвет, а целая куча оттенков белого.
Проще заново всю карту нарисовать.. .
Если Вы все же решите пойти по сложному пути и раскрасить дороги карты другим цветом,
то алгоритм может быть такой:
Представим карту в виде координатной сетки.
Создадим двухмерный массив согласно количества ячеек сетки.
Просканируем каждую "ячейку" картинки с координатами от ...и до.. .на наличие красного цвета (дорога)
Если в ячейке есть дорога (красный цвет) , то в массив занесем "1", иначе "0".
В итоге, получим массив примерно такого типа:
Остается посчитать наименьшее количество "единичек" от А до Б.. .
Естественно, чем больше размерность массива, тем выше будет точность расчета.
и что, в задании сказано чтобы программа брала jpg файл и сама понимала где там улица, а где там дерево?
я более чем уверен что тебе вручную надо описать карту как кучу соединённых узлов.... говоря иначе, это будет граф
и потом уже сочинять программу обхода графа.
или покрой карту города сеткой и если клетка попадает на дорогу, то это пусто, а если занято чем-то.. . занято.
и используя метод.... хм, скажем для примера, волновой метод, находишь кратчайший путь...
⇢