Извлечение топологии из дорожной сети (.NET)

Question

У нас есть несколько высококачественных дорожных сетей, доступных из нескольких источников (Open Street Map, TomTom ...). Эти источники содержат больше информации, чем нам нужно, эффективно блокируя наши вычисления. Отфильтровывать второстепенные дороги легко. Наши основные проблемы - это представление автомобильных дорог (две дороги в противоположных направлениях), сложные переходы на шоссе (различные выездные пути, переходы не являются точками). Для наших целей идеальной была бы более «топологическая» дорожная сеть.

Очень подробный источник данных:

Идеальная упрощена сеть:

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

ОБНОВЛЕНИЕ:

Исходные данные представлены в виде ломаных линий с некоторыми ограниченными метаданными, прикрепленными. В метаданных указывается идентификация дороги (имя или номер), «ранг» дороги (шоссе, первичный, вторичный и т. Д.), А также некоторые детали, такие как ограничение скорости, будь то участок линии - мост или туннель. Качество данных очень хорошее, мы можем легко объединить сегменты полилинии, которые вместе образуют дорогу, основанную на идентификации дороги. Аналогичным образом, очень легко игнорировать второстепенные дороги. Ускоренные/замедляющие полосы на выезде с шоссе также четко обозначены в их ранге, поэтому они также легко фильтруются.

Мы видим две основных проблем:

1) Автомобильные дороги: Заменить два (или более) OneWay дороги с одной дорогой

2) шоссе перекрестков: Определить центральную точку стыков, и сделать что наши упрощенные автодороги связаны с этим.

ОБНОВЛЕНИЕ 2: Данные хранятся в EZRI Shape files. Используя SharpMap library, их относительно легко разобрать или выполнить геопространственный поиск. Исходные данные сегментируются по странам, одна страна - один файл формы (если страна слишком велика, как США, Германия), она далее делится на более мелкие регионы. И да, это разделение вызывает дополнительную проблему. Как убедиться, что упрощенные автодороги на границе Франции и Германии встречаются друг с другом?

Thanx за внимание

Answer 1

Это только эскиз решения, но:

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

• Теперь выберите алгоритм кластеризации и попросите его сгруппировать дороги в зависимости от расстояния, которое вы только что определили. Будьте очень щедры с количеством кластеров, которые вы позволили ему использовать.Когда он вернется, найдите кластеры с очень низким «диаметром», что означает, что каждая точка в кластере очень похожа на все остальные. «Полная кластеризация связей», вероятно, является хорошим местом для начала вашего исследования, поскольку оно приводит именно к такому кластеру.

• Затем вы можете взять среднее значение в каждом из этих кластеров, чтобы превратить коллекции очень похожих дорог в одну дорогу, решая проблему (1) (и, надеюсь, (2) тоже).

Это было сделано, следующая задача - отличить «важные» дороги от «несущественных» дорог. Лучший подход здесь состоял бы в том, чтобы сесть и построить учебный набор из нескольких сотен случайных дорог, вручную маркируя их, важны они или нет. Затем возьмите классификатор какого-то типа и обучите их на свой ручной набор. Затем попросите его предсказать, какие другие дороги важны.

Я не могу сказать, какой классификатор лучше всего использовать, но если вы можете сэкономить время, чтобы построить большой учебный комплект и изучить литературу, «нейронные сети» могут дать впечатляющие результаты. Если вы хотите что-то более простое, посмотрите на «случайные леса» или (еще проще) «логистическую регрессию».