Геопространственная маршрутизация

Question

Я программист по логистике, и меня попросили выяснить, находится ли точка GPS вне маршрута, где маршрут состоит из нескольких геопространственных точек (широта, долгота).

Каков наилучший алгоритм для определения, находится ли точка рядом с маршрутом? Я буду использовать C # и SQL Server, но на самом деле это не имеет большого значения, если я знаю, какой алгоритм использовать.

Я рассмотрел

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

У меня нет степени по математике, но я, вероятно, могу справиться со всем, учитывая правильные термины и поисковую систему.

Мне придется делать не менее 4000 вычислений в час, поэтому использование картографического решения, вероятно, неприемлемо из-за объема.

Answer 1

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

На самом деле, это ИДЕАЛЬНЫЙ пример, в котором было бы полезно картографическое решение. Не ваш традиционный "взгляд на карту и определение расстояния", а скорее "позволить базе данных определить, какой маршрут ближе всего к вашей точке GPS.

Поскольку вы говорите, что не против использования другой базы данных, вы можете подумать:

1. SQL Server 2008, который имеет Spatial Database Engine функции или
2. PostgreSQL с открытым исходным кодом PostGIS (пространственное) расширение, которое имеет значительно больше функций пространственного анализа, чем MS SQL 2008.

Посмотрите на функцию PostGIS ST_Distance или MS SQL Server 2008 STDistance . Это хорошая запись в блоге , которая описывает преимущества SQL2005 по сравнению с SQL2008.

Вы также можете прочитать (или попросить более подробное сопоставление) посты на gis.stackexchange . Вся эта группа посвящена пространственному анализу. Некоторые хорошие обсуждения, на которые вы могли бы взглянуть, были бы

• Найти ближайший лат длинный к входному лат длинный (SQL Server 2008)
• PostGIS: ближайшая точка на линейной линии к данной точке

Answer 2

Google для "Along-track distance", и вы должны найти формулы, обычно используемые в авиации. В качестве альтернативы, cross-track distance также может быть тем, что вы хотите.

Answer 3

Как насчет следующего ...

Итерация по всем отрезкам линии

lineSegSlope = Вычислить наклон для каждого отрезка линии

Нарисуйте притворную линию из рассматриваемой точкикоторый пересекает текущий сегмент линии.это делается путем инвертирования lineSegSlope и умножения на -1, чтобы получить новый наклон, а затем подставить целевую точку X, Y и новый наклон в y-y1 = b * (x-x1).Ваш X переходит в x1, ваш Y переходит в Y1, а ваш newSlope переходит в B.

составляет уравнение для отрезка.

, если вы рисуете две линии друг над другом, они должны сделать X, где каждый угол равен 90 градусам.

вычислить пересечение двух линий

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

это выглядит как беспорядок, но, надеюсь, это должно сработать.

Answer 4

Наивным подходом было бы вставить новую точку GPS в различных местах вдоль маршрута. Начните с его вставки перед первой точкой P0, затем между первой и второй точками P0 и P1 и т. Д., Пока вы не попытаетесь вставить его в качестве последней точки. Каждый раз, когда вы пытаетесь вставить его в определенное место, вычисляйте общее расстояние для цепи и сохраняйте, сохраняя самое короткое общее расстояние. Это можно ускорить, предварительно вычислив расстояния между ногами и сохранив эту сумму. Проверьте расстояние, вычитая расстояние между ногами для ноги, в которую вы вставляете новую точку, и добавляя новое расстояние от точки P (n) до точки GPS в P (n + 1). Если это самое короткое общее расстояние находится в пределах допустимого уровня, вы можете принять его.

Вероятно, это не "лучший" алгоритм (в зависимости от вашего определения наилучшего), но это O (n) от количества точек в вашем маршруте для сложности времени и пространства. Поэтому, если у вас на маршруте не будет огромное количество точек, каждая проверка должна быть чуть меньше секунды, так что это должно соответствовать вашим требованиям времени.

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

Answer 5

Можете ли вы взять существующий маршрут в виде последовательности отрезков линии в 2-D, а затем взять точку запроса и найти ближайшую точку и ближайший отрезок линии? Расстояние до ближайшего отрезка / отрезка будет равно расстоянию, о котором вы заботитесь.

Если вы придерживаетесь относительно низких широт (ниже 60 градусов), вы можете рассматривать широту и долготу, как если бы они были просто плоскими, как на проекции Меркатора.

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

Если вы не имеете дело с миллионами точек маршрута, у вас не должно быть проблем с процессорным временем.