Гость
Форумы / Разработка информационных систем [игнор отключен] [закрыт для гостей] / Расстояния между городами / 23 сообщений из 23, страница 1 из 1
12.08.2006, 18:34
    #33914694
apstar
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
Есть задача!
Написать сервис который бы расчитывал расстояния между городами введеных (или выбранные из списка) пользователем. Может кто подскажет с чего начать.
Я то выкрутился из положения (отсылаю пост запрос на другой сайт и получаю ответ, его обрабатываю и вывожу на екран), но ведь это до поры до времени! и расчет не мой!
...
Рейтинг: 0 / 0
12.08.2006, 18:57
    #33914704
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
Начать стоит с толкового ТЗ. После этого подключить географический справочник и посмотреть в учебнике сферической геометрии формулу расстояния по поверхности шара (хотя в общем-то ее и так легко вывести).
...
Рейтинг: 0 / 0
13.08.2006, 18:24
    #33915052
Расстояния между городами
Земля - не сфера, земля - геоид.


Поищите формулу для вычисления ортродромического расстояния
...
Рейтинг: 0 / 0
14.08.2006, 07:59
    #33915336
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
ШтурманчегЗемля - не сфера,
Для практических задач сайта такого приближения более чем достаточно.

Штурманчегземля - геоид.
А масло - масляное.

ШтурманчегПоищите формулу для вычисления ортродромического расстояния
Тут Вы правы. Причем что характерно, это и будет та формула, о которой я говорил. Иначе ее называют "длина дуги большого круга".
...
Рейтинг: 0 / 0
14.08.2006, 09:30
    #33915456
Calm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
По-моему это классическая задача нахождения минимального пути на графе.
Вершины - города, ребра - дороги.

Расстояние между Российскими городами можешь легко получить из атласа автодорог.
...
Рейтинг: 0 / 0
14.08.2006, 09:32
    #33915462
Calm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
авторПосле этого подключить географический справочник и посмотреть в учебнике сферической геометрии формулу расстояния по поверхности шара

Вспоминается анекдот про консультанта и пастуха
Softwarer, зачем же так усложнять? :)
...
Рейтинг: 0 / 0
14.08.2006, 10:20
    #33915556
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
CalmПо-моему это классическая задача нахождения минимального пути на графе. Вершины - города, ребра - дороги.
И каково расстояние от Багдада до Мехико?

Расстояние между Российскими городами можешь легко получить из атласа автодорог.[/quot]

CalmВспоминается анекдот про консультанта и пастуха
Воистину.

CalmSoftwarer, зачем же так усложнять? :)
Это, собственно, к Вам вопрос - вместо единственной простой формулы, записываемой в одну строку, Вы предлагаете реализовать классический алгоритм, нормальная по скорости реализация которого для веба весьма и весьма нетривиальна.
...
Рейтинг: 0 / 0
14.08.2006, 11:09
    #33915726
ChMt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
softwarer ШтурманчегЗемля - не сфера,
Для практических задач сайта такого приближения более чем достаточно.

практические задачи Вашего сайта могут сильно отличаться от задач сайта автора топика :)
к сожалению о них ничего не сказано и, в зависимости от задач, решение может сильно варьироваться. вряд ли автомобилисты путешествуют по ортодромии и дороги не всегда по локсодромии проложены :)
...
Рейтинг: 0 / 0
14.08.2006, 12:03
    #33915946
прохожу.
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
типичная задача "комивояжера"(надеюсь правильно написал), полно книг уже написано.
...
Рейтинг: 0 / 0
14.08.2006, 12:37
    #33916087
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
ChMtпрактические задачи Вашего сайта могут сильно отличаться от задач сайта автора топика :)
Безусловно. Однако для меня очевидно, что сайт автора не является главным расчетным центром Аэрофлота :)

ChMtк сожалению о них ничего не сказано и, в зависимости от задач, решение может сильно варьироваться.
Поэтому, если обратите внимание, первым пунктом моего ответа стоит толковое ТЗ.
...
Рейтинг: 0 / 0
14.08.2006, 12:39
    #33916097
Calm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
Согласен, что если интересует расстояние исключительно в географическом смысле, то проще вычислять по формуле, без всяких графов.

авторВы предлагаете реализовать классический алгоритм, нормальная по скорости реализация которого для веба весьма и весьма нетривиальна.
Грубо, 95% запросов будет касаться 5% городов.
Небольшой кэш из, скажем 2-3 тыс. записей (расстояний между городами) снизит количество "полновесных" расчетов до приемлемой величины. Даже если кэш будет 10 тыч записей, то даже бесплатный хостинг не упадет.
...
Рейтинг: 0 / 0
14.08.2006, 13:30
    #33916311
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
имхо, пока автор темы не раскроет его понимаение термина "расстояние", обсуждать способы решения бессмысленно.
вдуг его пространственное расстояние (по прямой) интересует...
...
Рейтинг: 0 / 0
14.08.2006, 15:06
    #33916725
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
CalmНебольшой кэш из, скажем 2-3 тыс. записей
Если Вы имеете в виду кэш на программном уровне, то насколько я понимаю, для веба он уже не так-то прост в реализации (почему на php, perl итп постоянно носятся с дурацкой идеей постоянных реконнектов).

