автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы вычислительной геометрии в задачах расчета сил моментов светового давления и аэродинамического сопротивления, действующих на космические объекты

РТ5 оа

Я 3 о;«

ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ им. М.В. Келдыша Российской Академии Наук

На правах рукописи УДК 681.3.082

БАЛАБАН Иван Юрьевич

МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ В ЗАДАЧАХ РАСЧЕТА СИЛ И МОМЕНТОВ СВЕТОВОГО ДАВЛЕНИЯ И АЭРОДИНАМИЧЕСКОГО СОПРОТИВЛЕНИЯ, ДЕЙСТВУЮЩИХ НА КОСМИЧЕСКИЕ ОБЪЕКТЫ

Специальность 05.13.11 — "Математическое и программное обеспечение вычисли*)ельных машин, комплексов, систем и сетей".

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 1995

/

Рабсп иыполнекав Институте Прикладной Математики им. М.В.Кслдыша РоссиЬ кой Академии Наук

Научные руководители:

доктор физико-ыатематичоских наук, профессор Л.К.Платонов кандидат фи п.го-матемаа ичсских наук М.М.Комаро:

Официальные оппоненты:

доктор физико-математич(^ских наук М .М .Горбунов- Посадов кандидат физико-математических наук К.И.Кий

Ведущая организация:

Вычислительный Центр Российской Академии Наук

Защита состоится "_"_1995г. в _па заседании диссертационного совета Д 002.40.1 при Институте Прикладной Математики им. М.В.Келдыша Российской Академии Наук по адресу: 125047, Москва А-47, Миусская пл. 4.

Автореферат разослан "_"_1995г.

Ученый секретарь Диссертационного Совета кандидат физико- математических наук ^ -•

Т.А.Нол илова

Актуальность темы

Существует значительный интерес к эффективным методам вычисления светового и аэродинамического воздействия на космические объекты. Это связано с растущими требованиями к точности траекторных расчетов и с возможностью использования сил светового и аэродинамического давления для управления движением космических аппаратов. Например, расчет движения астероидов, орбиты которых проходят близко к орбите Земли. Не исключена возможность их столкновения с Землей, что вызовет катастрофические последствия. Поэтому важен точный расчет их траекторий, чтобы была возможность как можно раньше определить возможное столкновение и принять соответствующие меры. Силы светового давления могут использоваться даже в качестве основного источника тяги при межорбитальных перелетах аппаратов, снабженных солнечным парусом.

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

Набегающий поток газа, создающий аэродинамическое давление, приближенно можно рассматривать как поток параллельных лучей. С учетом последнего допущения, построение участков поверхности, омываемых аэродинамическим потоком, можно проводить при помощи тех-же алгоритмов, что и построение освещенных участков поверхности. Определение таких участков и являете:» центральной задачей, рассматриваемой в работе.

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

Цель работы

Целью работы является разработка и реализация алгоритмов решения геометрических задач, возникающих при вычислении главного

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

Методы исследования

В работе использованы методы и аппарат алгебры, анализа, вычислительной геометрии. Проведено численное тестирование полученных программ.

Научная новизна

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

2. Разработан и проанализирован новый, ассимптотически оптимальный алгоритм поиска пересечений отрезков па плоскости, улучшающий известные оценки.

3. Предложен практичный метод обработки случаев необщего положения - вырождений. Исследовано его поведение для часто встречающихся геометрических вырождений.

Практическая ценность

Программный комплекс Illumination, созданный автором на основе предложенных в работе алгоритмов, был применен в работах но гранту РФФИ (код проекта 94-01-01090).

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

Апробация работы

Основные положения и результаты диссертационной работы докладывались и обсуждались на конференции "Методы и средства обработки сложной графической информации" г. Нижний Новгород 1992г.; на 40-ой научно-практической конференции МФТИ 1995г.; на 19-ых научных чтениях но космонавтике 1995г, ва 11-ом ежегодном симпозиуме АСМ по Вычислительной Геометрии г. Ванкувер 1995г.

Структура и объем работы

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

Содержание работы

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

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

В работе эта задача сводится х построению границ освещенных участков поверхности многогранника.

Во введении, на основе анализа литературы по тематике диссертационной работы, делается вывод о том, что быстродействие алгоритмов, решающих дапную задачу, зависит от затрат на поиск точек пересечения проекций определенных ребер многогранника. Отсюда делается вывод о том, что ключ к построению эффективного алгоритма решения задачи это эффективный алгоритм нахождения пересечений проекций нужных ребер.

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

Рис. 1

Глава 1

Решение задачи построения освещенных участков разбивается на четыре этапа.

1. Нахождение множества фронтальных граней, контурных ребер и особых вершин многогранника.

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

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

3. Определение затененности ребер и вершил.

4. Определение освещенных участков поверхности.

Второй этап является наиболее важным и определяет время работы алгоритма. На этом этапе необходимо найти п-пересечения контурных ребер с контурными и фронтальными ребрами. Для нахождения

п-пересечений контурных ребер с контурными можно воспользоваться алгоритмами, предназначенными для поиска пересечений множества отрезков на плоскости. Задача поиска пересечений множества отрезков на плоскости рассматривается во второй главе. Нахождения п-пересечений контурных ребер с фронтальными можно свести к задаче поиска пересечений между двумя множествами отрезков на плоскости. Однако для решения последней задачи не существует достаточно эффективных алгоритмов. Поэтому в работе предлагается - специальный алгоритм, основанный на специфике расположения контурных и фронтальных ребер.

Рассматриваются свойства множества фронтальных граней, имеющих непустое п-пересечение с точкой р, для которого вводится обозначь UD{p). Это множество обладает следующими свойствами.

Свойство 1. Пусть имеется кривая I : р = p(t) с регулярным параметром t € Д3. Тогда при изменении t множество UD(p(t)) будет изменяться только в точках п-пересечезшя кривой I с контурными илп фронтальными ребрами. Причем в общем положении возможны только следующие изменения.

- В точке п-пересечения с контурным ребром происходит добавление инцидентной ему фронтальной грани к множеству UD, если её там не было, и удаление, если она там содержалась.

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

Свойство 2.Рассмотрим произвольную точку р б I- Ближайшая к этой точке (вдоль кривой) точка п-пересечения I с ребрами многогранника есть либо точка п-пересечения I с контурным ребром, либо точка п-пересечения I с ребром, инцидентным одной из граней множества UD(p).

В итоге предлагается следующий метод.

1. Находим точки п-пересечений контурных ребер.

2. Точки, принадлежащие одному и тому же ребру, упорядочиваем в направлении ребра. Первая по порядку точка п-пересечения должна находиться ближе остальных к началу ребра, последняя — ближе к концу. По мере нахождения новых точек п-пересечения они должны добавляться в сп 1ски п-пересечений соответствующих ребер с сохранением этого порядка.

3. Находим множества UD для определенного набора вершин. Эти вершины называются в работе начальными.

4. Обходим контурные ребра, начиная с начальных вершин. При этом}

