ReconstructLine - восстановление линий по точкам в QGIS

Эта страница является черновиком статьи.

Описание инструмента для создания линейных объектов в QGIS.

ReconstructLine - это инструмент для интерактивного создания линейных объектов по точечным.

Вы наверняка сталкивались с инструментом, объединяющим точки в линии. Все такие инструменты работают либо последовательно, т.е. точки объединяются в линии так, как они идут в таблице, либо про атрибутам. Теперь представьте, что вам не важен порядок записей в таблице и атрибутивная информация отсутствует или бесполезна, но что вам все равно нужно объединить точки в линию.

Расширение ReconstructLine умеет восстанавливать линии по точкам, используя только их пространственное расположение, "восстанавливая" линию. Поскольку восстановление - это сложный алгоритм, ReconstructLine работает только интерактивно. Процесс восстановления может занять значительное время, если точек много.

ReconstructLine плохо подходит для облаков точек.

Создано в

Веб ГИС для вашей организации по доступной цене

Замечания по установке

Расширение доступно из официального репозитория.

ReconstructLine находится в разработке и протестирован с QGIS 2.6 и выше. Расширение работает в Windows и Linux (Ubuntu).

Исходный код модуля доступен в (репозитории на Github).

Алгоритм

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

Дан набор точек $T_{1},T_{2},\dots T_{n}$ .
Дана метрика $d(T_{i},T_{j})$ -- функция, которая измеряет расстояния между произвольной парой точек. Тогда потенциальной восстановленной кривой (т.е. последовательности точек $(T_{i_{1}},T_{i_{2}},...,T_{i_{n}})$ ) можно поставить в соответствие её длину, равную сумме растояний между парами точек, составляющих восстановленную кривую: $L=d(T_{i_{1}},T_{i_{2}})+d(T_{i_{2}},T_{i_{3}})+\dots +d(T_{i_{n-1}},T_{i_{n}})$ .
Требуется найти среди всех комбинаций $(T_{i_{1}},T_{i_{2}},...,T_{i_{n}})$ такую комбинацию, для которой ее длина L будет минимальной.

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

Приведенная выше формулировка задачи представляет собой хорошо известную задачу поиска Гамильтонова пути. Также хорошо известно, что эта задача уже при небольшом числе точек не может быть решена "в лоб" простым перебором вариантов, поскольку их число взрыовобразно растет. Так, например, для пяти точек будет всего 60 (т.е. 5!/2) возможных комбинаций, для десяти точек -- уже почти два миллиона, а, например, для тридцати -- количество комбинаций описывется числом, состоящим из 34-х цифр.

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

Работа с расширением

После установки расширения появится новая панель инструментов с двумя кнопками: "копировать точки" и "вставить линию".

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

Исходные точки

Что будет, если просто соединить их в линию (например с помощью расширения Points2One):

Последовательное объединение точек в линию

Для объединения с помощью ReconstructLine:

1. Инструментом выделения выделите нужные точки, нажмите на кнопку "копировать точки" в панели инструментов ReconstructLine

2. Вставьте линию в существующий или новый линейный слой, нажмите на кнопку "вставить линию" в панели инструментов ReconstructLine

Результат должен выглядеть более логично:

Объединение точек в линию с помощью ReconstructLine

Контакты

Если вы нашли ошибку или у вас есть предложения по улучшению расширения — воспользуйтесь багтрекером. Кроме того, вопросы по использованию расширения можно задать авторам напрямую.

Ссылки по теме

ReconstructLine - восстановление линий по точкам в QGIS