Визуализация контуров стационарных железнодорожных объектов на основе кусочно-полиномиальной аппроксимации координат спутниковых данных Шаповалова Елизавета Юрьевна

Содержание к диссертации

Введение

Глава 1. Визуализация железнодорожного пути на основе кусочно-полиномиальной аппроксимации оцифрованного массива декартовых координат 31

1.1. Разбиение массива точек на отрезки 31

1.2. Построение интерполяционного полинома 33

1.3. Сравнение предложенного метода аппроксимации с существующими 48

1.4. Выводы 49

Глава 2. Расчет и визуализация нормали и касательной в произвольной точке линии железнодорожного пути 51

2.1. Алгоритм построения нормали и касательной 51

2.2. Определение уравнения нормали в выбранной точке, расчет точек, отстоящих от кривой на заданную длину отрезка 52

2.3. Идентификация направления нормали 59

2.4. Результаты программного эксперимента. 70

2.5. Выводы 73

Глава 3. Расчет и визуализация землеотвода участка железных дорог 74

3.1. Определения и термины 74

3.2. Поиск контейнера отрезков прямых, составляющих границу станции (верхнюю или нижнюю) 78

3.3. Расчет координат землеотвода по найденному контейнеру отрезков прямых 83

3.4. Формальное описание алгоритма поиска контейнера граничных отрезков прямых 98

3.5. Расчет координат землеотвода по найденному контейнеру Отрезков прямых 104

3.6. Оценка временной сложности алгоритма построения землеотвода 106

3.7. Примеры визуализации полосы отвода 107

3.8. Сравнение предложенного метода построения полосы отвода с существующими аналогами 110

3.9. Выводы 112

Заключение 114

Литература 116

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

Введение к работе

Актуальность темы. Информационные технологии внедряются во все сферы народного хозяйства, позволяя автоматизировать анализ и управление различными информационными и производственными процессами. В частности, это относится к железнодорожной отрасли. Для решения задач проектирования при реконструкции парков железнодорожных станций и строительства новых применяются специальные редакторы, позволяющие с достаточно высокой точностью воссоздать визуальную модель будущего объекта. Такие системы дают возможность визуализировать данные координат спутниковой фотосъемки стационарных объектов и их контуров, при этом ставится вопрос о точности аппроксимации данных при отображении. Известные способы аппроксимации не всегда позволяют отображать набор произвольных кривых, не всегда подходят для построения контуров полосы отвода вследствие сложности визуализации контуров незамкнутых объектов. Существующие алгоритмы буферизации позволяют визуализировать буферную зону точечных, линейных и простейших полигональных объектов, но, как правило, не вычисляют внешнюю границу рассматриваемого объекта. Это не дает возможности использовать известные алгоритмы для визуализации незамкнутых контуров объектов и путей, построения и отображения полосы отвода схем железнодорожных станций, представляющих собой набор полигонов. Таким образом, задача визуализации контуров стационарных объектов, линий пути и буферной зоны сложных незамкнутых объектов является не решенной в полной мере и актуальной.

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

Цель диссертационной работы состоит в создании методов, синтеза на их основе и программной реализации алгоритмов визуализации линий железнодорожных путей, а также контуров буферной зоны сложных незамкнутых объектов по координатам спутниковой фотосъемки.

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

1. Разработать метод, синтезировать и программно реализовать алгоритм визуализации железнодорожного пути, заданного массивом координат спутниковой фотосъемки, на основе кусочно-полиномиальной аппроксимации линии пути с помощью интерполяционных полиномов Ньютона инвариантно относительно выбора участка пути.

2. Разработать метод, синтезировать и программно реализовать алгоритм построения и визуализации касательных и нормалей определенного направления параметрически заданной кривой для расчета, а также визуализации контура участка железнодорожного пути, представленного массивом координат.

3. Разработать метод, синтезировать и реализовать алгоритм автоматического поиска граничных отрезков кривых, заданных последовательностями координат спутниковой фотосъемки; для контейнера граничных отрезков кривых синтезировать и программно реализовать алгоритм расчета и визуализации узловых точек полосы отвода.

