Пересекающиеся линии -> 1 линя

[oleg]

Есть шейп пресекающихся между собой линий (замкнутые, отрезки, кривые).
Задача конвертировать это множество линий в одну, с одной начальной и одной конечной точкой.
При необходимости результирующая линия может проходить несколько раз вперёд-назад точка-в-точку сама над собой.

Просьба подсказать инструменты и способы, если реализация возможна.
Спасибо.

[Александр Мурый]

Было бы неплохо увидеть пример файла, а то на словах не очень ясно.
Т.е. нужно просто объединить все линии в файле в одну полилинию? Или надо выбрать какие-то по признакам (атрибуты и т.д.) и уже потом объединить. Или объединение нужно вообще для сетевой анализа?

[oleg]

Да, просто преобразовать все линии в файле в одну линию. Пример - карта OSM, без точек.
Вариант "обхода" красным в примере. Для наглядности неизбежные двойные линии изобразил параллельными.

[Voltron]

Для QGIS есть модуль JoinLines, но пока без поддержки пакетного режима, т.е. «клеить» отрезки надо вручную.

[Александр Мурый]

Если не трудно, выложите пример самого SHP-файла. Интересно попробовать объединить линии в одну в GRASS.

[oleg]

Пример шейпа в аттаче. Родилось необязательное пожелание - хорошо, если результирующая линия будет минимальной длины (но это не критично). Спасибо за внимание к теме!

[Александр Мурый]

хорошо, если результирующая линия будет минимальной длины (но это не критично)

Т.е. надо вычислить кратчайший путь по всем линиям от какой-то начальной точки к какой-то конечной, так? Тогда вопрос: каковы начальная и конечная точки?
Если задача не в этом, тогда вопрос: в чём задача (кроме просто объединения линий в одну)?

[oleg]

Кроме просто объединения линий в одну задач нет, это конечная цель. Начальной и конечной точки нет, можно брать любые. Пожелание по длине родилось исходя лишь из мысли о меньшем размере результирующих данных (но в моем случае это не обязательно).

Да, кратчайший путь обхода - подходящее и ёмкое определение. В эту сторону не пробовал искать еще. Наверно должно быть что-то готовое для решения задачи обхода... например всех троп или просек с целью наблюдения...

[oleg]

Если вдруг у кого-то возникнут идеи на эту тему - выходите, пожалуйста, на связь, задача всё-еще актуальна.

[KolesovDmitry]

кратчайший путь обхода - подходящее и ёмкое определение.

В такой формулировке это задача Штейнера, в GRASS GIS есть соответствующий модуль для ее решения, наверняка такое есть и в других ГИС.
Есть загвоздка: я не уверен, что этот модуль возвращает одну линию, скорее всего решение представляет собой набор соприкасающихся сегментов. Решить эту проблему "дешево и сердито" я предлагаю так: создайте буферную зону вокруг полученных линий размером "эпсилон -> 0", а потом преобразуйте площадной буфер к линии, получится ПОЧТИ то, что вам нужно.