для каждого ребра простым перебором находим все п-пересечения этого ребра с ребрами, инцидентными граням, содержащимся во множестве UD его первой вершины.

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

Нахождение множеств UD для начальных вершин осуществляется следующим способом. Выбираем точку ро, ;уш которой легко определяется множество UD. Например, для точки с абсциссой меньшей абсцисс всех вершин многогранника UD = 0. Соединяем точку р0 и все начальные вершины контурных циклов ломаной. После этого множество UD начальной точки каждого контурного цикла находится прохождением по ломаной, начиная с и применением вышеизложенного алгоритма.

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

При создании комплекса Illumination широко использовался объектно-ориентированный подход. Объектно-ориентированный подход к реализации алгоритмов состоит в анализе алгоритма с целыо определения абстрактных структур данных — "объектов" и операций пад ними.

• Объекты — сущности имеющие структуру и состояние.

• Операции — действия, участвуя в которых, объекты могут получать доступ к своему состоянию и изменять его.

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

Общие принципы построения и функционирования комплекса Illumination таковы.

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

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

Глава 2

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

2.1 Краткий обзор имеющихся алгоритмов.

2.2 Постановка задачи, описание базовых структур данных.

Рассматривается задача в следующей постановке. На плоскости задано множество 5, состоящее из N отрезков. Необходимо найти множество всех пересекающихся пар (множество пересечений). Пусть количество пересечений равно К.