4 4. Синтезировать и программно реализовать алгоритм построения и визуализации буферной зоны сложных объектов на примере полосы отвода схемы станции со свойством инвариантности построения буферизации.

Научная новизна результатов диссертационной работы заключается в следующем:

4. Разработан метод, синтезирован и программно реализован алгоритм визуализации железнодорожного пути, заданного массивом координат спутниковой фотосъемки; метод и алгоритм отличаются от известных программной процедурой кусочно-полиномиальной аппроксимации линии пути на основе интерполяционных полиномов Ньютона, которые переводятся в форму алгебраических полиномов с числовыми коэффициентами; за счет вариации степени это позволяет повысить точность и качество визуализации, вычислять производные различных порядков, строить касательные и нормали в произвольной точке пути, вести обработку данных с малой временной сложностью инвариантно относительно выбора участка пути (С. 31 - 49).

5. Разработан метод, синтезирован и программно реализован алгоритм построения и визуализации касательных и нормалей, расположенных по одну сторону от фрагмента параметрически заданной кривой, отличающийся от известных реализацией на основе кусочно-полиномиальной аппроксимации фрагмента с помощью интерполяционных полиномов Ньютона в алгебраической форме с числовыми коэффициентами, что позволяет синтезировать и программно реализовать алгоритм расчета и визуализации контура участка железнодорожного пути, заданного массивом координат (С. 51 - 72).

6. Предложен метод и синтезирован алгоритм автоматического поиска граничных отрезков кривых, заданных последовательностями координат спутниковой фотосъемки, отличающийся от известных по алгоритмической структуре и позволяющий для контейнера граничных отрезков кривых синтезировать и программно реализовать алгоритм расчета и визуализации узловых точек полосы отвода (Стр. 73 - 98).

7. На основе предложенного поиска граничных отрезков кривых и расчета узловых точек полосы отвода синтезирован и программно реализован алгоритм построения и визуализации буферной зоны сложных объектов на примере полосы отвода схемы станции. Алгоритм отличается от известных по структуре и инвариантностью построения буферизации (С. 101 - 111).

Основные положения, выносимые на защиту

1. Метод, синтез и программная реализация алгоритма визуализации с высокой точностью железнодорожного пути, заданного массивом координат

спутниковой фотосъемки, на основе кусочно-полиномиальной аппроксимации линии пути интерполяционными полиномами Ньютона.

2. Метод, синтез и программная реализация алгоритма построения и визуализации касательных и нормалей, расположенных по одну сторону от фрагмента параметрически заданной кривой, со свойством инвариантности относительно выбора фрагмента, с целью расчета и визуализации контура участка железнодорожного пути, представленного массивом координат.

3. Метод, синтез и реализация алгоритма автоматического поиска граничных отрезков кривых, заданных последовательностями координат спутниковой фотосъемки, алгоритм расчета и визуализации узловых точек контура для контейнера граничных отрезков кривых.

4. Синтез и программная реализация алгоритма построения и визуализации контура сложных объектов на примере полосы отвода схемы станции со свойством инвариантности построения буферизации.

Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и программно реализованных алгоритмов визуализации линии железнодорожного пути, построения полосы отвода схем станций на основе кусочно-полиномиальной аппроксимации линии пути при помощи интерполяционных полиномов Ньютона. На основе предложенных методов и алгоритмов разработано программное обеспечение, проведены программные и численные эксперименты, подтверждающие достоверность разработанного анализа данных спутниковой фотосъемки, позволяющие на этой основе автоматизировать обработку и визуализацию спутниковых данных. Получено свидетельство об официальной регистрации программ для ЭВМ (№ 2014610821). Результаты диссертационного исследования могут быть использованы в качестве инструмента визуализации с высокой точностью дискретных объектов и инструмента построения буферных зон фигур, характеризующихся геометрической сложностью, в графических редакторах и ГИС-системах.

Внедрение и использование результатов работы. Полученные в работе результаты использованы:

