Висячие концы линейной сети

Кроме QGIS
Ответить
Аватара пользователя
rhot
Гуру
Сообщения: 1727
Зарегистрирован: 25 янв 2011, 17:50
Репутация: 194
Ваше звание: доктор
Откуда: Архангельск

Висячие концы линейной сети

Сообщение rhot » 06 окт 2015, 15:57

Есть сеть соединённых линий. См. файл.

Как выделить висячие концы этих линий т.е. линии, которые имеют один свободный конец (обозначены жёлтым цветом)?
Вложения
question_headwaters.jpg
question_headwaters.jpg (31.99 КБ) 13805 просмотров
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________

Александр Мурый
Гуру
Сообщения: 5173
Зарегистрирован: 26 сен 2009, 16:26
Репутация: 793
Ваше звание: званий не имею
Откуда: Москва

Re: Висячие концы линейной сети

Сообщение Александр Мурый » 06 окт 2015, 16:35

Первая мысль:
- получить из линий их начальные/конечные точки (в GRASS модуль v.to.points с опцией "use=node";
- найти те точки, которые не соприкасаются с линиями (в GRASS модуль v.select);
- сохранить линии, к которым принадлежат выбранные точки, в отдельный слой.
Редактор материалов, модератор форума

Аватара пользователя
rhot
Гуру
Сообщения: 1727
Зарегистрирован: 25 янв 2011, 17:50
Репутация: 194
Ваше звание: доктор
Откуда: Архангельск

Re: Висячие концы линейной сети

Сообщение rhot » 06 окт 2015, 17:02

Александр Мурый писал(а):Первая мысль:
- получить из линий их начальные/конечные точки (в GRASS модуль v.to.points с опцией "use=node";
- найти те точки, которые не соприкасаются с линиями (в GRASS модуль v.select);
- сохранить линии, к которым принадлежат выбранные точки, в отдельный слой.
Не получается. Что там за оператор нужно выбрать?
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________

Александр Мурый
Гуру
Сообщения: 5173
Зарегистрирован: 26 сен 2009, 16:26
Репутация: 793
Ваше звание: званий не имею
Откуда: Москва

Re: Висячие концы линейной сети

Сообщение Александр Мурый » 06 окт 2015, 18:43

В общем, я ошибся насчёт v.select, там всё сложней оказалось. Стало интересно, написал "на коленке" шелл-скрипт (модуль) для GRASS 7, который на выходе даёт линии с "висячими концами".

Код: Выделить всё

./find_deadends.sh in=lines out=lines_find
find_deadends.sh.zip
(1016 байт) 402 скачивания
Перед тестированием лучше дублировать исходные данные (мало ли какая ошибка в скрипте).
Редактор материалов, модератор форума

Аватара пользователя
rhot
Гуру
Сообщения: 1727
Зарегистрирован: 25 янв 2011, 17:50
Репутация: 194
Ваше звание: доктор
Откуда: Архангельск

Re: Висячие концы линейной сети

Сообщение rhot » 06 окт 2015, 19:07

Благодарю. А каков алгоритм? Шеллом не владею, к сожалению...
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________

Александр Мурый
Гуру
Сообщения: 5173
Зарегистрирован: 26 сен 2009, 16:26
Репутация: 793
Ваше звание: званий не имею
Откуда: Москва

Re: Висячие концы линейной сети

Сообщение Александр Мурый » 06 окт 2015, 23:53

Алгоритм такой:
- получаем нач./конеч. точки линий (v.to.points);
- находим точки с недублирующимися координатами (для этого вываливаем координаты в текстовом виде через <v.out.ascii>, прогоняем через фильтр и загоняем в GRASS через <v.in.ascii>;
- находим линии, которым принадлежат отфильтрованные точки (с помощью <v.distance>); точнее, их категории (cats);
- извлекаем из исходных данных линии с нужными категориями (v.extract).
Редактор материалов, модератор форума

Александр Мурый
Гуру
Сообщения: 5173
Зарегистрирован: 26 сен 2009, 16:26
Репутация: 793
Ваше звание: званий не имею
Откуда: Москва

Re: Висячие концы линейной сети

Сообщение Александр Мурый » 07 окт 2015, 16:01

Поправил ошибку в скрипте и перезалил zip.
Редактор материалов, модератор форума

Аватара пользователя
rhot
Гуру
Сообщения: 1727
Зарегистрирован: 25 янв 2011, 17:50
Репутация: 194
Ваше звание: доктор
Откуда: Архангельск

Re: Висячие концы линейной сети

Сообщение rhot » 14 мар 2016, 21:11

Пробовал шелл-скрипт на своих данных - не работает.

Вот ещё по теме (правда не open-source): http://gis.stackexchange.com/questions/ ... p-or-grass. Ответ Кирка может быть полезен, т.к. проливает свет на теорию вычисления (см. теорию графов)

Хочу сделать то же самое, но в R. Спрошу ещё в соседней ветке.
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________

Ariki
Гуру
Сообщения: 731
Зарегистрирован: 12 янв 2011, 22:40
Репутация: 304
Ваше звание:

Re: Висячие концы линейной сети

Сообщение Ariki » 14 мар 2016, 21:24

rhot писал(а): Вот ещё по теме (правда не open-source): http://gis.stackexchange.com/questions/ ... p-or-grass
А почему не open-source? По ссылке же приводится решение для GRASS:

Код: Выделить всё

v.clean in={your input vector} tool=rmdangle thresh={your threshold} out={output vector}

gamm
Гуру
Сообщения: 4044
Зарегистрирован: 15 окт 2010, 08:33
Репутация: 1049
Ваше звание: программист
Откуда: Казань

Re: Висячие концы линейной сети

Сообщение gamm » 14 мар 2016, 21:36

rhot писал(а):Хочу сделать то же самое, но в R. Спрошу ещё в соседней ветке.
можно и на R, но я делал на С++. Нужно построить несколько структур данных, в R для скорости - на массивах, а не на data.frame

1) Грузим все отрезки в память, ID - порядковый номер (насколько я понял, это отдельные линии)
2) Создает структуру с записями для концов линий (X,Y,ID.line) - координаты концов линии + ее ID (2 записи на линию)
3) Нужно найти всех соседей. Вот тут могут быть проблемы либо со скоростью, либо с памятью, либо и с тем и с другим. Если линий мало, просто используем dist() (и имеем проблемы с памятью) и потом считаем, сколько соседей имеет расстояние менее порога "слипания". Если линий много, то строим триангуляцию, и ищем соседей в ней (либо непосредственных: dnearneigh(), tri2nb() {spdep}, либо циклом по улитке в триангуляции - тогда проблемы со скоростью)
4) считаем (aggregate(), table()) сколько концов, имеющих 2 и более соседей (1 - сам), у каждого ID, и те ID, у которых таких концов менее 2, являются висячими

