Маршрутизация карты, а-ля Google Maps?

Во время недавнего опыта написания JS-переводчика я много боролся с внутренней работой дат ECMA / JS. Итак, я полагаю, что я брошу свои 2 цента здесь. Надеемся, что совместное использование этого материала поможет другим с любыми вопросами о различиях между браузерами в том, как они обрабатывают даты.

Сторона входа

Все реализации хранят свои значения даты внутри себя как 64-разрядные номера которые представляют собой миллисекунды с 01.01.1970 UTC (GMT - это то же самое, что и UTC). Даты, возникающие после 1/1/1970 00:00:00, являются положительными числами, а даты предшествуют отрицательным.

Поэтому следующий код дает точный результат во всех браузерах.

Date.parse('1/1/1970');

В моей временной зоне ( EST), результат составляет 18000000, потому что это то, сколько мс составляет 5 часов (это всего 4 часа в летние месяцы). Значение будет отличаться в разных часовых поясах. Все основные браузеры делают это одинаково.

Вот и все. Несмотря на то, что в форматах входных строк есть некоторые отклонения, которые основные браузеры будут анализировать как даты, они по существу интерпретируют их одинаково с часовыми поясами и летней экономией. Один из них - формат ISO 8601. Это единственный формат, специально описанный в спецификации ECMA-262 v.5. Для всех других строковых форматов интерпретация зависит от реализации. По иронии судьбы, это формат, в котором браузеры могут отличаться. Ниже приведен сравнительный вывод Chrome vs Firefox для 1/1/1970 на моей машине с использованием формата строки ISO 8601.

Date.parse('1970-01-01T00:00:00Z');       // Chrome: 0         FF: 0
Date.parse('1970-01-01T00:00:00-0500');   // Chrome: 18000000  FF: 18000000
Date.parse('1970-01-01T00:00:00');        // Chrome: 0         FF: 18000000
  • Спецификатор «Z» указывает, что вход уже находится в UTC и не требует смещения перед хранением.
  • Спецификатор «-0500» указывает, что вход находится в GMT-05: 00, поэтому оба браузера интерпретируют ввод как находящийся в моем локальном часовом поясе. Это означает, что значение будет преобразовано в UTC перед сохранением. В моем случае это означает добавление 18000000 мс к внутреннему значению даты, что требует сдвига -18000000 мс (-05: 00), чтобы вернуть меня в локальное время.
  • Однако, когда спецификатор отсутствует, FF обрабатывает ввод в качестве локального времени, в то время как Chrome рассматривает его как время UTC. Для меня это создает 5-часовую разницу в сохраненной стоимости, что является проблематичным. В моей реализации я оказался на стороне FF здесь, потому что мне нравится вывод toString для соответствия моему входному значению, если я не укажу альтернативный часовой пояс, который я никогда не делаю. Отсутствие спецификатора должно предполагать местный вход времени.