1. В ОАО «НИИАС» приняты к использованию: метод и алгоритм визуализации железнодорожного пути, заданного массивом координат спутниковой фотосъемки, с высокой точностью и качеством визуализации с помощью кусочно-полиномиальной аппроксимации линии пути на основе интерполяционных полиномов Ньютона; алгоритм построения и визуализации полосы отвода схем станций на основе методов автоматического поиска граничных отрезков кривых и расчета для них узловых точек полосы отвода.

2. В учебном процессе кафедры информатики Таганрогского института имени А.П. Чехова (филиал) «Ростовского государственного экономического университета (РИНХ)» в курсах «Численные методы», читаемые на факультете физики, математики и информатики, «Методы численного анализа и вычислительной и линейной алгебры» читаемой в магистратуре по направлению подготовки «Прикладная информатика» магистральная программа «Информационные системы в менеджменте», «Дополнительные главы по курсу объектно-ориентированное

программирование» читаемому по направлению подготовки педагогического образования профиль информатика.

Апробация работы. Основные результаты работы докладывались на Всероссийской научной конференции «Техническая кибернетика, Радиоэлектроника и системы управления» (2008, Таганрог); 12-м Всероссийском симпозиуме по промышленной и прикладной математике (2011, Москва); Международной научно-практической конференции «Актуальные вопросы развития науки» (2014, Уфа); 15-м Всероссийском симпозиуме по промышленной и прикладной математике (2014, Москва); V Международной научной конференции «Наука в современном обществе» (2014, Ставрополь).

Публикации. По материалам диссертационной работы опубликовано 11 печатных работ общим объемом около 10 печатных листов, в том числе 2 статьи в реферируемых журналах из списка ВАК, свидетельство об официальной регистрации программ для ЭВМ (№ 2014610821).

Структура и объём работы. Диссертационная работа состоит из введения, трех глав основного раздела, заключения, списка литературы и двух приложений. Основное содержание работы изложено на 127 страницах, включая список литературы из 122 наименований; приложения содержат 33 страницы, на которых приводятся текст программы для ЭВМ, акты об использовании результатов диссертационной работы, свидетельство о государственной регистрации программ для ЭВМ.

Построение интерполяционного полинома

Алгоритмы построения буферных зон могут быть разбиты на две группы: растровые алгоритмы [90, 119] и векторные алгоритмы [97, 113]. Основное отличие между группами состоит в том, что первые расширяют объекты в растре, записывая новую границу, в то время как вторые строят двойные параллельные линии и дуги окружности вокруг объектов, а затем разглаживает их границы. В своей статье [109] Wang et al провели подробный анализ существующих алгоритмов построения буферных зон и описали их характеристики, применимость, сложность и множество других аспектов.