Общий подход к построению эффективных алгоритмов решения такого рода задач заключается во введения некоторого поряд ка на множестве отрезков, позволяющего вести эффективный поиск пересечений. К сожалению, множество отрезков на плоскости может располагаться весьма сложным образом и это делает невозможным введение "полезного" отношения порядка на всем множестве. Поэтому выделяются структуры на которых отношения порядка легко вводятся. В качестве таких структур предлагается использовать множества отрезков, не пересекающихся внутри заданной вертикальной полосы, концы которых лежат на противоположенных краях полосы. Для них вводится специальное название — лестницы. Для лестниц существует естественное упорядочение отрезков, из которых они состоят, по высоте вдоль полосы. Благодаря такому упорядочению, можно найти пересечение любого множества отрезков Б с лестницей за время 0{\Б\1одп + А), где п - количество отрезков в лестнице, а к - количество найденных пересечений. Если же множество 8 упорядочено по высоте вдоль некоторой вертикальной прямой, лежащей внутри лестницы, то пересечение лестницы и множества Б можно найти за время 0(|5| + п + к).

Далее излагается алгоритм поиска пересечений отрезков в заданной вертикальной полосе.

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

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

2.3. Промежуточный алгоритм.

Чтобы решить задачу в общей постановке, необходимо представить

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

Основной рекурсивный шаг алгоритма заключается в следующем, ч Пусть имеется множество отрезков в, лежащее внутри некоторой полосы. \ Нам известен порядок следования ординат отрезков, концы которых ^ лежат на левом краю полосы. Если концы всех отрезков лежат на \ противоположенных сторонах полосы, то применяется процедура, изложенная в п.2.3, и происходит возврат множества в, упорядоченного по возрастанию ординат правых концов, на предыдущий уровень рекурсии (если он был, если нет, то алгоритм завершен). В противном случае (не все концы отрезков лежат на противоположенных сторонах), выделяется максимальная лестница, находятся пересечения лестницы с оставшимся множеством в'. Полоса, вместе с множеством Б', разрезается вдоль вертикальной прямой, проходящей через медиану концов отрезков в полосе. Получаются две вертикальных полосы и два множества отрезков и Бг. Процедура рекурсивно применяется к левой половине (это можно сделать, поскольку, порядок следования ординат отрезков вдоль левого края левой половины получается из порядка следования ординат отрезков всего множества вдоль левого края исходной полосы простым удалением отрезков вошедших в лестницу) — в результате оказываются найдены все пересечения внутри левой половины и множество 81, упорядоченное но возрастанию ординат вдоль разреза. Если разрез прошел через левый конец отрезка, то отрезок добавляется к множеству Б1, если через правый - то удаляется из множества Б1. В результате получается множество Бг, упорядоченное по возрастанию ординат вдоль разреза. Теперь можно рекурсивно применить исходную процедуру к правой половине. В результате будут найдены все пересечения внутри правой половины и множество Бг, упорядоченное вдоль правого края правой пловины или, что то-же самое, правого крат исходной полосы. Затеи это множество сливается с упорядоченным множеством отрезков лестницы н получается множество отрезков Э, упорядоченное вдоль правого края исходной полосы. Это множество возвращается процедурой на предыдущий уровень рекурсии (если он был). Доказано, что такая процедура находит все пересечения множества отрезков за время 0{М1од3Ы + К), при этом необходима память линейная по числу отрезков. Пример изображен на рис 3.

2.4. Оптимальный алгоритм.

Показано как модифицировать алгоритм, чтобы он работал за время 0{NlogN 4- К). Главное препятствие к достижению такой оценки появляется на этапе нахождения пересечений множества отрезков с ' лестницей. Порядок на подмножествах, пересекающих левый и правый

