Связывание ближайших точек с дорожкой

Question

Учитывая набор упорядоченных точек и путь, составленный из упорядоченных широт, длинных точек, который проходит рядом с этими точками (в координатах широта / долгота), я хочу связать точки с путем, в идеале с хорошей алгоритмической сложностью ( n * log (n)) или лучше, но, возможно, это нереально.

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

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

Итак, это, безусловно, самый математический и необычный вопрос, который я задавал о переполнении стека. Любые идеи будут хороши при решении этой проблемы. Я планирую использовать его для объединения данных формы GTFS с данными поездки, которые описывают время остановки, и встроить их в проект с открытым исходным кодом, Depart App .

Спасибо за вашу помощь!

Answer 1

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

Идея состоит в том, чтобы сначала выбрать первую красную точку в качестве начальной (или можнопервая синяя точка).Затем сравните расстояние от этой точки до следующей красной точки и следующей синей точки, выберите ближе.Повторяйте, пока оба списка не будут исчерпаны.Кажется, это довольно эффективно для набора данных Translink.Я дам обновление, если внесу изменения в эту идею.

Answer 2

Мне кажется, у вас есть два набора точек: широта / долгота и красные точки. Одна из точек широты и долготы - ваша отправная точка. Теперь, рассматривая все остальные точки как набор, используйте (приблизительный?) Алгоритм ближайшего соседа, чтобы найти следующую точку. Теперь повторите. Единственная проблема в том, что алгоритмы ближайшего соседа имеют тенденцию быть O (n), что делает то, что вы хотите сделать, O (n ^ 2).

Answer 3

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

Answer 4

Для каждой красной точки переберите синие сегменты и найдите для нее лучший сегмент. Что именно «лучше», зависит от задачи, но похоже, что хорошей мерой будет «насколько длиннее становится путь». Если A - красная точка, а BC - сегмент, то лучший сегмент минимизирует это: f (A, BC) = (| BA | + | AC | - | BC |).

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

Без оптимизации это даст O (N ^ 2).

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