Содержание к диссертации
Введение
ГЛАВА 1. Разработка алгоритма и методики построения условной развертки отсека топографической поверхности между двумя заданными точками 13
1.1. Разбиение топографической поверхности на треугольные ячейки 15
1.2. Построение развертки соседней пары треугольных ячеек 16
1.3. Выбор направления пути для построения условной развертки части топографической поверхности 20
1.4. Последовательное построение условной развертки части топографической поверхности по заданному пути 29
1.5. Алгоритм построения условной развертки части топографической поверхности по заданному пути. Численный пример 39
1.6. Перенос заданных точек на условную развертку 44
1.7. Выводы 47
ГЛАВА 2. Разработка алгоритма построения и методики поиска квазигеодезической линии на топографической поверхности 50
2.1. Алгоритм построения квазигеодезической линии между двумя заданными точками на топографической поверхности по ее условной развертке 50
2.2. Определение принадлежности отрезка прямой, соединяющей две заданные точки, построенной на развертке 51
2.3. Корректировка пути построения условной развертки между двумя точками на топографической поверхности 56
2.4. Перенос на топографическую поверхность квазигеодезической линии между двумя заданными точками А и В, найденной на условной развертке 75
2.5. Выводы 88
ГЛАВА 3. Алгоритм решения задачи штейнера на топографической поверхности, применительно к прокладке трубопроводов 4
3.1. Построение кратчайших линий, соединяющих заданные точки на плоскости 90
3.2. Построение квазигеодезической линии, соединяющей три заданные точки на топографической поверхности 100
3.3. Построение квазигеодезической линии, соединяющей заданных точек на топографической поверхности 114
3.3. Выводы 118
Заключение ...119
Список литературы 121
Приложения 130
- Выбор направления пути для построения условной развертки части топографической поверхности
- Алгоритм построения условной развертки части топографической поверхности по заданному пути. Численный пример
- Определение принадлежности отрезка прямой, соединяющей две заданные точки, построенной на развертке
- Построение квазигеодезической линии, соединяющей три заданные точки на топографической поверхности
Введение к работе
Проблема исследования и ее актуальность. Республика Казахстан обладает большими запасами углеводородного сырья. Экономическое развитие республики непосредственно связанно со степенью развития нефте-и газодобывающих отраслей. В виду географической отдаленности от мировых потребителей углеводородного сырья, а также в связи с большими расстояниями между месторождениями внутри территории Казахстана, предстоит освоить большой объем строительства нефте- и газопроводов.
Стоимость строительства и эксплуатации трубопроводов высока, поэтому возникает потребность в поиске путей по снижению их себестоимости. Одним из важных путей решения этой задачи является поиск методов и алгоритмов оптимального моделирования конфигурации инженерных сетей.
Для транспортировки нефти и газа из отдельных скважин в пункты сбора
и хранения сооружают промысловые трубопроводы, по которым
энергоносители поступают в магистральные трубопроводы. Конфигурацию
промысловых трубопроводов можно моделировать с помощью теории
графов. Здесь скважины, пункты сбора и хранения являются вершинами, а
соединяющие их трубопроводы — ветвями моделирующего графа. Исходной
информацией для составления моделирующего графа является расположение
промысловых скважин, представляющих собой неподвижные вершины
искомого графа. Расположения пунктов сбора и хранения должны быть
рациональными в экономическом отношении и удобными для
эксплуатации. Следовательно, вершины моделирующего графа,
соответствующие пунктам сбора и хранения, являются подвижными и подлежат определению. Кроме того, необходимо определить ветви графа,
т.е. найти оптимальную трассу, соединяющую каждую скважину с пунктом сбора или хранения нефти.
Общим критерием оптимизации практически для всех транспортных сетей является поиск минимального дерева, связывающего заданные точки. Если при такой оптимизации допускается добавление новых точек, то такая задача известна, как задача по построению кратчайшего дерева Штейнера (далее КДШ) для заданных точек [6, 8, 28, 40, 51, 52, 55, 64, 135].
Поиск КДШ для точек, заданных на плоскости, относится к разряду сложных задач. При большом числе заданных узлов применение алгоритма прямого перебора становится практически невозможным из-за резкого роста объема вычислений. Поэтому были разработаны специальные алгоритмы для избежания прямого перебора вариантов [9, 12, 13, 14, 20, 29, 33, 34, 39, 48 ,73, 89,96, 100, 105, 114, 120, 122, 123, 124, 127, 128].
Реальная гористая местность сильно отличается от ее плоскостной модели. Здесь задача поиска КДШ еще более усложняется. Известные алгоритмы по построению КДШ для топографической поверхности [2, 21, 35, 37, 38, 41, 45, 47, 50, 53, 61, 69, 75, 79, 90] практически не используют накопленную богатейшую методическую и алгоритмическую базу для поиска КДШ на плоскости. Это обстоятельство делает невозможным разработку универсального способа решения задач для любой местности, состоящей из сильно пересеченных и относительно ровных участков.
Вышеизложенные факты показывают актуальность проблемы исследований, посвященных разработке новых и эффективных алгоритмов и методов построения оптимальной конфигурации инженерных сетей.
Анализ методов геометрического моделирования конфигураций инженерных сетей. Выделим несколько основных критериев для оптимизации конфигурации инженерных сетей. Это объем строительно-монтажных работ, ресурсоемкость, трудоемкость, сроки строительства,
эксплуатационные расходы, транспортные расходы и т. д. Все вышеприведенные затраты имеют, в основном, линейную зависимость от протяженности инженерных сетей.
Поиск конфигурации инженерной сети наименьшей протяжённости можно свести к следующей геометрической задаче: построить связывающую линию для некоторого множества точек в пространстве Е3, имеющую кратчайшую длину. Эту задачу называют проблемой Штейнера [3, 4, 44, 58, 59, 67, 78, 86, ПО, 118, 121, 125, 130, 134].
Проблемой Штейнера занимались многие известные ученые. Так, например, Торричели и Ферма установили, что в общем случае, кратчайшая сеть для трех точек будет найдена введением еще одной точки [1, 17, 54, 65]. При этом ребра, соединяющие дополнительную точку с вершинами треугольника, сходятся под углами в 120. Так же решением проблемы Штейнера занимались ученые Р. Курант [26, 27, 30, 57, 119] и В.М.Прокофьев [31, 36, 83, 84, 85], которые установили, что линия кратчайшей длины на плоскости состоит из отрезков прямых и имеет вершины трёх типов. Первый тип - это тупик, т.е. вершина инцидентная только одному отрезку. Второй тип - это колено, т.е. вершина инцидентная двум отрезкам, сходящимся под углом не менее 120. И третий тип - это узел, т.е. вершина инцидентная трём отрезкам, сходящимися под углами в 120.
Известный советский ученый Н. Ф. Четверухин [108, 109] предложил
оригинальный метод мыльной пленки, основанный на физическом явлении
поверхностного натяжения жидкости. В этой модели имеются две
прозрачные параллельные пластины. Положения вершин Аь А2,..., Ап
фиксируются тонкими стержнями-отрезками перпендикулярными
пластинам, концы которых жестко закреплены в них. Полученная таким образом конструкция погружается в мыльный раствор. После извлечения конструкции из раствора образуется мыльная плёнка между стержнями.
Под воздействием физического эффекта поверхностного натяжения мыльная плёнка может находиться только в состоянии устойчивого равновесия, когда общая площадь образуемой ею поверхности минимальна (изопериметрическая задача). Проекция мыльной пленки на пластины является решением проблемы Штейнера для п фиксированных точек.
Существуют и другие физические модели для поиска кратчайшей сети Штейнера. Но физические модели, хотя и доказывают существование кратчайших связывающих линий, но не дают конкретных геометрических алгоритмов для их расчетов на компьютерах.
Полным перебором всех возможных вариантов для п узлов плоскости можно решить задачу построения кратчайшей сети между заданными точками. Это доказал Мельзак в работе [111, 133]. По этой схеме пытались решить проблему Штейнера в работах [126, 129, 131, 132]. Резкий рост объемов вычислений при большом количестве узлов делает невозможным решение задачи даже с применением современных мощных ЭВМ.
Поэтому необходимы методы, значительно уменьшающие количество вариантов, подлежащих перебору. В работах [25, 32, 95, 111, 134] предложены фильтры, отсеивающие некорректные варианты по установленным геометрическим признакам. Таким образом, усовершенствованный алгоритм Мельзака может обрабатывать сети только для п<\5. На основе изопериметрической задачи в работе [117] предложен алгоритм построения кратчайшей сети для я<30. Более эффективные алгоритмы для решения проблемы Штейнера были получены на базе теории графов [14, 15, 60, 82, 88, 107].
Приложения проблемы Штейнера для конкретных примеров накладывают дополнительные условия, например, задача построения сети минимальной стоимости. Так же имеются приложения по отраслям. В работах [40, 51, 55, 99] исследуется проблема Штейнера для прокладки линий электропередачи, в работах [61, 106, 111] для автомобильных дорог
и в [5, 7, 11, 46, 70, 81, 101] для магистральных нефте- и газопроводов.
Во всех этих работах общая геометрическая задача обычно решается поэтапно через пошаговое приближение к оптимальному результату. Так, сначала определяется кратчайшая сеть Прима [83] для заданных п точек. На следующем этапе добавляются дополнительные точки, т.е. находится кратчайшая сеть Штейнера.
В реальных условиях на прокладку инженерных сетей накладываются различные запреты и ограничения. Например, если на определенном участке трубопровода, дороги или линии электропередачи встречаются естественные препятствия в виде гор, рек или плохих грунтов, то возникает необходимость в обходе этих, так называемых, карстовых областей [10, 35].
Как было отмечено выше, реальная местность сильно отличается от плоскостной модели и поэтому актуально решение проблемы Штейнера и в других пространственных моделях. В работе [74] была рассмотрена задача построения кратчайшей связывающей сети на поверхности сферы и предложен алгоритм. Для многомерного пространства свойства кратчайших связывающих сетей рассматривались в работах [16, 23, 29, 102]. Для произвольной поверхности задача нахождения кратчайшей линии рассматривалась в работах [49, 62, 63].
С использованием ортогональной метрики решались задачи нахождения кратчайших транспортных сетей внутри городских кварталов или внутри заводских цехов, а также для транспортировки грузов внутри складов. Здесь транспортные линии могут быть выбраны только параллельно осям прямоугольной системы координат. Аналогичная задача возникает также при трассировке соединений на печатных платах [10, 14,15, 30, 31, 32, 60, 113].
Большую практическую ценность имеют решения проблемы Штейнера
на реальной топографической поверхности. Впервые задачу построения
геодезической линии на топографической поверхности поставил
Н.А.Глаголев [21, 22]. Профессором Н.Н.Рыжовым рассматривалась задача по построению геодезической линии в заданном направлении на топографической поверхности [90]. Приближенный способ построения кратчайшей линии с использованием свойств нормальных сечений рассматриваются в работах [49, 75, 97]. В вышеупомянутых работах рассматривались кратчайшие соединения для двух точек, лежащих на топографической поверхности. Поэтому не представляется возможным использовать их для построения кратчайшей линии, связывающей заданное множество из п точек на топографической поверхности.
Более приемлемым, с целью автоматизации, является цифровое моделирование топографической поверхности [35, 41, 45, 63, 71, 79] и использование волнового алгоритма Ли [42, 43]. Таким образом, созданные методики для построения кратчайших сетей, связывающих заданное множество точек на топографической поверхности, могут быть использованы в системах автоматизированного проектирования.
Необходимо отметить, что методики на основе волнового алгоритма Ли имеют существенный недостаток в выборе дискретного набора возможных направлений, что может привести к сильным искажениям и, как следствие, неоптимальным решениям.
Большое количество работ, посвященных нахождению оптимальной конфигурации инженерных сетей, также свидетельствует об актуальности и практической значимости наших исследований.
Постановка задач. В результате анализа отечественных и зарубежных работ выявлено, что достаточно эффективной и универсальной методики определения оптимальной конфигурации инженерных сетей, в частности трубопроводов, не разработано. Известные методы и алгоритмы приводят к существенным искажениям в результатах, так как они используют пространственные модели, не соответствующие реальным условиям на местности.
Но в то же время известен хороший способ построения кратчайших связывающих линий на торсовой поверхности, когда используется ее развертка. Аналогично можно использовать этот подход для более сложных поверхностей таких, как топографическая поверхность. Но работы в этом направлении практически не велись из-за сложности построения развертки топографической поверхности.
Использование разверток топографических поверхностей для решения проблемы Штейнера, кроме повышенной точности результатов, позволяет использовать всю накопленную богатейшую базу методов и алгоритмов решения проблемы Штейнера на плоскости.
Цель работы. Разработка метода, методик и алгоритмов по определению рациональной трассы разветвленных инженерных сетей, в частности трубопроводов, проектируемых на реальной местности и приводящей к снижению строительно-монтажных, а также эксплуатационно-транспортных расходов.
В связи с этим в диссертации решаются следующие основные задачи:
— разработать геометрические модели реальных топографических
поверхностей, которые позволяют легко вводить в компьютер
исчерпывающую информацию об особенностях данной местности;
разработать алгоритмы и методику построения условной развертки отсека топографической поверхности по выбранному направлению;
разработать методы и алгоритмы определения квазигеодезической линии, соединяющей заданные точки, топографической поверхности;
разработать методы и алгоритмы поиска кратчайшего дерева на топографической поверхности, связывающего три и более точек с добавлением точек Штейнера;
создать программное обеспечение разработанных моделей, методов и алгоритмов по построению развертки отсека поверхности, определению квазигеодезических и поиска кратчайших связывающих линий на
топографической поверхности, моделирующих оптимальную конфигурацию инженерных сетей.
Методика исследования. Поставленные в работе задачи решались методами аналитической, начертательной, вычислительной и комбинаторной геометрии, теории графов, теории оптимизации, технико-экономического анализа и программирования.
Теоретической базой проведенных исследований явились работы ведущих ученых:
— по теории геометрического моделирования: Бусыгина В. А.,
Волкова В. Я., Иванова Г. С, КотоваИ. И., Михайленко В. Е., Наджарова
К. М., Нурмаханова Б., Осипова В. А., Тевлина А. М., Тузова А. Д.,
Фролова С. А., Якунина В. И. и многих других;
— по геометрии связывающих линий: Глаголева Н. А., Есмуханова
Ж. М., Калинина В. А., Кельманса А. К., Куранта Р., Мельзака Ю. Г.,
Мульдекова И. О., Рыжова Н. Н., Четверухина Н. Ф., Штейнера Я. и других.
Научную новизну диссертационной работы составляют следующие результаты:
— геометрические алгоритмы и методика построения условной
развертки отсека топографической поверхности между двумя заданными
точками;
— геометрические алгоритмы и методы определения квазигеодезической
линии между двумя точками на топографической поверхности с
использованием условной развертки отсека топографической поверхности
между этими двумя точками;
— геометрические алгоритмы и методы обратного переноса на
поверхность кратчайшего расстояния, найденного на условной развертке
отсека топографической поверхности между двумя заданными точками;
— геометрические методы и алгоритмы поиска кратчайшего
связывающего дерева для трех и более точек на топографической
поверхности с использованием условной развертки отсека топографической поверхности;
— прикладные программы ModeBrez, Razvert, Poisk, Perenos, Steiner, RazVlas и RazVlasSt, которые позволяют построить условную развертку отсека топографической поверхности, определить квазигеодезическую линию между двумя точками и точки Штейнера, определить кратчайшие связывающие заданные точки деревья на топографической поверхности.
Апробация работы. Основные результаты диссертационной работы были доложены и обсуждены на:
Международной конференции «Молодые ученые — 10-летию независимости Казахстана», г. Алматы, 2001 г.;
Второй Международной научно-практической конференции молодых ученых, г. Алматы, 2002 г.,
Международной научно-практической конференции «Естественно-гуманитарные науки и их роль в подготовке инженерных кадров», г. Алматы, 2002 г.;
На научных семинарах и заседаниях кафедры начертательной геометрии и графики Казахского национального технического университета имени К. И. Сатпаева и кафедры прикладной геометрии Московского авиационного института (технического университета).
Публикации. По теме диссертации опубликовано 6 научных статей, в которых полно отражены теоретические и прикладные результаты проведенных исследований.
Выбор направления пути для построения условной развертки части топографической поверхности
Под воздействием физического эффекта поверхностного натяжения мыльная плёнка может находиться только в состоянии устойчивого равновесия, когда общая площадь образуемой ею поверхности минимальна (изопериметрическая задача). Проекция мыльной пленки на пластины является решением проблемы Штейнера для п фиксированных точек.
Существуют и другие физические модели для поиска кратчайшей сети Штейнера. Но физические модели, хотя и доказывают существование кратчайших связывающих линий, но не дают конкретных геометрических алгоритмов для их расчетов на компьютерах.
Полным перебором всех возможных вариантов для п узлов плоскости можно решить задачу построения кратчайшей сети между заданными точками. Это доказал Мельзак в работе [111, 133]. По этой схеме пытались решить проблему Штейнера в работах [126, 129, 131, 132]. Резкий рост объемов вычислений при большом количестве узлов делает невозможным решение задачи даже с применением современных мощных ЭВМ.
Поэтому необходимы методы, значительно уменьшающие количество вариантов, подлежащих перебору. В работах [25, 32, 95, 111, 134] предложены фильтры, отсеивающие некорректные варианты по установленным геометрическим признакам. Таким образом, усовершенствованный алгоритм Мельзака может обрабатывать сети только для п \5. На основе изопериметрической задачи в работе [117] предложен алгоритм построения кратчайшей сети для я 30. Более эффективные алгоритмы для решения проблемы Штейнера были получены на базе теории графов [14, 15, 60, 82, 88, 107].
Приложения проблемы Штейнера для конкретных примеров накладывают дополнительные условия, например, задача построения сети минимальной стоимости. Так же имеются приложения по отраслям. В работах [40, 51, 55, 99] исследуется проблема Штейнера для прокладки линий электропередачи, в работах [61, 106, 111] для автомобильных дорог и в [5, 7, 11, 46, 70, 81, 101] для магистральных нефте- и газопроводов.
Во всех этих работах общая геометрическая задача обычно решается поэтапно через пошаговое приближение к оптимальному результату. Так, сначала определяется кратчайшая сеть Прима [83] для заданных п точек. На следующем этапе добавляются дополнительные точки, т.е. находится кратчайшая сеть Штейнера.
В реальных условиях на прокладку инженерных сетей накладываются различные запреты и ограничения. Например, если на определенном участке трубопровода, дороги или линии электропередачи встречаются естественные препятствия в виде гор, рек или плохих грунтов, то возникает необходимость в обходе этих, так называемых, карстовых областей [10, 35].
Как было отмечено выше, реальная местность сильно отличается от плоскостной модели и поэтому актуально решение проблемы Штейнера и в других пространственных моделях. В работе [74] была рассмотрена задача построения кратчайшей связывающей сети на поверхности сферы и предложен алгоритм. Для многомерного пространства свойства кратчайших связывающих сетей рассматривались в работах [16, 23, 29, 102]. Для произвольной поверхности задача нахождения кратчайшей линии рассматривалась в работах [49, 62, 63].
С использованием ортогональной метрики решались задачи нахождения кратчайших транспортных сетей внутри городских кварталов или внутри заводских цехов, а также для транспортировки грузов внутри складов. Здесь транспортные линии могут быть выбраны только параллельно осям прямоугольной системы координат. Аналогичная задача возникает также при трассировке соединений на печатных платах [10, 14,15, 30, 31, 32, 60, 113].
Большую практическую ценность имеют решения проблемы Штейнера на реальной топографической поверхности. Впервые задачу построения геодезической линии на топографической поверхности поставил Н.А.Глаголев [21, 22]. Профессором Н.Н.Рыжовым рассматривалась задача по построению геодезической линии в заданном направлении на топографической поверхности [90]. Приближенный способ построения кратчайшей линии с использованием свойств нормальных сечений рассматриваются в работах [49, 75, 97]. В вышеупомянутых работах рассматривались кратчайшие соединения для двух точек, лежащих на топографической поверхности. Поэтому не представляется возможным использовать их для построения кратчайшей линии, связывающей заданное множество из п точек на топографической поверхности.
Более приемлемым, с целью автоматизации, является цифровое моделирование топографической поверхности [35, 41, 45, 63, 71, 79] и использование волнового алгоритма Ли [42, 43]. Таким образом, созданные методики для построения кратчайших сетей, связывающих заданное множество точек на топографической поверхности, могут быть использованы в системах автоматизированного проектирования.
Необходимо отметить, что методики на основе волнового алгоритма Ли имеют существенный недостаток в выборе дискретного набора возможных направлений, что может привести к сильным искажениям и, как следствие, неоптимальным решениям.
Большое количество работ, посвященных нахождению оптимальной конфигурации инженерных сетей, также свидетельствует об актуальности и практической значимости наших исследований.
Постановка задач. В результате анализа отечественных и зарубежных работ выявлено, что достаточно эффективной и универсальной методики определения оптимальной конфигурации инженерных сетей, в частности трубопроводов, не разработано. Известные методы и алгоритмы приводят к существенным искажениям в результатах, так как они используют пространственные модели, не соответствующие реальным условиям на местности.
Алгоритм построения условной развертки части топографической поверхности по заданному пути. Численный пример
Предлагаемый нами алгоритм состоит из следующей последовательности действий: 1. Строится первая условная развертка топографической поверхности между двумя заданными точками по методике, предложенной в первой главе. 2. Строится прямая, соединяющая две заданные точки. 3. Определяется: лежит ли эта прямая внутри построенной развертки? Если да, то работа алгоритма на этом этапе завершается, если же нет, то необходимо произвести корректировку пути построения развертки. 4. Вновь строится прямая, соединяющая две заданные точки. 5. Переход к выполнению шага 3. Завершение работы алгоритма приведет к построению такой условной развертки, у которой отрезок прямой, соединяющей две заданные точки, полностью лежит внутри построенной развертки. 2.2. Определение принадлежности отрезка прямой, соединяющей две заданные точки, построенной развертке Сначала рассмотрим задачу по поиску факта пересечения прямой с треугольником. Задача. Пусть задана прямая АВ двумя точками. Пусть также задан треугольник А123. Определить: пересекает ли прямая АВ треугольник А123. Решение. В общем случае вершинам треугольника А123 будут соответствовать на прямой АВ точки С, D и Е, для которых параллельные проекции на координатную ось х будут совпадать с соответствующими проекциями на эту же ось точек 1, 2 и 3 (см. рис. 2.1). Для определения факта пересечения прямой АВ треугольника А123 введем следующее свойство.
Свойство 2.1. Факт пересечения прямой АВ с треугольником А123 считается установленным, если для вершин 1, 2 я 5 на прямой АВ соответствуют точки С, D и Е , для которых проекции на координатную ось х попарно совпадают, а для проекций на координатную ось у справедливо утверждение, что если две из вершин треугольника А123 расположены выше или ниже соответствующих им точек на прямой АВ, то третья вершина будет наоборот ниже или выше соответствующей ей точке на прямой АВ.
Доказательство. Предположим обратное, т. е. все три вершины треугольника А123 расположены выше или ниже соответствующих точек С, D и Е на прямой АВ, которая имеет некоторую точку пересечения U с этим треугольником. Если это так, то точка U принадлежит одному из ребер треугольника А123 и является точкой пересечения этого ребра с прямой АВ, а следовательно вершины этого ребра должны располагаться по разную сторону от соответствующих им точек на прямой АВ, что противоречит поставленному условию. Следовательно, вышеуказанное свойство справедливо.
Далее, рассмотрим задачу по установлению факта пересечения прямой с парой соседних треугольников, определяемых четырьмя вершинами (рис. 2.2). Определим свойство аналогичное свойству 2.1 для пар соседних треугольников. 4 на прямой АВ соответствуют точки С, D, Е и F, для которых проекции на координатную ось х попарно совпадают, а для проекций на координатную ось у справедливо утверждение, что если одна из вершин четырехугольника 1, 2, 3 и 4 расположена выше или ниже соответствующей ей точки на прямой АВ, то имеется другая вершина, которая будет наоборот ниже или выше соответствующей ей точке на прямой АВ.
Доказательство. Предположим обратное, что одна из вершин 1, 2, 3 и 4 расположена выше или ниже соответствующей ей точки на прямой АВ, и нет точки, которая будет наоборот ниже или выше соответствующей ей точке на прямой АВ и при этом прямая АВ пересекает одну из соседних треугольников. Если это так, то все вершины 1, 2, 3 ж 4 расположены выше или ниже соответствующих им точек на прямой АВ, а следовательно согласно свойства 2.1 не пересекают ни одну из соседних треугольников. Следовательно, свойство 2.2 справедливо.
Используя свойства 2.1 и 2.2, перейдем к определению свойства принадлежности отрезка АВ условной развертке между точками А я В, состоящей из соседних пар треугольных ячеек.
Свойство 2.3. Отрезок АВ полностью принадлежит построенной условной развертке между точками А и В, если прямая АВ пересекает все пары соседних треугольных ячеек.
Доказательство. Предположим обратное, что отрезок АВ принадлежит условной развертке, но не пересекает некоторую пару соседних треугольных ячеек. Но так как условная развертка из Главы 1 определена, как непрерывная последовательность соседних пар треугольных ячеек с одинаковым направлением знака пристраивания, то в данном случае возникает нарушение условия непрерывности условной развертки. Следовательно, свойство 2.3 справедливо.
Теперь составим аналитические выражения для определения положения отрезка прямой АВ и условной развертки топографической поверхности. где хс , ус — координаты точки С, принадлежащей прямой АВ и соответствующей вершине (і, у); XD , Уй — координаты точки Д принадлежащей прямой АВ и соответствующей вершине (/+7, j); ХЕ , УЕ — координаты точки Е, принадлежащей прямой АВ и соответствующей вершине (i+l,j+l); F, yF— координаты точки F соответствующей вершине (/, j+1). Для сравнения координат у вершин пар соседних треугольных ячеек и соответствующих им точек на прямой АВ будем рассматривать следующие неравенства: Если неравенство из (2.3) выполняется, то вершина располагается ниже соответствующей ей точке. В противном случае, если разность равна нулю, то вершина совпадает с соответствующей ей точкой, а если разность отрицательная, то вершина располагается выше соответствующей ей точки. Перепишем теперь свойство (2.2) в зависимости от результатов проверки неравенств (2.3).
Свойство 2.4. Факт пересечения прямой АВ с парой соседних треугольных ячеек, заданных координатами четырех своих вершин (i,j), (i+l,j), (і, j+1) и (i+l,j+l), считается установленным, если для этих вершин (i,j), (i+l,j), {і, j+1) и (i+l,j+l) на прямой АВ соответствуют точки С, D, Е и F, для которых проекции на координатную ось х попарно совпадают и если одновременно не выполняется от одного до трех неравенств из (2.3).
Алгоритм по установлению факта пересечения прямой АВ с парой соседних треугольных ячеек с целью применения на компьютере удобно реализовать через счетчик, который при выполнении неравенства увеличивается на единицу, при не выполнении неравенства уменьшается на единицу, а если разность равна нулю то счетчик не изменяется. Алгоритм проверяет все неравенства из (2.3) и соответственно влияет на изменение счетчика. Если окончательное значение счетчика равно 4, то следовательно прямая АВ проходит выше пары соседних треугольных ячеек. Если окончательное значение счетчика равно -4, то следовательно прямая АВ проходит ниже пары соседних треугольных ячеек. Если же счетчик не равен 4 без учета знака, то следовательно прямая АВ проходит через пару соседних треугольных ячеек. Блок-схема алгоритма показана на рис. 2.3.
Определение принадлежности отрезка прямой, соединяющей две заданные точки, построенной на развертке
Оптимизация конфигурации инженерных сетей сводится, как известно, к построению кратчайшего дерева, связывающего фиксированное множество пунктов. При геометрическом моделировании инженерных сетей возникает задача Штейнера по определению линии, соединяющую заданные точки. Решение этой задачи рассматривались в следующих работах [21, 35, 45, 86, 90, 117, 120, 123, 132]. Но большинство исследований проводились для задач по нахождению кратчайших связывающих деревьев только на плоскости. Некоторые авторы использовали методы по поиску кратчайших расстояний по заданным направлениям [98, 115]. Применение разработанных методов ограничивается следующими факторами: 1) методы построения кратчайшего связывающего дерева на реальной поверхности, в общем случае, отличаются от методов на плоскости. Поэтому возможны серьезные ошибки при проектировании, например, когда линия нефтепровода прокладывается через высокую гору или глубокую впадину; 2) на реальной местности практически всегда существуют различные преграды, встающие на пути прокладки трубопровода по кратчайшей линии; 3) трасса, проложенная по не оптимизированному пути, приводит к дополнительным расходам средств по эксплуатации, так как имеются перепады по высотам, в результате этого в нефте- и газопроводах падает давление, что приводит к необходимости использования дополнительных энергетических затрат на насосных станциях; 4) не оптимизированные трассы также приводят к дополнительным экономическим потерям, вследствие удаленности от промышленных центров, необходимости строительства дополнительной инфраструктуры: дорог, мостов, насосных станций и т.д. К тому же эти факторы часто присутствуют не изолированно друг от друга, а в совокупности. Все это не позволяет решать нашу задачу точными методами. Таким образом, невозможно точно найти кратчайший путь (геодезическую линию) между двумя точками на топографической поверхности, который бы представлял бы собой натянутую струну, занявшую устойчивое положение, стремящуюся к прямой линии и характеризующуюся минимальной длиной. Второй фактор можно свести к первому, т.е. к решению задачи построения кратчайшей связывающей линии на топографической поверхности при помощи введения «весовых» коэффициентов, приводящих самые разнообразные условия местности к некоторому типовому рельефу. В данной главе нами рассматриваются методы и алгоритмы по построению кратчайших связывающих линий на топографической поверхности, основанные на рассмотренных во второй главе методах и алгоритмах по геометрическому поиску квазигеодезической линии между двумя заданными точками путем построения условной развертки части топографической поверхности. Особенностью предлагаемой методики является возможность использования богатейшей базы ранее разработанных методов и алгоритмов для решения задачи построения кратчайших сетей на плоскости к решению задачи на сложной реальной топографической поверхности. В начале дадим реферативный обзор по методам построения кратчайших связывающих линий на плоскости. Для решения задачи нахождения кратчайших связывающих линий на топографической поверхности с использованием ее условной развертки необходимо рассмотреть алгоритмы и методы решения той же задачи на плоскости. Заметим, что развертка — это отображение поверхности на плоскость. длиной. Известно также, что можно получить связывающую данное множество точек линию с меньшей суммарной длиной, если разрешается добавлять новые точки. Линия минимальной длины, связывающая заданные вершины с использованием любого числа дополнительных точек, называется кратчайшим деревом Штейнера (далее будем обозначать КДШ). Дополнительные точки-вершины этого дерева называются точками Штейнера (далее будем обозначать S). Сформулируем следующую задачу: Дано компланарное множество точек: А і, А2, ..., А„ . Требуется построить КДШ, отыскав необходимые минимизирующие точки Sh S2, ..., Sm . Решение будем искать следующим путем: 1) если у первого треугольника АіА2А3 все углы меньше 120 , то часть искомого КДШ состоит из трех ребер, которые образуют между собой углы по 120 и инциденты точке S (рис. 3.1, а); 2) если же первое условие не выполняется, то искомое КДШ будет состоять из двух ребер, соединяющие вершины ;, А2 и А3 (рис. 3.1, б). Точку S можно найти с помощью следующих известных методов. Способ окружностей. Если построить три окружности с центрами в точках О), О2, Оз, являющихся точками пересечения прямых, проведенных через вершины треугольника А]А2А3 под углом 30 к соответствующим ребрам, то точка пересечения этих трех окружностей будет являться точкой Штейнера — S (рис. 3.2).
Способ прямых. Если на каждой стороне треугольника А1А2А3 построить соответствующий равносторонний треугольник, направленный наружу, тогда прямые А]0], А202 и А303, где точки Oj, 02 и 03 — новые вершины равносторонних треугольников, пересекутся в точке Штейнера S. Этот способ разработал С. Кокстер [54] (рис. 3.3).
Комбинированный способ. На одной из сторон треугольника А1А2А3 строим равносторонний треугольник. На этой же стороне строим равнобедренный треугольник с углом у основания равным 30. Вершину равностороннего треугольника соединяем с противолежащей вершиной треугольника А Аз . Вершину равнобедренного треугольника используем как центр окружности, которую проведем через две другие вершины этого же треугольника. Построенные прямая и окружность будут пересекаться в точке Штейнера — S (рис. 3.4).
Построение квазигеодезической линии, соединяющей три заданные точки на топографической поверхности
Для решения задачи по построению квазигеодезической линии на топографической поверхности, соединяющей п заданных точек, предлагаем использовать разработанный нами алгоритм для случая из трех точек. На основе принципа наименьшего удлинения можно разбить нашу сложную задачу для п точек на множество более простых задач для трех точек.
Сформулируем следующий алгоритм: 1. Выбираем пару точек М,- и My, для которых квазигеодезическая линия имеет наименьшую длину. 2. На каждой последующей ступени квазигеодезическая линия удлиняется за счет добавления новой точки, т. е. переходим от КДШ, к КДШ,+;, где t — количество точек КДШ. При этом из всех возможных вариант присоединения новой точки следует выбирать вариант, дающий наименьшую длину. 3. Подключение всех точек из заданного множества заканчивает выполнение алгоритма. Для реализации предлагаемого алгоритма на практике рекомендуется использовать диалоговые возможности компьютера. Проектировщик выбирает на графическом дисплее вариант разбиения заданного множества точек. По программе компьютер выдает результаты для каждого варианта. На основе полученных данных специалист может выбрать наиболее оптимальный вариант. 3.3. Выводы 1. Дан реферативный обзор и анализ существующих методов и алгоритмов построения кратчайших деревьев, соединяющих заданные точки на плоскости. 2. Составлены необходимые нам формулы для аналитического вычисления координат точки Штейнера S на плоскости. 3. Разработана блок-схема алгоритма определения точки Штейнера для заданных трех точек. На основе данной блок-схемы написана программа Steiner на языке высокого уровня Object Pascal. 4. Для построения кратчайших деревьев, соединяющих заданные точки на топографической поверхности, обобщены разработанные нами алгоритмы для нахождения квазигеодезической линии между двумя заданными точками на топографической поверхности. 5. Разработан алгоритм нахождения КДШ на топографической поверхности для трех заданных точек. 6. С целью реализации полученных нами алгоритмов была разработана блок-схема применительно к поиску пути построения условной развертки для заданных трех точек на топографической поверхности. На основе данной блок схемы была написана программа RazVlasSt на языке высокого уровня Object Pascal. В диссертационной работе, посвященной геометрическому моделированию конфигураций сложных и разветвленных инженерных сетей, получены следующие теоретические и прикладные результаты: 1. Предложена методика перехода от способа задания топографической поверхности дискретным линейным каркасом к способу ее задания дискретным точечным каркасом, позволяющим вводить в компьютер геометрическую информацию об особенностях конкретного реального рельефа местности для прокладки трубопроводов, в частности нефтепроводов. 2. Разработаны метод, методики и алгоритмы построения условной развертки узой полосы топографической поверхности по заданному направлению, т.е. в зоне трассы проектируемого трубопровода. 3. Предложен и обоснован способ определения квазигеодезической линии топографической поверхности, основанный на использовании условной развертки поверхности по заданному направлению. 4. Разработан алгоритм построения квазигеодезической линии, соединяющей две фиксированные точки на топографической поверхности. Данный алгоритм переносит кратчайшую линию с развертки на поверхность. 5. Поставлена и решена задача о кратчайшем соединении трех точек топографической поверхности, которая является обобщением аналогичной задачи Штейнера на плоскости. 6. Разработан алгоритм построения кратчайшего связывающего дерева на топографической поверхности, служащего оптимальной геометрической моделью сложных и разветвленных инженерных сетей. 7. На основе разработанных алгоритмов составлены программы ModeBrez, Razvert, Poisk, Perenos, Steiner, RazVlas и RazVlasSt на языке высокого уровня Object Pascal, которые образуют в совокупности геометрический модуль системы автоматизированного проектирования инженерных сетей. 8. Результаты настоящей диссертационной работы использованы при проектировании промысловых нефтепроводов, а также внедрены в учебный процесс Актюбинского филиала Казахского национального технического университета имени К. И. Сатпаева.