Ariki
Гуру
Сообщения: 731
Зарегистрирован: 12 янв 2011, 22:40
Репутация: 304
Ваше звание:

Re: Висячие концы линейной сети

Сообщение Ariki » 14 мар 2016, 22:52

Несколько раз приходилось собирать граф из геометрий на Python. На практике координаты концов полилиний не всегда совпадают точно, поэтому использовал такой алгоритм:
1. Завожу пространственный индекс для вершин. У меня был самопальный велосипед, но если бы делал сейчас, использовал бы R-tree, реализованное в libspatialindex. Если координаты целочисленные и гарантированно стыкуются точка в точку, вместо пространственного индекса хватит хэш-таблицы с координатами.
2. Читаю полилинии из набора данных, заношу координаты обоих концов в пространственный индекс, если их там ещё нет; если там уже есть точка в пределах заданного радиуса, то беру её. Попутно заполняю список рёбер со ссылками на начало и конец каждого ребра. Чтобы можно было быстро считать степени вершин и обходить граф, в структуру данных, описывающую вершину, добавляю ссылки на примыкающие рёбра. В результате мы для каждой вершины можем получить список инцидентных рёбер, а для каждого ребра - две вершины, являющиеся его концами.
3. Имея такую структуру данных, найти висячие концы просто: находим вершину со степенью 1 и от неё проходим по цепочке рёбер, пока не встретим вершину со степенью, отличной от 2. Пройденные вершины и рёбра помечаем. Повторяем для всех ещё не помеченных вершин со степенью 1.

Александр Мурый
Гуру
Сообщения: 5173
Зарегистрирован: 26 сен 2009, 16:26
Репутация: 793
Ваше звание: званий не имею
Откуда: Москва

Re: Висячие концы линейной сети

Сообщение Александр Мурый » 14 мар 2016, 22:55

rhot писал(а):Пробовал шелл-скрипт на своих данных - не работает.
Приведите пример данных.
Редактор материалов, модератор форума

Ответить

Вернуться в «Свободные, бесплатные, открытые ГИС»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 6 гостей