края полосы, получается вышеизложенным алгоритмом. В результате пересечения лестницы с отрезками, пересекагрпшмн левый или правый край полосы, можно найтк, согласно результатам 2.2, за время 0(|5|+к), где к - количество найденных пересечений. Однако пересечения отрезков, лежащих целиком внутри полосы, приходится пехать за время 0(п1одЫ+ к), где и — количество таких отрезков. Показано, что это и приводит к появлению квадрата в результирующей оценке алгоритма. Предложен алгоритм создания дополнительных структур, хранящих информацию об отрезках, полученную на более глубоких стадиях рекурсии. Это позволяет [¡екать пересечения лестницы с отрезками, лежащими целиком внутри полосы, за время О [л + к).

Доказано, что, с учетом изменений в алгоритме и построения дополнительных структур данных, время его работы будет равно 0{NlogN + КУ, при необходимой памяти О(^), что является ассимптотически оптимальным. Доказательство содержат семь лемм и три теоремы.

Глава 3

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

В п. 3.1 содержится описание проблемы вырождений во входных данных.

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

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

3.2 Описание вычислительной модели и метода символических возмущений.

Рассматривается некоторый алгоритм, на вход которого подается вектор I = (к1,...,и„,11,...,/4), щ е Я, 1> 6 где Л — множество действительных, £ — множество целых чисел. Алгоритм использует набор ячеек памяти М = (го1,...,гот,]\,...,]ч), ячейки и>;, { = 1,...,п предназначены для храпения действительных чисел, ячейки i = — целых. Проекция вектора I на обозначается через и, на Ъ* — через Ь, содержимое памяти в какой-то момент времени считается парой векторов (№,/), € Я™, / е

В качестве вычнелятельной модели используется модель Алгебраического Дерева Решений (АДР).

Алгоритм начинает выполняться с корня дерева. В каждом внутреннем узле происходит сравнение одной из входных величин или содержимого одной из ячеек памяти с нулем и, в зависимости от результата (меньше нуля, равно нулю, больше нуля), переход к одному из сыновей. При проходе по ребру модифицируется содержимое памяти. Если задан вход I, то алгоритм проходит некий путь Р(1) в дереве, достигая листового узла, в котором выводится содержимое некоторых ячеек памяти.

Особенно выделяется случай, когда величина сравниваемая с нулем во внутреннем узле является "непрерывной", т.е. принадлежат й. Такие величины в работе называются критическими.

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

Дня обработки вырожденных входов в методе символических возмущений используется следующий прием: на вход алгоритма вместо вектора Г = (1/,Ь) подается вектор I' = (и',Ь), и' = и + с г, где и — вещественные входные переменные, V — возмущенные переменные, г — случайный вектор, а е символическая величина, обладающая такими свойствами:

1. £ больше нуля

2. с меньше любой величины, большей нуля.

После того, как на вход подан вектор I' = («1»1ь —>*«)> алгоритм начинает работу. Величины (и'1)...,и|л,го1,..'.,и)7) рассматриваются как дробно рациональные выражения от е. При выводе они вычисляются путем приравнивания е нулю. Сравнение с нулем дробно-рационального выражения от е сводится к сравнению с нулем соответствующего мно-

гочлена. Если вход I' также оказывается вырожденным, то вектор г меняется случайным образом и алгоритм начинает работать заново.

Недостатком этого метода является необходимость поддержания арифметических операций над дробно-рациональными выражениями от е.

3.3 Разбираются пути адаптации метода символических возмущений для практического использования.

Предлагается вести все вычисления над кольцом полиномов от е по модулю е2, которое обозначается через Е. Все величины в алгоритме будут иметь вид а + сЬ со следующими операциями:

1. (о + е'Ь) + (с+ с<1) = (а + с) + е(6 +■ <*),

2. (а + Е&)(с+£<0 = ас + £(&с + а<*),

3. Для всех элементов кольца, кроме делителей нуля, имеющих вид О + е Ь, существуют обратные элементы. Отсюда правило деления: при а^О, (с + £с1)/(а + еЬ) = с/а + е(ё/а — Ь* (1/а2).

4. Ноль в кольце имеет вид 0 + с 0.

5. Сравнение двух чисел (а + е 6) и (с + е й) происходит следующим образом. Если а < с или о = с и Ь < то (о + еЬ) < (с + ей), если а = с и Ь = то (а + £ Ь) = (с + е

Окончательно алгоритм работает так. На вход подается возмущенный вектор 1' и алгоритм начинает работать, используя вышеприведенные операции. Если в ходе работы обнаруживается, что /' вырожден, то вектор г меняется случайным образом и алгоритм начинает выполняться заново.

Скорость работы метода существенно возрастает, так как операции над элементами кольца Е выполняются значительно быстрее, чем над дробно-рациональными выражениями от е. '

Однако, теперь нельзя ликвидировать все классы вырождений, так как для некоторых из них вход V может оказаться вырожденным при любом значении г. Такие входные данные называются в работе нелинейно вырожденными.

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

Л(я(/) ф о),

соответственно множество вырожденных определяется набором уравнений

УЫ*У) = 0),

то подмножество нелинейно вырожденных входов определяется следую-

щвм условием

v(ы^) = o)л(gradt/ы/)) = o).