Растровые алгоритмы проще векторных в реализации. В основе ранних растровых алгоритмов лежало первичное расширение и размытие, определенное в теории математической морфологии [93], которое могло объяснить, как пиксели увеличиваются в объеме [121]. Растровые алгоритмы расширяют точки растра, линии, дуги в нужную ячейку на требуемом расстоянии и затем определяют их границы для расчета буферной зоны. В этом случае точность отображения буферной зоны связана с разрешением изображения, которое измеряется его размерами. Однако высокое разрешение растра требует слишком больших затрат ресурсов памяти. Отсюда вытекает необходимость поиска компромисса между скоростью обработки изображения и его разрешением. Для векторных алгоритмов проблема точности расчетов и отображения решается проще, однако они являются более сложными, поскольку связаны с решением задач пересечения кривых, разбиением арок на сегменты, установлением правил соответствия и т.д. Векторный алгоритм состоит из 3 шагов: прорисовка параллельной линии для каждого линейного сегмента, сглаживание переходных кривых и решение задачи объединения и пересечения многоугольников [105, 99]. Для оптимизации второго и третьего шага предложено большое количество стратегий. Например, Elber et al [75] сравнивают отклонение методов аппроксимации кривых, Er et al [76] предлагают использовать алгоритм визуализации коридора с изменяемой длиной ширины буфера. Wolff et al [115] создали алгоритм для подсчета криволинейных образцов с временной сложностью 0(_п2, где п количество точек полилиний. Ren et al в своей работе [102] предложили использовать алгоритм Дугласа-Пекера [74, 84] для удаления нехарактерных точек на кривых и выделения характерных. В [94, ПО] предложен метод буферизации на основе трассировки векторных границ, который позволяет избежать сложных векторных вычислений, сохраняя при этом точность существующих векторных алгоритмов. Развитие параллельных вычислений способствовало появлению параллельных алгоритмов расчета [69, 89, 118, 101] и визуализации [106] буферных зон. Рассмотрим подробнее некоторые алгоритмы построения буферных зон. Алгоритм преобразования Евклидового расстояния на растре [109]. Алгоритм представляет собой разновидность методов анализа расстояния на растровых данных. Подробное описание алгоритма дается в [93, 81]. Для реализации данного алгоритма требуется по меньшей мере три двумерных массива, два из которых целочисленные (компоненты расстояния в направлении X и Y), а третий – вещественный (значения расстояний). Первая строка массива расстояний, заполняется нулями, остальные отмечаются равными бесконечности. После установки начальных значений расстояние от любого слоя карты до растрового объекта может быть получено с помощью двух итераций процедуры, аналогичной алгоритму Дейкстры [6, 27] (классическому алгоритму нахождения кратчайшего пути в графе). Затем с помощью сравнения заранее определенного расстояния с расчетным в каждом узле заполняется вся сетка буферной зоны. Полученная таким образом буферная зона может быть использована далее для расчета буферной зоны с другим буферным расстоянием, что особенно ценно при решении задач динамического буферного анализа [91, 98].

Алгоритм параллельных двойных линий [109]. Это один из простейших векторных алгоритмов построения буферной зоны, который имеет два варианта применения: метод биссектрисы угла и метод выпуклой дуги. Метод биссектрисы состоит из трех шагов: построение параллельных линий для каждого отрезка прямой (рис. 13), сглаживание точек пересечения кривых и процесс самопересечения [83]. Однако данный метод сложен в реализации, поскольку алгоритм не гарантирует равную ширину параллельных двойных линий, а также имеет множество других проблем. Рис. 13 Метод биссектрисы угла

Основная идея метода выпуклой дуги состоит в следующем (рис. 14): сначала определить выпуклость и вогнутость каждой экстремальной точки кривой, затем с выпуклой стороны соединить границы буфера с помощью дугового сегмента, радиус которого равен расстоянию буфера, после чего на вогнутой стороне построить две линии параллельные граничным линейным сегментам, и найти их точку пересечения – соответствующую вершину; Затем, соединив дуговой сегмент и параллельные линии в соответствующем порядке, сформировать закрытую границу буфера.

Метод выпуклой дуги может допускать некоторое искажение границы буфера в силу острых углов и иных причин. Эти искажения классифицированы по трем группам (16 типов) Gong J.H. et al провели работу по устранению недостатков в каждом из случаев [96]. На базе метода выпуклой дуги в статье [67] предлагается метод вращения радиуса, основанный на векторных операциях, которые упрощают процесс получения параллельных линий и сглаживания острого угла. Статья [73] излагает полную реализацию алгоритма выпуклой дуги для простой линейной структуры, который с помощью непосредственного вычисления решает задачу самопересечения границы полигона. Вычислительная сложность алгоритма (количество элементарных операций, затрачиваемых алгоритмом для решения конкретной задачи) [49, 86, 1] – O(n2 ).

Алгоритм простых перекрытий [109]. Данный тип алгоритмов строит буферную зону как объединение буферных зон основных графических элементов (точек, линий). Одна из основных проблем метода – объединение двух буферных зон с помощью операции пересечения нескольких полигонов. Сначала был предложен алгоритм непосредственных наложений, но в виду его большой вычислительной сложности разработано большое количество способов его оптимизации. Например, метод нарастающей буферной зоны основан на динамическом наложении [108]. Sun et al [107] проанализировали расположения дуг на вершинах после пересечения границ буферных полигонов и разработали правило их принадлежности итоговой буферной зоне.

Рассмотрим сначала алгоритм непосредственного наложения буферных зон. Единичная буферная зона каждого линейного сегмента – это простой капсульный полигон. Сначала получаем буферную зоны для каждого линейного сегмента в отдельности, затем объединяем их, используя алгоритм наложения полигонов (рис. 15). По мнению Guo [82], данный алгоритм аналогичен алгоритму топологического построения буфера.

Определение уравнения нормали в выбранной точке, расчет точек, отстоящих от кривой на заданную длину отрезка

Как видно из таблицы предложенный метод кусочно-полиномиальной аппроксимации на основе интерполяционных полиномов Ньютона (с переводом в форму алгебраических полиномов) обеспечивает более высокую точность по сравнению с классическими интерполяционными полиномами Ньютона, Лагранжа, B-сплайном и кривой Безье.

Также следует отметить, что аппроксимирующий полином по методу B сплайна имеет большую степень по сравнению с полиномом Ньютона в методе кусочно-полиномиальной аппроксимации для визуализации одной и той же кривой [20]. Следовательно, аппроксимация по методу B-сплайнов имеет большую временную сложность по сравнению кусочно полиномиальной аппроксимацией. Автоматическая обработка кривой Безье имеет большую временную сложность, по сравнению с полиномом Ньютона в методе кусочно-полиномиальной аппроксимации [61].

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

Постановка вопроса. Как отмечено во введении, диссертационная работа посвящена расчету и визуализации железнодорожных путей, заданных оцифрованным массивом координат спутниковой съемки, и их полосы отвода. В главе 1 при помощи кусочно-полиномиальной аппроксимации на основе полинома Ньютона разработан алгоритм визуализации путей. Используя результаты первой главы, требуется разработать метод построения и визуализации полосы отвода аппроксимированных путей. То есть необходимо рассчитать геометрическое место точек, равноудаленных от границ путей на величину коэффициента безопасности.

Для расчета координат полосы отвода требуется синтезировать алгоритм построения и визуализации нормали и касательной в произвольной точке аппроксимированных путей. При этом все нормали должны располагаться по одну сторону от пути. Это даст возможность для каждой точки рассчитать соответствующую координату полосы отвода.

Из каждой точки на кривой можно провести две нормали (внутреннюю и внешнюю) и касательную (различается направление вперёд и назад в порядке обхода кривой). Для построения полосы отвода необходимо строить нормали одностороннего направления по отношению к кривой. Это связано с тем, что полоса отвода строится по одну и по другую сторону одновременно для группы рядом расположенных путей, например, если эти пути образуют двухстороннюю колею. С этой целью фиксируется длина отрезка нормали и выполняется его визуализация только с одной стороны линии полотна.

Формальный алгоритм построения нормали и касательной можно представить следующим образом. Шаг 1. Выбор точки построения нормали и касательной на визуализированной кривой пути.

В главе 1 для визуализации исходной дискретной параметрической функции у(х) = y(x(t)) = y(t), где 0 ґ 1 предложена кусочно-полиномиальная аппроксимация на основе интерполяционных полиномов Ньютона, обладающая высокой точностью приближения исходной функции (гл. 1 параграф 1.3). Данный метод позволяет рассматривать функции абсциссы и ординаты на каждом из отрезков как полиномы, зависящие от параметра t. То есть, для произвольно выбранного отрезка можно записать, что x(i) a0 +a1t + ... + antn, y(t)&b0+bj + ... + bjm, где n,m - степени соответствующих полиномов, а., 0 г п; Ъ}., 0 j т - коэффициенты. Из формул (2.2) и (2.3) следует, что первая и вторая производная исходной параметрической функции у(х) существует на всей области определения за исключением точек [26], в которых функция xt обращается в ноль. Такие точки называются особыми. В особых точках построение нормали и касательной не выполняются.

