Висячие концы линейной сети
- rhot
- Гуру
- Сообщения: 1727
- Зарегистрирован: 25 янв 2011, 17:50
- Репутация: 194
- Ваше звание: доктор
- Откуда: Архангельск
Висячие концы линейной сети
Есть сеть соединённых линий. См. файл.
Как выделить висячие концы этих линий т.е. линии, которые имеют один свободный конец (обозначены жёлтым цветом)?
Как выделить висячие концы этих линий т.е. линии, которые имеют один свободный конец (обозначены жёлтым цветом)?
- Вложения
-
- question_headwaters.jpg (31.99 КБ) 14116 просмотров
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________
-
- Гуру
- Сообщения: 5173
- Зарегистрирован: 26 сен 2009, 16:26
- Репутация: 793
- Ваше звание: званий не имею
- Откуда: Москва
Re: Висячие концы линейной сети
Первая мысль:
- получить из линий их начальные/конечные точки (в GRASS модуль v.to.points с опцией "use=node";
- найти те точки, которые не соприкасаются с линиями (в GRASS модуль v.select);
- сохранить линии, к которым принадлежат выбранные точки, в отдельный слой.
- получить из линий их начальные/конечные точки (в GRASS модуль v.to.points с опцией "use=node";
- найти те точки, которые не соприкасаются с линиями (в GRASS модуль v.select);
- сохранить линии, к которым принадлежат выбранные точки, в отдельный слой.
Редактор материалов, модератор форума
- rhot
- Гуру
- Сообщения: 1727
- Зарегистрирован: 25 янв 2011, 17:50
- Репутация: 194
- Ваше звание: доктор
- Откуда: Архангельск
Re: Висячие концы линейной сети
Не получается. Что там за оператор нужно выбрать?Александр Мурый писал(а):Первая мысль:
- получить из линий их начальные/конечные точки (в GRASS модуль v.to.points с опцией "use=node";
- найти те точки, которые не соприкасаются с линиями (в GRASS модуль v.select);
- сохранить линии, к которым принадлежат выбранные точки, в отдельный слой.
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________
-
- Гуру
- Сообщения: 5173
- Зарегистрирован: 26 сен 2009, 16:26
- Репутация: 793
- Ваше звание: званий не имею
- Откуда: Москва
Re: Висячие концы линейной сети
В общем, я ошибся насчёт v.select, там всё сложней оказалось. Стало интересно, написал "на коленке" шелл-скрипт (модуль) для GRASS 7, который на выходе даёт линии с "висячими концами".
Перед тестированием лучше дублировать исходные данные (мало ли какая ошибка в скрипте).
Код: Выделить всё
./find_deadends.sh in=lines out=lines_find
Редактор материалов, модератор форума
- rhot
- Гуру
- Сообщения: 1727
- Зарегистрирован: 25 янв 2011, 17:50
- Репутация: 194
- Ваше звание: доктор
- Откуда: Архангельск
Re: Висячие концы линейной сети
Благодарю. А каков алгоритм? Шеллом не владею, к сожалению...
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________
-
- Гуру
- Сообщения: 5173
- Зарегистрирован: 26 сен 2009, 16:26
- Репутация: 793
- Ваше звание: званий не имею
- Откуда: Москва
Re: Висячие концы линейной сети
Алгоритм такой:
- получаем нач./конеч. точки линий (v.to.points);
- находим точки с недублирующимися координатами (для этого вываливаем координаты в текстовом виде через <v.out.ascii>, прогоняем через фильтр и загоняем в GRASS через <v.in.ascii>;
- находим линии, которым принадлежат отфильтрованные точки (с помощью <v.distance>); точнее, их категории (cats);
- извлекаем из исходных данных линии с нужными категориями (v.extract).
- получаем нач./конеч. точки линий (v.to.points);
- находим точки с недублирующимися координатами (для этого вываливаем координаты в текстовом виде через <v.out.ascii>, прогоняем через фильтр и загоняем в GRASS через <v.in.ascii>;
- находим линии, которым принадлежат отфильтрованные точки (с помощью <v.distance>); точнее, их категории (cats);
- извлекаем из исходных данных линии с нужными категориями (v.extract).
Редактор материалов, модератор форума
-
- Гуру
- Сообщения: 5173
- Зарегистрирован: 26 сен 2009, 16:26
- Репутация: 793
- Ваше звание: званий не имею
- Откуда: Москва
Re: Висячие концы линейной сети
Поправил ошибку в скрипте и перезалил zip.
Редактор материалов, модератор форума
- rhot
- Гуру
- Сообщения: 1727
- Зарегистрирован: 25 янв 2011, 17:50
- Репутация: 194
- Ваше звание: доктор
- Откуда: Архангельск
Re: Висячие концы линейной сети
Пробовал шелл-скрипт на своих данных - не работает.
Вот ещё по теме (правда не open-source): http://gis.stackexchange.com/questions/ ... p-or-grass. Ответ Кирка может быть полезен, т.к. проливает свет на теорию вычисления (см. теорию графов)
Хочу сделать то же самое, но в R. Спрошу ещё в соседней ветке.
Вот ещё по теме (правда не open-source): http://gis.stackexchange.com/questions/ ... p-or-grass. Ответ Кирка может быть полезен, т.к. проливает свет на теорию вычисления (см. теорию графов)
Хочу сделать то же самое, но в R. Спрошу ещё в соседней ветке.
___________(¯`·.¸(¯`·.¸ Scientia potentia est _/ {SILVA}:::{FOSS}:::{GIS} \_ Знание сила ¸.·´¯)¸.·´¯)___________
-
- Гуру
- Сообщения: 731
- Зарегистрирован: 12 янв 2011, 22:40
- Репутация: 304
- Ваше звание: ∀
Re: Висячие концы линейной сети
А почему не open-source? По ссылке же приводится решение для GRASS:rhot писал(а): Вот ещё по теме (правда не open-source): http://gis.stackexchange.com/questions/ ... p-or-grass
Код: Выделить всё
v.clean in={your input vector} tool=rmdangle thresh={your threshold} out={output vector}
-
- Гуру
- Сообщения: 4067
- Зарегистрирован: 15 окт 2010, 08:33
- Репутация: 1062
- Ваше звание: программист
- Откуда: Казань
Re: Висячие концы линейной сети
можно и на R, но я делал на С++. Нужно построить несколько структур данных, в R для скорости - на массивах, а не на data.framerhot писал(а):Хочу сделать то же самое, но в R. Спрошу ещё в соседней ветке.
1) Грузим все отрезки в память, ID - порядковый номер (насколько я понял, это отдельные линии)
2) Создает структуру с записями для концов линий (X,Y,ID.line) - координаты концов линии + ее ID (2 записи на линию)
3) Нужно найти всех соседей. Вот тут могут быть проблемы либо со скоростью, либо с памятью, либо и с тем и с другим. Если линий мало, просто используем dist() (и имеем проблемы с памятью) и потом считаем, сколько соседей имеет расстояние менее порога "слипания". Если линий много, то строим триангуляцию, и ищем соседей в ней (либо непосредственных: dnearneigh(), tri2nb() {spdep}, либо циклом по улитке в триангуляции - тогда проблемы со скоростью)
4) считаем (aggregate(), table()) сколько концов, имеющих 2 и более соседей (1 - сам), у каждого ID, и те ID, у которых таких концов менее 2, являются висячими
-
- Гуру
- Сообщения: 731
- Зарегистрирован: 12 янв 2011, 22:40
- Репутация: 304
- Ваше звание: ∀
Re: Висячие концы линейной сети
Несколько раз приходилось собирать граф из геометрий на Python. На практике координаты концов полилиний не всегда совпадают точно, поэтому использовал такой алгоритм:
1. Завожу пространственный индекс для вершин. У меня был самопальный велосипед, но если бы делал сейчас, использовал бы R-tree, реализованное в libspatialindex. Если координаты целочисленные и гарантированно стыкуются точка в точку, вместо пространственного индекса хватит хэш-таблицы с координатами.
2. Читаю полилинии из набора данных, заношу координаты обоих концов в пространственный индекс, если их там ещё нет; если там уже есть точка в пределах заданного радиуса, то беру её. Попутно заполняю список рёбер со ссылками на начало и конец каждого ребра. Чтобы можно было быстро считать степени вершин и обходить граф, в структуру данных, описывающую вершину, добавляю ссылки на примыкающие рёбра. В результате мы для каждой вершины можем получить список инцидентных рёбер, а для каждого ребра - две вершины, являющиеся его концами.
3. Имея такую структуру данных, найти висячие концы просто: находим вершину со степенью 1 и от неё проходим по цепочке рёбер, пока не встретим вершину со степенью, отличной от 2. Пройденные вершины и рёбра помечаем. Повторяем для всех ещё не помеченных вершин со степенью 1.
1. Завожу пространственный индекс для вершин. У меня был самопальный велосипед, но если бы делал сейчас, использовал бы R-tree, реализованное в libspatialindex. Если координаты целочисленные и гарантированно стыкуются точка в точку, вместо пространственного индекса хватит хэш-таблицы с координатами.
2. Читаю полилинии из набора данных, заношу координаты обоих концов в пространственный индекс, если их там ещё нет; если там уже есть точка в пределах заданного радиуса, то беру её. Попутно заполняю список рёбер со ссылками на начало и конец каждого ребра. Чтобы можно было быстро считать степени вершин и обходить граф, в структуру данных, описывающую вершину, добавляю ссылки на примыкающие рёбра. В результате мы для каждой вершины можем получить список инцидентных рёбер, а для каждого ребра - две вершины, являющиеся его концами.
3. Имея такую структуру данных, найти висячие концы просто: находим вершину со степенью 1 и от неё проходим по цепочке рёбер, пока не встретим вершину со степенью, отличной от 2. Пройденные вершины и рёбра помечаем. Повторяем для всех ещё не помеченных вершин со степенью 1.
-
- Гуру
- Сообщения: 5173
- Зарегистрирован: 26 сен 2009, 16:26
- Репутация: 793
- Ваше звание: званий не имею
- Откуда: Москва
Re: Висячие концы линейной сети
Приведите пример данных.rhot писал(а):Пробовал шелл-скрипт на своих данных - не работает.
Редактор материалов, модератор форума
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 1 гость