Просмотр исходного текста страницы ReconstructLine - восстановление линий по точкам в QGIS

==== Случай одной линии ====

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

* Дан набор точек <math>T_1, T_2, \dots T_n</math>.
* Дана метрика <math>d(T_i, T_j)</math> -- функция, которая измеряет расстояния между произвольной парой точек. Тогда потенциальной восстановленной кривой (т.е. последовательности точек <math>(T_{i_1}, T_{i_2}, ..., T_{i_n})</math>) можно поставить в соответствие её длину, равную сумме растояний между парами точек, составляющих восстановленную кривую: <math>L = d(T_{i_1}, T_{i_2}) + d(T_{i_2}, T_{i_3}) + \dots + d(T_{i_{n-1}}, T_{i_n})</math>.
* Требуется найти среди всех комбинаций <math>(T_{i_1}, T_{i_2}, ..., T_{i_n})</math> такую комбинацию, для которой ее длина L будет минимальной.

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

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

Поэтому алгоритмы построения Гамильтонова пути, используемые на практике, представляют собой субоптимальные алгоритмы, которые позволяют найти хорошее решение за приемлемое время, но не гарантируют того, что оно будет лучшим из всех возможных. В данном модуле в качестве основного алгорима использовались  [https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%BC%D0%BE%D0%BE%D1%80%D0%B3%D0%B0%D0%BD%D0%B8%D0%B7%D1%83%D1%8E%D1%89%D0%B0%D1%8F%D1%81%D1%8F_%D0%BA%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0 самоорганизующиеся карты Кохонена]. Поскольку перед нами стоит задача восстановления линии, то и архитектура сети была выбрана линейной. Обученная сеть упорядочивает точки и в целом обеспечивает неплохой результат работы. Но в некоторых случаях "неудачного" расположения входных точек с одним узлом сети оказываются связаны несколько точек, их упорядоченность может оказаться нарушенной. Для того, чтобы отследить подобные случаи, в модуле используется постобработка: в упорядоченном картой Кохонена наборе точек производятся попарные перестановки соседних точек и измеряется совокупная длина линии. В итоге линия наименьшей длины возвращается в качестве результата алгоритма.