Расчет координат землеотвода по найденному контейнеру отрезков прямых

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

На вход метода поступает массив координат отрезков прямых (дискретизированных), определяющих пути железнодорожной станции (для краткости станции).

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

Для описания метода и последующей формализации алгоритма вводятся дополнительные определения. Контейнер граничных отрезков прямых – контейнер данных, в который сохраняются искомые упорядоченные отрезки прямых.

Текущий отрезок прямой – последний отрезок прямой в контейнере граничных отрезков прямых. Относительно него ищутся следующие граничные отрезки прямой.

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

Далее происходит фильтрация отрезков прямых по следующему принципу. Из массива отрезков прямых, определяющих пути станции, выбираются два отрезка прямых, такие что проекции первого и текущего отрезков на ось OX касаются (пример на рис. 3.5), при этом текущий отрезок прямой находится ниже для обхода по верху землеотвода (выше для обхода по низу землеотвода); а проекции второго и текущего отрезков на ось OX пересекаются (пример на рис. 3.6), при этом текущий отрезок прямой находится ниже для обхода по верху землеотвода (выше для обхода по низу землеотвода). Рис. 3.6 Случай выбора второго отрезка

Если рассматриваемая пара отрезков выбрана, то из них в качестве следующего выбирается тот, у которого минимальная абсцисса меньше. Выбранный в этом качестве отрезок прямой на следующем шаге становится текущим. Если в рассматриваемых условиях данный выбор не выполнен, то ищется отрезок прямой, имеющий в качестве граничной точки незадействованную граничную точку текущего отрезка прямой. Если в результате этого шага следующий отрезок прямой не был найден, то для поиска следующего отрезка прямой от точки с максимальным значением абсциссы текущего отрезка выполняется отступ вправо на два пикселя и проводится вертикальный луч вниз для обхода по верху землеотвода (вверх для обхода по низу землеотвода). Пересечение искомого отрезка прямой с вертикальным лучом (вида х = т) определяется, тем, что т является абсциссой какой-либо его точки. Из всех таких отрезков выбирается тот отрезок прямой, у которого наименьшее (для обхода по низу землеотвода) или наибольшее (для обхода по верху землеотвода) значение ординаты точки пересечения. Пример на рис. 3.7.

