ReconstructLine - восстановление линий по точкам в QGIS
Описание инструмента для создания линейных объектов в QGIS.
ReconstructLine - это инструмент для интерактивного создания линейных объектов по точечным.
Вы наверняка сталкивались с инструментом объединяющим точки в линии. Все такие инструменты работают либо последовательно, т.е. точки объединяются в линии так, как они идут в таблице, либо про атрибутам. Теперь представьте, что вам не важен порядок записей в таблице и атрибутивная информация отсутствует или бесполезна, что вам все равно нужно объединить точки в линию.
Расширение ReconstructLine умеет восстанавливать линии по точкам используя только их пространственное расположение, "восстанавливая" линию. Поскольку восстановление это сложный алгоритм, ReconstructLine работает только интерактивно. Процесс восстановления может занять значительное время, если точек много.
ReconstructLine плохо подходит для облаков точек.
| Создано в | 
|
Веб ГИС для вашей организации по доступной цене |
Замечания по установке
Расширение доступно из официального репозитория.
ReconstructLine находится в разработке и протестирован с QGIS 2.6 и выше. Расширение работает в Windows и Linux (Ubuntu).
Исходный код модуля доступен в (репозитории на Github).
Алгоритм
При разработке модуля принималось во внимание то, что точки можно соединить между собой "логичным" образом, если они образуют "видимую глазами" кривую линию. В этом случае задачу можно сформулировать следующим образом:
- Дан набор точек T1, T2, ... Tn.
- Дана метрика d(Ti, Tj) -- функция, которая измеряет расстояния между произвольной парой точек. Тогда потенциальной восстановленной кривой (т.е. последовательности точек (Ti1, Ti2, ..., Tin)) можно поставить в соответствие её длину, равную сумме растояний между парами точек, составляющих восстановленную кривую: L = d(Ti1, Ti2) + d(Ti2, Ti3) + .... + d(Tin-1, Tin).
- Требуется найти среди всех комбинаций (Ti1, Ti2, ..., Tin) такую комбинацию, для которой ее длина L будет минимальной.
Требование того, что восстановленная кривая должна иметь минимальную длину из всех возможных комбинаций -- чисто эвристическое допущение, которое, тем не менее, хорошо согласуется с реальным положением дел. (Чтобы убедиться в этом достаточно нарисовать кривую, измерить ее длину, затем "перепутать" в ней пару или несколько пар точек и измерить длину новой кривой).
Приведенная выше формулировка задачи представляет собой по сути хорошо известную задачи поиска Гамильтонова пути. Также хорошо известно, что эта задача уже при небольшом числе точек не может быть решена "в лоб" простым перебором вариантов поскольку их число взрыовобразно растет. Так, например, для пяти точке будет всего 60 (5!/2) возможных комбинаций, для десяти уже почти два миллиона, а для двадцати точек количество комбинаций описывется числом с 19-ю нулями.
Работа с расширением
После установки расширения появится новая панель инструментов с двумя кнопками: "копировать точки" и "вставить линию".
Предположим, что исходный набор точек выглядит следующим образом (обратите внимание на нумерацию, она отражает последовательность точек в таблице):
Что будет, если просто соединить их в линию (например с помощью расширения Points2One):
Для объединения с помощью ReconstructLine:
1. Инструментом выделения выделите нужные точки, нажмите на кнопку "копировать точки" в панели инструментов ReconstructLine
2. Вставьте линию в существующий или новый линейный слой, нажмите на кнопку "вставить линию" в панели инструментов ReconstructLine
Результат должен выглядеть более логично:
Контакты
Если вы нашли ошибку или у вас есть предложения по улучшению расширения — воспользуйтесь багтрекером. Кроме того, вопросы по использованию расширения можно задать авторам напрямую.