А так - если говорить о Вашем подходе, я бы вообще загнал в БД таблицу предрассчитанных расстояний, и "кэш" оказался бы ограничен только выделенным местом. Собственно, и рассчитывать новые расстояния по-хорошему тоже надо в БД, но есть подозрение, что в реальности так не получится.
...
Рейтинг: 0 / 0
14.08.2006, 16:16
    #33916947
RasimS
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
apstarЕсть задача!
Написать сервис который бы расчитывал расстояния между городами введеных (или выбранные из списка) пользователем. Может кто подскажет с чего начать.
Я то выкрутился из положения (отсылаю пост запрос на другой сайт и получаю ответ, его обрабатываю и вывожу на екран), но ведь это до поры до времени! и расчет не мой!
А что если граф использовать?
...
Рейтинг: 0 / 0
14.08.2006, 17:14
    #33917143
Calm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
автортак - если говорить о Вашем подходе, я бы вообще загнал в БД таблицу предрассчитанных расстояний

Вполне может что так и будет быстрее всего.


авторимхо, пока автор темы не раскроет его понимаение термина "расстояние"
Автор, подогрей тему!
...
Рейтинг: 0 / 0
01.09.2006, 16:02
    #33959084
pan159
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
В старой книге Мартин "Системный анализ передачи данных" есть решение этой задачи. Похоже на схему ПЕРТ или динамическое программирование. Начиная с конечного пункта (вершины графа) пишете на ребрах расстояние от конечного пункта до промежуточной вершины. Сначала смежные вершины. Потом смежные смежных и т.п. Если есть два или более варианта расстояний, то выбирается наименьшее. Оно приписывается промежуточной вершине.
...
Рейтинг: 0 / 0
01.09.2006, 16:39
    #33959275
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
pan159В старой книге Мартин "Системный анализ передачи данных" есть решение этой задачи.
Это называется "алгоритм Дейкстры" .

По этому поводу: http://www.sql.ru/forum/actualthread.aspx?tid=325732#2998126
...
Рейтинг: 0 / 0
01.09.2006, 20:01
    #33959770
apstar
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
Большое спасибо всем!
Я решил с помощь решения задачи комивояжера!
Вот только осталось одно! База данных! Где бы взять базу включающую хотя бы стнаны СНГ с растояниями между городами по автомобильным дорогам, в каком нибудь виде!
...
Рейтинг: 0 / 0
01.09.2006, 20:05
    #33959775
apstar
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
CalmСогласен, что если интересует расстояние исключительно в географическом смысле, то проще вычислять по формуле, без всяких графов.

авторВы предлагаете реализовать классический алгоритм, нормальная по скорости реализация которого для веба весьма и весьма нетривиальна.
Грубо, 95% запросов будет касаться 5% городов.
Небольшой кэш из, скажем 2-3 тыс. записей (расстояний между городами) снизит количество "полновесных" расчетов до приемлемой величины. Даже если кэш будет 10 тыч записей, то даже бесплатный хостинг не упадет.

По статистике на сайте 85% запросов касаются 5% городов (уже проверил), так что идея повышает быстродействие!
...
Рейтинг: 0 / 0
09.09.2006, 00:57
    #33975582
Lepsik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
apstarБольшое спасибо всем!
Я решил с помощь решения задачи комивояжера!
Вот только осталось одно! База данных! Где бы взять базу включающую хотя бы стнаны СНГ с растояниями между городами по автомобильным дорогам, в каком нибудь виде!

у яху есть бесплатный сервис по запросу возвращает точное расстояние.

Если ручками - то алгоритм Красовского он рассчитан на полет СС-18 от Красноярска до Нью-Йорка с точность около 10 метров
...
Рейтинг: 0 / 0
12.09.2006, 17:36
    #33981862
nik_x
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
Lepsik apstarБольшое спасибо всем!
Я решил с помощь решения задачи комивояжера!
Вот только осталось одно! База данных! Где бы взять базу включающую хотя бы стнаны СНГ с растояниями между городами по автомобильным дорогам, в каком нибудь виде!

у яху есть бесплатный сервис по запросу возвращает точное расстояние.

Если ручками - то алгоритм Красовского он рассчитан на полет СС-18 от Красноярска до Нью-Йорка с точность около 10 метров

На высоте XX метров по осевой линии дорог?
Ну-ка, ну-ка поделись алгоритмом с нами, темными... (не жлобствуй)
...
Рейтинг: 0 / 0
12.09.2006, 18:15
    #33982011
shuklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Расстояния между городами
apstarНаписать сервис который бы расчитывал расстояния между городами введеных (или выбранные из списка) пользователем.

