Разное

Хотелось бы обсудить такой вопрос. (расширение этой темы: http://www.softtime.ru/forum/read.php?id_forum=2&id_theme=58646)

Есть карта города, допустим гугл. Есть задача - научиться прокладывать маршрут в пределах города из точки А до точки Б.

Допущения такие: передвигаться можно только по улицам, поворачивать можно только на перекрёстках.

Вопрос: что нужно занести в базу, чтобы прокладывать такие маршруты?

Сразу понятно, что надо как-то обозначать перекрёстки. Допустим что мы занесли в базу все перекрёстки города в виде (n,m,coordinates) где n и m - id пересекающихся улиц coordinates - географические координаты перекрёстка. Что ещё надо добавить в данные или этого достаточно?

На основании географических координат можно рассчитывать расстояние между перекрёстками. А на основании точек пересечения можно (наверное) найти все доступные перекрёстки между точкой (a,b) и (x,y) где a,b,x,y - id соответствующих улиц.

Как вообще решаются подобные задачи?

Возможно, вам пригодится теория графов и алгоритм Дейкстры.

Угу, пригодится, это я в курсе. Но там вычисление расстояний на готовом графе, а его ещё надо построить. В этом и проблема пока.