Форумы GIS-Lab.info

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

Как выделить висячие концы этих линий т.е. линии, которые имеют один свободный конец (обозначены жёлтым цветом)?

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

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

Не получается. Что там за оператор нужно выбрать?

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

Благодарю. А каков алгоритм? Шеллом не владею, к сожалению...

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

Поправил ошибку в скрипте и перезалил zip.

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

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

Хочу сделать то же самое, но в R. Спрошу ещё в соседней ветке.

rhot писал(а): Вот ещё по теме (правда не open-source): http://gis.stackexchange.com/questions/ ... p-or-grass

А почему не open-source? По ссылке же приводится решение для GRASS:

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, являются висячими

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

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

Приведите пример данных.