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


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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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


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