Но здесь ситуация ухудшается, FF обрабатывает краткую форму формата ISO 8601 («YYYY -MM-DD ") по-разному, чем обрабатывает длинную форму (« YYYY-MM-DDTHH: mm: ss: sssZ ») без каких-либо логических причин. Вот результат из FF с длинными и короткими форматами даты ISO без спецификатора часового пояса.

Date.parse('1970-01-01T00:00:00');       // 18000000
Date.parse('1970-01-01');                // 0

Итак, чтобы ответить на вопрос первоначального вопросчика, "YYYY-MM-DD" - это короткая форма ISO 8601 "YYYY-MM-DDTHH:mm:ss:sssZ". Таким образом, это интерпретируется как время UTC, тогда как другое интерпретируется как локальное. Вот почему,

Это не jive:

console.log(new Date(Date.parse("Jul 8, 2005")).toString());
console.log(new Date(Date.parse("2005-07-08")).toString());

Это делает:

console.log(new Date(Date.parse("Jul 8, 2005")).toString());
console.log(new Date(Date.parse("2005-07-08T00:00:00")).toString());

Нижняя строка - это строка синтаксического анализа. Единственная строка ISO 8601, которую вы можете безопасно анализировать в браузерах, - это длинная форма. И ВСЕГДА используйте спецификатор «Z». Если вы это сделаете, вы можете спокойно перемещаться между локальным и UTC.

Это работает в браузерах (после IE9):

console.log(new Date(Date.parse("2005-07-08T00:00:00Z")).toString());

К счастью, большинство современных браузеров другие форматы ввода одинаково, включая наиболее часто используемые форматы «1/1/1970» и «1/1/1970 00:00:00 AM». Все следующие форматы (и другие) рассматриваются как локальный ввод времени во всех браузерах и конвертируются в UTC перед хранением. Таким образом, они совместимы с кросс-браузером. Выходной код этого кода во всех браузерах в моем часовом поясе одинаковый.

console.log(Date.parse("1/1/1970"));
console.log(Date.parse("1/1/1970 12:00:00 AM"));
console.log(Date.parse("Thu Jan 01 1970"));
console.log(Date.parse("Thu Jan 01 1970 00:00:00"));
console.log(Date.parse("Thu Jan 01 1970 00:00:00 GMT-0500"));

Сторона выхода

. На стороне вывода все браузеры переводили часовые пояса одинаково, но они обрабатывать строковые форматы по-разному. Вот функции toString и то, что они выводят. Обратите внимание на то, что функции toUTCString и toISOString выводят на моей машине 5:00 AM.

Конвертирует с UTC в локальное время перед печатью

 - toString
 - toDateString
 - toTimeString
 - toLocaleString
 - toLocaleDateString
 - toLocaleTimeString

Прямая печать сохраненного времени UTC

 - toUTCString
 - toISOString 

In Chrome
toString            Thu Jan 01 1970 00:00:00 GMT-05:00 (Eastern Standard Time)
toDateString        Thu Jan 01 1970
toTimeString        00:00:00 GMT-05:00 (Eastern Standard Time)
toLocaleString      1/1/1970 12:00:00 AM
toLocaleDateString  1/1/1970
toLocaleTimeString  00:00:00 AM

toUTCString         Thu, 01 Jan 1970 05:00:00 GMT
toISOString         1970-01-01T05:00:00.000Z

In Firefox
toString            Thu Jan 01 1970 00:00:00 GMT-05:00 (Eastern Standard Time)
toDateString        Thu Jan 01 1970
toTimeString        00:00:00 GMT-0500 (Eastern Standard Time)
toLocaleString      Thursday, January 01, 1970 12:00:00 AM
toLocaleDateString  Thursday, January 01, 1970
toLocaleTimeString  12:00:00 AM

toUTCString         Thu, 01 Jan 1970 05:00:00 GMT
toISOString         1970-01-01T05:00:00.000Z

Я обычно не используйте формат ISO для ввода строки. Единственный раз, когда использование этого формата полезно для меня, - это когда даты нужно сортировать как строки. Формат ISO можно сортировать как есть, а другие - нет. Если у вас есть совместимость с несколькими браузерами, укажите либо часовой пояс, либо используйте совместимый строковый формат.

Код new Date('12/4/2013').toString() проходит через следующее внутреннее псевдопреобразование:

  "12/4/2013" -> toUCT -> [storage] -> toLocal -> print "12/4/2013"

Надеюсь, этот ответ был полезен.

20
задан Vikash Pandey 12 May 2016 в 05:57
поделиться

7 ответов

Смотрите на открытый проект карты города видеть, как этим видом вещи занимаются в истинно использовании проекта бесплатного программного обеспечения только пользователя снабженные и лицензируемые данные, и имейте Wiki, содержащая материал, который Вы могли бы найти интересным .

Несколько лет поддерживают парней, вовлеченных, где довольно спокойный и ответил на большое количество вопросов, я имел так, я не вижу оснований, почему они все еще не хороший набор.

14
ответ дан 30 November 2019 в 00:19
поделиться

Barry Brumitt, один из инженеров функции нахождения маршрута карт Google, записал сообщение по теме, которая может представлять интерес: The road,

, к лучшему, новаторскому 06.11.2007 15:47:00

4
ответ дан 30 November 2019 в 00:19
поделиться

* на самом деле намного ближе к производственным алгоритмам отображения. Требуется вполне немного меньше исследования по сравнению с исходным алгоритмом Dijikstra.

4
ответ дан 30 November 2019 в 00:19
поделиться

Маршрутизацией Карты Вы означаете находить кратчайший путь вдоль уличной сети?

алгоритм поиска кратчайшего пути Dijkstra является самым известным. Википедия не имеет плохого введения: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

существует апплет Java здесь, где Вы видите его в действии: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html и Google Вы приводите Вас к исходному коду на примерно любом языке.

Любая реальная реализация для того, чтобы построить ведущие маршруты будет включать довольно мало данных по уличной сети, которая описывает партнера затрат пересечения ссылок и nodes— иерархия дорожной сети, средняя скорость, перекрестный приоритет, транспортное соединение сигнала, запретил повороты и т.д.

4
ответ дан 30 November 2019 в 00:19
поделиться

Вместо того, чтобы изучить API каждому поставщику картографического сервиса (как Gmaps, API Ymaps) Его польза для изучения Mapstraction

"Mapstraction является библиотекой, которая обеспечивает общий API для различного JavaScript, отображающего API",

я предложил бы, чтобы Вы перешли к URL и изучили общий API. Существует хорошая сумма Практических руководств также.

2
ответ дан 30 November 2019 в 00:19
поделиться

Я должен все же найти хорошее учебное руководство при маршрутизации, но существует много кода для чтения:

существуют приложения маршрутизации GPL, которые используют данные Openstreetmap, например, Gosmore, который работает над Windows (+ мобильный) и Linux. Существуют много интересные [приложения с помощью тех же данных, но gosmore имеет некоторое прохладное использование , например, интерфейс с веб-сайтами .

самой большой проблемой с маршрутизацией являются неправильные данные, и Вы никогда не получаете достаточно хорошие данные. Таким образом, если Вы хотите попробовать его, сохраняют Ваш тест очень локальным, таким образом, можно управлять данными лучше.

2
ответ дан 30 November 2019 в 00:19
поделиться

С концептуальной точки зрения предположите бросать камень в водоем и наблюдать пульсации. Маршруты представили бы водоем и камень Ваша стартовая позиция.

, Конечно, алгоритм должен был бы искать некоторую пропорцию путей n^2 как расстояние n увеличения. Вы взяли бы Вас стартовая позиция и проверили бы все доступные пути от той точки. Затем рекурсивно призовите к точкам в конце тех путей и так далее.

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

альтернативный путь состоит в том, чтобы использовать подход феромона муравья, где муравьи проверяют случайным образом от стартовой точки и оставляют след аромата, который растет, больше муравьев пересекает данный путь. При отправке (достаточно) муравьев и от стартовой точки и от конечных точек затем в конечном счете, путь с самым сильным ароматом будет кратчайшим. Это вызвано тем, что кратчайший путь посетят больше раз в данный период времени, учитывая, что муравьи идут в универсальном темпе.

РЕДАКТИРОВАНИЕ Spikie

Как дальнейшее объяснение того, как реализовать алгоритм водоема - потенциальные необходимые структуры данных выделяются:

необходимо будет сохранить карту как сеть. Это - просто ряд nodes и edges между ними. Ряд nodes составляет route. Край присоединяется к двум узлам (возможно оба тот же узел) и имеет связанное cost такой как distance или time для пересечения края. Край может или или быть двунаправлен или однонаправлен. Вероятно, самый простой просто иметь однонаправленные и согнуть для двух путей перемещение между узлами (т.е. один край от до B и другого для B к A).

, Как пример, воображают три железнодорожных станции расположенными в равностороннем треугольнике, указывающем вверх. Существуют также еще три станции каждый на полпути между ними. Края присоединяются ко всем смежным станциям вместе, заключительная схема будет иметь инвертированный треугольник, находящийся в большем треугольнике.

узлы Маркировки, начинающие с левой нижней части, идя слева направо и, как A, B, C, D, E, F (F наверху).

Предполагают, что края могут быть пересечены в любом направлении. Каждый край имеет стоимость 1 км.

хорошо, таким образом, мы хотим направить от левой нижней части к главной станции F. Существует много возможных маршрутов, включая тех, которые загибают на себе, например, ABCEBDEF.

у Нас есть стандартная программа, говорят, NextNode, который принимает node и cost и называет себя для каждого узла, в который она может переместиться.

Очевидно, если мы позволяем этой стандартной программе работать, она в конечном счете обнаружит все маршруты, включая, которые потенциально бесконечны в длине (например, ABABABAB и т.д.). Мы мешаем этому произойти путем проверки по cost. Каждый раз, когда мы посещаем узел, который не посетили прежде, мы помещаем и стоимость и узел, из которого мы произошли против того узла. Если узел посетили, прежде чем мы проверим по существующей стоимости и если мы являемся более дешевыми затем, мы обновляем узел и продолжаем (рекурсивно вызывать). Если мы являемся более дорогими, то мы пропускаем узел. Если все узлы пропускаются затем, мы выходим из стандартной программы.

, Если мы поражаем наш целевой узел затем, мы выходим из стандартной программы также.

Этот способ, которым все жизнеспособные маршруты проверяются, но кардинально только те, которые имеют самую низкую цену. К концу процесса каждый узел будет иметь самую низкую цену для получения к тому узлу, включая наш целевой узел.

Для получения маршрута мы работаем назад от нашего целевого узла. Так как мы сохранили узел, из которого мы произошли наряду со стоимостью, мы просто скачкообразно перемещаем назад создание маршрута. Для нашего примера мы закончили бы с чем-то как:

Узел - (Общая) Стоимость 0 - От Узла Ни один
Узел B - Стоимость 1 - От Узла
Узел C - Стоимость 2 - От узла B
Узла D - Стоимость 1 - От Узла
Узел E - Стоимость 2 - От Узла D / Стоимость 2 - От Узла B (это - исключение как, существует равная стоимость)
Узел F - Стоимость 2 - От узла D

, Таким образом, кратким маршрутом является ADF.

2
ответ дан 30 November 2019 в 00:19
поделиться
Другие вопросы по тегам:

Похожие вопросы: