Соединение линейных объектов и определение длины самой длинной линии

12

У меня есть линейный объект (см. Изображение), представляющий реку, которую я создал с помощью инструмента Stream_to_Feature. Таблица атрибутов содержит несколько записей, представляющих разные строки - проблема в том, что самая длинная строка (легко различимая визуально) не представлена ​​в таблице как одна строка, на самом деле она состоит из множества меньших строк. Линии кажутся соприкасающимися, хотя они не пересекаются друг с другом.

Как я могу объединить эти строки и затем определить длину самой длинной линии, используя ArcObjects или ручные методы, которые я могу преобразовать в ArcObjects? Еще более удачное решение - избавиться от всех притоков и оставить меня в русле реки.

Линия особенность - река

радиолокационный
источник
1
Они подключаются вообще? Вы сказали, что они не пересекаются, но означает ли это, что они не разделяют вершины?
Натанус
1
Извините - мне следовало быть более ясным. Они имеют общие вершины, но не полностью пересекают друг друга.
Радар
Вы знаете, где находится устье реки? Является ли река всегда деревом (один уникальный путь от каждого устья до устья)?
Кирк Куйкендалл
3
На самом деле, вы не хотите, чтобы длина "самой длинной линии". Это может быть маршрут от одного верхнего потока к другому удаленному восходящему направлению. Это произойдет, когда две основные ветви потока соединятся у его устья. Вместо этого вам нужен самый длинный маршрут между устьем и любой другой конечной точкой в ​​потоке. (Эта характеристика даже не требует, чтобы поток был представлен в виде дерева: он может заплетаться и иметь острова.)
whuber
@whuber - ваша оценка верна - есть идеи, как мне это сделать, используя маршруты?
Радар

Ответы:

18

Во-первых, небольшой фон, чтобы указать, почему это не сложная проблема. Поток через реку гарантирует, что ее сегменты, если они правильно оцифрованы, всегда могут быть ориентированы для формирования ориентированного ациклического графа (DAG). В свою очередь, граф может быть линейно упорядочен тогда и только тогда, когда это DAG, используя метод, известный как топологическая сортировка . Топологическая сортировка быстрая: ее требования к времени и пространству равны O (| E | + | V |) (E = количество ребер, V = количество вершин), что вполне приемлемо. Создание такого линейного порядка позволит легко найти основную часть русла реки.

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

Чтобы сделать это более понятным, я предлагаю некоторый (непроверенный) псевдокод . Входные данные представляют собой набор линейных сегментов (или дуг) S (содержащих оцифрованный поток), каждый из которых имеет две различные конечные точки - начало (S) и конец (S) и положительную длину - длину (S); и устье реки р , которое является точкой. Выход представляет собой последовательность сегментов, объединяющих устье с наиболее удаленной точкой вверх по течению.

Нам нужно будет работать с «отмеченными сегментами» (S, p). Они состоят из одного из сегментов S и одной из двух его конечных точек, p . Нам нужно будет найти все сегменты S, которые совместно используют конечную точку с контрольной точкой q , пометить эти сегменты другими их конечными точками и вернуть набор:

Procedure Extract(q: point, A: set of segments): Set of marked segments.

Когда такой сегмент не может быть найден, Extract должен вернуть пустой набор. Как побочный эффект, Extract должен удалить все сегменты, которые он возвращает из набора A, тем самым изменив сам A.

Я не даю реализацию Extract: ваша ГИС предоставит возможность выбирать сегменты S, совместно использующие конечную точку с q . Для их маркировки достаточно просто сравнить начало (S) и конец (S) с q и вернуть то, что из двух конечных точек не совпадает.

Теперь мы готовы решить проблему.

Procedure LongestUpstreamReach(p: point, A: set of segments): (Array of segments, length)
    A0 = A                        // Optional: preserves A
    C = Extract(p, A0)            // Removes found segments from the set A0!
    L = 0; B = empty array
    For each (S,q) in C:          // Loop over the segments meeting point p
        (B0, M) = LongestUpstreamReach(q, A0)
        If (length(S) + M > L) then
            B = append(S, B0)
            L = length(S) + M
        End if
    End for
    Return (B, L)
End LongestUpstreamReach

Процедура append (S, B0) вставляет сегмент S в конец массива B0 и возвращает новый массив.

(Если поток действительно является деревом: нет островов, озер, кос и т. Д., То вы можете обойтись без шага копирования A в A0 .)

Ответ на оригинальный вопрос заключается в формировании объединения сегментов, возвращаемых LongestUpstreamReach.

Для иллюстрации рассмотрим поток на исходной карте. Предположим, он оцифрован как коллекция из семи дуг. Дуга a идет от устья в точке 0 (вверху карты, справа на рисунке ниже, который повернут) вверх по течению до первого слияния в точке 1. Это длинная дуга, скажем, 8 единиц в длину. Дуга b ветвится слева (на карте) и короткая, около 2 единиц в длину. Дуга c разветвляется вправо и имеет длину около 4 единиц и т. Д. Обозначения «b», «d» и «f» обозначают ветви с левой стороны, когда мы идем сверху вниз на карте, и «a», «c», «e» и «g» - другие ветви и нумерация вершин от 0 до 7, мы можем абстрактно представить граф как набор дуг

A = {a=(0,1), b=(1,2), c=(1,3), d=(3,4), e=(3,5), f=(5,6), g=(5,7)}

Я полагаю , что они имеют длину 8, 2, 4, 1, 2, 2, 2 для через г , соответственно. Рот вершины 0.

фигура

Первый пример - это вызов Extract (5, {f, g}). Возвращает набор отмеченных сегментов {(f, 6), (g, 7)}. Обратите внимание, что вершина 5 находится в месте слияния дуг f и g (две дуги внизу карты) и что (f, 6) и (g, 7) помечают каждую из этих дуг своими конечными точками вверх по течению .

Следующим примером является вызов LongestUpstreamReach (0, A). Первое действие, которое требуется, это вызов Extract (0, A). Это возвращает набор, содержащий отмеченный сегмент (a, 1), и удаляет сегмент a из набора A0 , который теперь равен {b, c, d, e, f, g}. Существует одна итерация цикла, где (S, q) = (a, 1). Во время этой итерации вызывается LongestUpstreamReach (1, A0). Рекурсивно, он должен возвращать либо последовательность (g, e, c), либо (f, e, c): обе одинаково действительны. Длина (M), которую он возвращает, равна 4 + 2 + 2 = 8. (Обратите внимание, что LongestUpstreamReach не изменяет A0 .) В конце цикла сегмент aбыл добавлен к слою потока, а длина была увеличена до 8 + 8 = 16. Таким образом, первое возвращаемое значение состоит из последовательности (g, e, c, a) или (f, e, c, a), с длиной 16 в любом случае для второго возвращаемого значения. Это показывает, как LongestUpstreamReach просто движется вверх по течению от устья, выбирая при каждом слиянии ветвь с наибольшим расстоянием, которое еще предстоит пройти, и отслеживает сегменты, пройденные по ее маршруту.

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

Whuber
источник
+1 Если бы они знали это до того, как назвали реку Миссури.
Кирк Куйкендалл
1
@Kirk Рекурсивное исследование американского Запада в начале 1800-х было нелегким :-).
whuber
это удивительно полезно! Я посмотрю, смогу ли я получить эту настройку в своей ГИС и поделиться некоторым полезным кодом, как только я получу его работу. Ура!
Радар
Хороший ответ whuber
Ragi Yaser Burhum
2

Инструмент Unsplit Line может быть полезен для того, что вы пытаетесь сделать, хотя вам нужно будет найти какой-то метод, чтобы отличить одну ветвь потока от другой (для поля растворения). Это предполагает, что у вас есть лицензия ArcInfo.

Если у вас нет такой лицензии, вы можете рассмотреть подход ArcObjects, в котором XY каждой вершины заполняется IPointCollection, а затем создается IGeometryкак a PolyLineClass.

Nathanus
источник
1

Вы можете использовать RivEX , это инструмент ArcGIS 9.1 (который будет работать в 9.3 и 10). Он имеет инструменты для выявления топологических проблем с речными сетями и множество инструментов обработки. Один из таких инструментов находит основной ствол .

Hornbydd
источник