Оценка временной сложности алгоритма построения землеотвода

Определим оценку алгоритма расчета координат землеотвода по найденному контейнеру отрезков прямых, формальное описание которого приведено на с. 97 - 99. Будем считать, что контейнер состоит не более чем из п элементов, к каждому из которых применяется алгоритм расчета. Алгоритм состоит из десяти шагов, на каждом из которых выполняется конечное число операций, не зависящих от числа п элементов в контейнере. Таким образом, временная сложность алгоритма, примененного к одному элементу контейнера, - 0(1), а ко всем - 0{п). Следовательно, временная сложность алгоритма расчета координат землеотвода по найденному контейнеру отрезков прямых - 0(п).

На основании оценок временной сложности приведенных алгоритмов можно сказать, что временная сложность алгоритма построения землеотвода составляет Т(п) = 0(п2) + 0(п) = 0(п2).

Далее приводится итог построения и визуализации полосы отвода станций Таганрогской дистанции пути, схемы и данные которых поступают в программу, реализованную согласно структурной схеме из рис. 3.22, из файла формата .txt (как описано [58, 42]).

На рис. 3.24 представлено построение и визуализация полосы отвода схемы станции, образованной пятью путями и шестью съездами. Графически схема представляет объединение трех полигональных объектов и одного линейного. Разница в расстоянии между горизонтальными и наклонными участками полосы отвода и соответствующими граничными отрезками станции, возникающая в процессе визуализации, является исключительно погрешностью масштабирования. В свою очередь масштабирование предпринято единственно с целью размещения рисунка в формате A4.

Граница полосы отвода в нижней части рис. 3.24 отстоит от соответствующего граничного отрезка станции на величину, превышающую значение коэффициента безопасности. Такое превышение обусловлено необходимостью унификации алгоритма для обработки участков границ станции с рис. 3.24 и 3.26, представляющих собой случаи А и Б с рис. 3.25.

Далее визуализируется схема станции, графически представляющая собой набор полигонов, незамкнутых объектов и путей (рис. 3.26). Рис. 3.26 Визуализация схемы станции Таганрог -1 и ее землеотвода В главе 1 представлен метод и синтезирован алгоритм построения и визуализации участка железнодорожного пути, заданного своими координатами, при помощи кусочно-полиномиальной аппроксимации на основе полинома Ньютона, во второй главе разработаны алгоритм построения нормалей и касательных по одну сторону от кривой и алгоритм визуализации полосы отвода железнодорожного пути (путей перегонов). В третьей главе предложен метод и синтезирован алгоритм расчета и визуализации полосы отвода схем станций. Таким образом, объединение результатов глав диссертации дает возможность визуализировать станцию с участком путей перегона (рис. 3.26).