Далее рассматривается вопрос о том насколько "велико" множество нелинейно вырожденных входов. Условие, невырожденности называется в работе линейнъич, если множество нелинейно вырожденных входов для этого условия имеет меру нуль во множестве всех вырождеииых входов. В проткзюм случае оно называется нелинейны.«.

Доказано, «го множество нелинейных условий невырожденности имеет меру нуль во множестве условий невырожденности предстааимых полиномами.

Рассматриваются три ^ида условий невырожденности, часто встречающихся в геометрических алгоритмах, работающих с объектами ва плоскости.

1. Задан набор из пар исходных точек, пи какая из ник да имеет одинаковых абсцисс (ординат).

2. Задан набор троек исходных точек. Необходимо, чтобы ни одна тройка не лежала на одной прямой.

3. Задан набор, троек отрезков, каждый из которых задан парой исходных точек. Необходимо, чтобы ни одна тройка не пересекалась в одной точке.

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

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

Рассматривается некоторый алгоритм А, представляющий набор процедур т,...,Ш1, выполняющихся в определенной, зависящей от входа последовательности, причем ни одна из перечисленных процедур не вызывается дваждьт Предполагается, что в классе данных П, к которому нужно применить ашъритм А, могут встретиться вырождения не обрабатываемые процедурами Як,...,Ю [к,1] 6 [1,Ь]. Другие вырождения в классе П либо не встречаются, либо корректно обрабатываются всеми процедурами. Желательно работать с обычным представлением чисел

ana процедур Rk,...,Rl и переходить к представлению чпссл как элементов кольца Е только внутри этих процедур (локальные возмущения).

Входные переменные процедуры Ш, i 6 ¡k,ij, возмущаемые при ее вызове обозначаются через ш5 '= (w¡,tí?^«).

Доказано, что ;шгоритм А будет корректпо обрабатывать все данные из класса П с использованием локальных возмущений, если любой вход вырожденный для процедуры Ял, ,ч € [£,í] не является вырожденным для всех остальных процедур и ранг якобиана

не меньше п~\

Третья глава также содержит результаты эксперимента но использованию вышеописанного метода. Суть эксперимента в том, что создаются два модуля Values 1 и Values2, которые описывают тип floatvalue, предназначенный для представления чисел с плавающей точкой и операций над ними, В модуле Valuesl представление чисел с плавающей точкой и операции с пими является стандартным. Модуль Values2 служит для представления элементов кольца Е и определяет операции над ними. Цель состоит п том, чтобы сравнить работу программ, когда они используют модуль Valuesl и когда они используют модуль Values2.

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

При использовании модуля Valuesl при подаче вырожденного входа часто получался неверный результат, в то время как при использовании модуля Values2 вышеупомянутые программы корректно обрабатывали все вырожденные и невырожденные входы, но работали примерно вдвое дольше.

\

Список результатов.

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

• На основе предложенного алгоритма создан программный комплекс Шшшш^юп для расчетов главного вектора и главного момента сил светового давления, действующих на космические объекты. При создании комплекса широко использовался объектно-ориентированиый подход и написана библиотека классов геометрических объектов.

• Разработан новый ассимптотически оптимальный (как по времени работы, так и по необходимой памяти) алгоритм поиска пересечений множества отрезков на плоскости. Тем самым положительно решен остававшийся долгое время открытым вопрос о существовании такого алгоритма. В отличие от известных алгоритмов с оптимальным временем работы, предложенный алгоритм не требует прямолинейности отрезков (отрезки могут быть отрезками кривых). Предложен упрощенный вариант алгоритма. Этот вариант значительно проще с точки зрения программной реализации, обладает несколько худшим ассимптотическим временем работы и работает в два раза быстрее на реальных данных.

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

Публикации

Результаты диссертации опубликованы в работах:

1. Балабан И.Ю., Алгоритм поиска пересечений множества отрезков. Препринт Института прикладной математики им. М.В. Келдыша РАН, 1994, N45.