адаптировано из http://www.esanu.name/delphi/Algorithms/Maths/Calculate%20Distance%20using%20Latitudes%20and%20Longitudes.html

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
SET QUOTED_IDENTIFIER OFF 
GO
SET ANSI_NULLS OFF 
GO


ALTER   FUNCTION dbo.distance2
	(
		  @StartLatitude float -- Start Latitude
		, @StartLongitude float -- Start Longitude
		, @FinalLatitude float -- Final Latitude
		, @FinalLongitude float -- Final Longitude
	)
RETURNS @tbl TABLE (Distance float, Bearing float)
AS
	BEGIN
DECLARE
	  @fPhimean float -- Mean Latitude
	, @fdLambda float -- Difference between longtitudes
	, @fdPhi float -- Difference between lantitudes
	, @fAlpha float -- Drift
	, @fRho float -- Meridian radius of curvature. 
	, @fNu float -- Cross-section radius of curvature
	, @fR float -- Earth radius
	, @fz float -- Angular distance from the center of a spheroid
	, @fTemp float -- The temporal variable used in calculations
	, @Distance float -- Distance in meters
	, @Bearing float -- Bearing
	, @R2D float --  constant for transformation a radian in degrees
	, @a float -- The basic halfaxes
	, @b float -- Nonbasic halfaxes
	, @e2 float -- A square of ellipsoid eccentricity
	, @f float -- Alignment of ellipsoid


	SET @R2D =  57 . 295781 
	SET @a =  6378137 . 0 
	SET @b =  6356752 . 314245 
	SET @e2 =  0 . 006739496742337 
	SET @f =  0 . 003352810664747 


	-- We calculate a difference between two longitudes and breadthes and it is received average breadth 
	SET @fdLambda = radians(@StartLongitude - @FinalLongitude);
	SET @fdPhi = radians(@StartLatitude - @FinalLatitude);
	SET @fPhimean = radians((@StartLatitude + @FinalLatitude) /  2 . 0 );

	-- We calculate meridian and cross-section radiuses of curvature of average breadth 
	SET @fTemp =  1  - @e2 * (Power(Sin(@fPhimean),  2 ));
	SET @fRho = (@a * ( 1  - @e2)) / Power(@fTemp,  1 . 5 );
	SET @fNu = @a / (Sqrt( 1  - @e2 * (Sin(@fPhimean) * Sin(@fPhimean))));

	-- We calculate angular distance 
	SET @fz =
		Sqrt(Power(Sin(@fdPhi /  2 . 0 ),  2 ) + Cos(radians(@FinalLatitude)) * Cos(radians(@StartLatitude)) *
		Power(Sin(@fdLambda /  2 . 0 ),  2 ));

	SET @fz =  2  * ASin(@fz);

	-- We calculate displacement 
	SET @fAlpha = Cos(radians(@FinalLatitude)) * Sin(@fdLambda) *  1  / Sin(@fz);
	SET @fAlpha = ASin(@fAlpha);

	-- We calculate radius of the Earth 
	SET @fR = (@fRho * @fNu) / ((@fRho * Power(Sin(@fAlpha),  2 )) + (@fNu *
		Power(Cos(@fAlpha),  2 )));

	-- Calculating displacement and distance 
	SET @Distance = (@fz * @fR);
	if ((@StartLatitude < @FinalLatitude) and (@StartLongitude < @FinalLongitude))
		SET @Bearing = Abs(@fAlpha * @R2D)
	else if ((@StartLatitude < @FinalLatitude) and (@StartLongitude > @FinalLongitude))
		SET @Bearing =  360  - Abs(@fAlpha * @R2D)
	else if ((@StartLatitude > @FinalLatitude) and (@StartLongitude > @FinalLongitude))
		SET @Bearing =  180  + Abs(@fAlpha * @R2D)
	else if ((@StartLatitude > @FinalLatitude) and (@StartLongitude < @FinalLongitude))
		SET @Bearing =  180  - Abs(@fAlpha * @R2D);

		INSERT INTO @tbl (Distance, Bearing)
		SELECT @Distance, @Bearing
	RETURN
	END


GO
SET QUOTED_IDENTIFIER OFF 
GO
SET ANSI_NULLS ON 
GO


...
Рейтинг: 0 / 0
26.09.2006, 21:48
    #34014010
Расстояния между городами
По роду деятельности совершаю поездки с Севера на автомобиле практически во все концы РФ. Для интереса пытался пользоваться таблицами расстояний из интернета, но они все на 50 - 250 км, в зависимости от расстояний занижены. Греша на спидометр одно время сличал их с придорожными указателями расстояний между населенными пунктами - никакого соответствия. Наверное они составлялись авиаторами, а не автомобилистами.
...
Рейтинг: 0 / 0
Форумы / Разработка информационных систем [игнор отключен] [закрыт для гостей] / Расстояния между городами / 23 сообщений из 23, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]