Как видно из приведенных выше примеров, предложенные в работе алгоритмы (освященные так же в [59, 60]) позволяют строить и визуализировать буферные зоны вокруг незамкнутых объектов сложной формы. Ниже представлено сравнение предложенного подхода с существующими аналогами. Во введении представлен обзор основных методов и алгоритмов буферизации, таких как алгоритм параллельных двойных линий [83], алгоритм простых перекрытий [108], метод динамического наращивания . Данные методы позволяют строить буферную зону для точечных, линейных и простейших полигональных объектов [109]. Схема станции представляет собой набор полигонов, незамкнутых объектов и путей. Применение указанных методов для расчета ее полосы отвода невозможно, так как они не позволяют вычислить внешнюю границу рассматриваемого объекта [109]. Так, алгоритм параллельных двойных линий [83] предполагает построение параллельных линий для каждого отрезка прямой [109], что в случае рассматриваемой задачи означает построение избыточного количества линий, не позволяющих построить искомый объект. Метод непосредственного наложения буферных зон [82] предлагает строить буферную зону для каждого линейного отрезка в отдельности. Результирующая буферная зона объекта рассчитывается как результат объединения буферных зон отрезков. В результате применение данного метода к решению рассматриваемой в главе задачи не позволит правильно рассчитать искомый объект из-за большого количества лишних построений. Метод динамического наращивания [108] предполагает сначала построение буферного полигона для первого и второго линейного сегмента, затем с помощью операции пересечения полигонов строится их буферная зона, которая пересекается с буферным полигоном третьего линейного сегмента и т.д. Как и в случае алгоритма параллельных двойных линий, результирующий объект будет содержать большое количество лишних буферных полигональных объектов. Таким образом, существующие алгоритмы построения буферной зоны не вполне подходят для решения задачи расчета и построения полосы отвода вокруг схем станций, поскольку не вычисляют внешнюю границу рассматриваемого объекта и не исключают из рассмотрения линейные сегменты, которые заведомо не участвуют в формировании буферной зоны. Согласно замечанию доктора Jiechen Wang из Geographic Information Science Department, Nanjing University, Nanjing, China, предложенный в диссертации метод возможно сравнить с методами, используемыми в современных ГИС-системах, например, ArcGis, ObjectLand.

Исходя из описания их возможностей, указанных в руководстве пользователя [51,18], можно утверждать, что заложенные в них алгоритмы буферизации также не могут позволить построить полосу отвода вокруг схемы станции.

В частности, в руководстве пользователя ГИС ObjectLand [18] в главе 18 «Вспомогательные операции редактирования» в разделе «Построение буферной зоны объектов» указано, что ГИС может строить буферную зону для точечных, линейных и площадных объектов. ГИС позволяет также создавать буферную зону для выделенной совокупности объектов, но построение выполняется для каждого из объектов в отдельности. Буферная зона совокупности объектов получается объединением буферных зон отдельных объектов. Аналогичный функционал описан в руководстве пользователя ГИС ArcGIS [51] в разделе Buffer главы Proximity toolset. Данные инструменты не позволяют решить задачу расчета и визуализации полосы отвода схем станций из-за построения лишних буферных объектов.

Следует отметить, что оценка временной сложности разработанного алгоритма построения полосы отвода составляет O(n2 ) (см. (3.6)), что в некоторых случаях превышает временную сложность алгоритмов расчета буферных зон [109], наилучшая из которых – O(nlogn) [109]. Однако, как было отмечено выше, существующие алгоритмы не решают задачу вычисления внешней границы сложного незамкнутого объекта и не исключают из рассмотрения линейные сегменты, которые заведомо не участвуют в формировании буферной зоны. Поэтому они не вполне подходят для решения задачи построения полосы отвода схем стаций. Предложенный в работе метод и алгоритм являются более универсальными по сравнению с существующими, но отличается от них сравнительно высокой временной сложностью.