Я ищу эффективный способ кластеризации линий независимо от их направления. Это означает, что линия между Нью-Йорком и Лос-Анджелесом должна находиться в том же кластере, что и линия в другом направлении между Лос-Анджелесом и Нью-Йорком. Расположение начальной / конечной точек должно быть аналогичным (т.е. Сан-Диего и Лонг-Айленд должны находиться в том же кластере, что и Лос-Анджелес, но, вероятно, не Сан-Франциско-Бостон), и промежуточных точек не должно быть. Входные данные будут похожи на этот пример:
(Кассиопея сладкая в японской Википедии GFDL или CC-BY-SA-3.0 , через Викисклад)
Ранее я пытался заранее отсортировать линии, например, чтобы все они проходили с запада на восток, но это не решает проблему линий, идущих с севера на юг и наоборот.
Вы знаете какой-нибудь алгоритм, имеющий дело с этой проблемой? Я искал, но кроме Алгоритма для вычисления среднего направления ненаправленных сегментов, я не нашел ничего отдаленно полезного, поэтому я должен использовать неправильные условия поиска.
источник
Ответы:
Если я вас правильно понимаю, вы хотите сгруппировать линии, которые примерно одинаковы, независимо от направления.
Вот идея, которая, я думаю, могла бы сработать.
разделить линии в начальной и конечной точках
Кластер точек и получить идентификатор кластера
Найти строки с одинаковой комбинацией идентификатора кластера. Это кластер
Это должно быть возможно в PostGIS (конечно :-)) версии 2.3
Я не тестировал функцию ST_ClusterDBSCAN, но она должна делать эту работу.
Если у вас есть таблица строк, как это:
И вы хотите создать кластер, где начальная и конечная точки находятся на расстоянии не более 10 км друг от друга. И для кластера должно быть как минимум 2 точки, тогда запрос может выглядеть примерно так:
Присоединяясь к
a.cluster_id<b.cluster_id
вам, вы получаете сопоставимый идентификатор кластера независимо от направления.источник
Вы действительно хотите кластеризоваться исключительно по направлению, без учета происхождения или назначения? Если это так, есть несколько очень простых способов. Возможно, самый простой - это вычислить направление каждой линии, удвоить его и построить в виде точки на окружности. Поскольку подшипники вперед-назад различаются на 180 градусов, они отличаются на 360 градусов после удвоения и, следовательно, располагаются в одном и том же месте. Теперь сгруппируйте точки на плоскости, используя любой метод, который вам нравится.
Вот рабочий пример
R
с выводом линий, окрашенных в соответствии с каждым из четырех кластеров. Конечно, вы, вероятно, будете использовать ГИС для расчета подшипников - я использовал евклидовы подшипники для простоты.источник
Ваше разъяснение вопроса указывает на то, что вы хотите, чтобы кластеризация основывалась на фактических отрезках линии , в том смысле, что любые две пары отправления-назначения (OD) следует рассматривать как «близкие», когда оба источника близки, а оба получателя близки. , независимо от того, какой момент считается происхождения или назначения .
Эта формулировка предполагает, что у вас уже есть ощущение расстояния d между двумя точками: это может быть расстояние, когда самолет летит, расстояние на карте, время в пути туда и обратно или любая другая метрика, которая не изменяется, когда O и D переключился. Единственное осложнение состоит в том, что сегменты не имеют уникальных представлений: они соответствуют неупорядоченным парам {O, D}, но должны быть представлены как упорядоченные пары, (O, D) или (D, O). Поэтому мы можем принять расстояние между двумя упорядоченными парами (O1, D1) и (O2, D2) за некоторую симметричную комбинацию расстояний d (O1, O2) и d (D1, D2), например их сумму или квадрат корень суммы их квадратов. Давайте напишем эту комбинацию как
Просто определите расстояние между неупорядоченными парами, чтобы оно было меньше из двух возможных расстояний:
На данный момент вы можете применить любой метод кластеризации на основе матрицы расстояний.
В качестве примера я вычислил все 190 расстояний между двумя точками на карте для 20 самых густонаселенных городов США и запросил восемь кластеров, используя иерархический метод. (Для простоты я использовал евклидовы вычисления расстояний и применил методы по умолчанию в программном обеспечении, которое я использовал: на практике вы захотите выбрать подходящие расстояния и методы кластеризации для вашей задачи). Вот решение, с кластерами, обозначенными цветом каждого отрезка. (Цвета были случайным образом назначены кластерам.)
Вот
R
код, который произвел этот пример. Его ввод - текстовый файл с полями «Долгота» и «Широта» для городов. (Для обозначения городов на рисунке также имеется поле «Ключ».)источник