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

На правах рукописи

РЫБАЛКА Сергей Анатольевич

Математическое и программное обеспечение генерирования векторных сплайн-изображений с оценкой качества в метрике Хаусдорфа

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

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Томск

1997

Работа выполнена в Томском политехническом университете

Научный руководитель : доктор технических наук, профессор Ксчегуров ВА

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

доктор технических наук, профессор Бондаренко В.П.,

кандидат технических наук, доцент Воловоденко В А.

Ведущая организация; НГГУ ( г. Новосибирск )

Защита диссертации состоится " 3 " 1Лс С /■{ •)" 1997 г. в часов на заседании диссертационного Совета Д 063.80.03 Томского политехнического университета по адресу: 634034, г. Томск, пр. Ленина 30.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан " л/ )" 1997 г.

Ученый секретарь диссертационного совета, кандидат технических наук доцент

Общая характерв ста ка работы

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

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

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

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

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

переносятся и на пространственные кривые, как. объекты образованные композицией явных функций.

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

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

1. Исследовать особенности приближения плоских и пространственных регулярных кривых в метрике Хаусдорфа параметрически заданными многочленами и сплайнами.

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

3. Решить задачу о наилучшем приближении регулярной пространственной кривой параметрическими сплайнами.

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

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

Работа выполнялась в соответствии с госбюджетной темой "Разработать и ввести в опытную эксплуатацию в ТПИ автоматизированную систему научных исследований и обучения в обласга электрофизики" входящей в научно-техническую программу ГКНТ "Создать новые и развить действующие системы автоматизированного проектирования (САПР) и автоматизированные системы научных исследований (АСНИ) в народном хозяйстве" на 1986 — 1990 гг.

Научная новизна результатов, полученных в диссертации, состоит в следующем :

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

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

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

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

Практическая цепкость работы.

1. Разработан алгоритм построения неулучшаемого многочлена для гладкой пространственной кривой.

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

-73. На основе оценок, полученных в диссертации, разработаны алгоритмы и пакет подпрограмм интерполяции и аппроксимации регулярных плоских и пространственных кривых сплайнами первой степени. 4. Разработанные алгоритмы и программы внедрены в программные комплексы построения карт, применяемые в нескольких НГДУ, а также в пакет построения графиков, внедренный в учебный процесс на кафедре прикладной математики "ГПУ.

Апробация работы. Основные положения диссертации докладывались и обсуждались на:

1. Пятой региональной научно-практической конференции "Молодые ученые и специалисты — ускорению научно-технического прогресса", Томск, 1986.

2. Всероссийском семинаре "Вопросы огтшизации вычислений", Алушта, 1987.

3. Третьей Международной Конференции по Компьютерной Графике и Визуализации (вИАРШССЖ'93), Санкт-Петербург, 1993.

4. Втором Сибирском Конгрессе по Прикладной и Индустриальной Математике (ИНПРИМ-96), Новосибирск, 1996 г.

Публикация. По результатам выполненных исследований было опубликовано 7 работ.

Оеиозпьге положения выпоетзые ва защиту :

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

» Получены аналога теоремы Чебышева для характеризации неулучшаемого параметрического многочлена на плоскости и в п-мерном векторном пространстве.

• Решены задачи построения наилучших и асимптотически наилучших в метрике Хаусдорфа сплайнов оценочным и точным численно - аналитическим методами.

Структура и объем работы. Диссертация состоит из введения, трех глав и заключения. Основная часть содержит 101 страницу текста, 28 рисунков, список литературы из 44 наименований и приложение.

-8-

Содсраанне работы

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

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

Рассматриваются некоторые дифференциальные свойства функции отклонения полинома Рд(х) от заданной непрерывной функции f(x), определенной на интервале

хе Д=[а, Ь]. Показано, что функция p(f(x),PB(x)) = sup|f(x)-Ptt(x)|,f(x) еСд,

хеД

является равномерно непрерывной функцией на области значений коэффициентов Q={aj}, -<o<aj<«o, i=0,n полинома Рп(*), а функция sup Рп(х) является моно-

ХеД

тонна возрастающей функцией по каждому из коэффициентов aj, Osj^o. При этом

функция xq = strg sap Pa(x) является кусочно-непрерывной функцией от aj, 0<;j хеД

so, Функция <9Pn(x)/c>aj является кусочно-непрерывной на области значений коэффициентов aj, fej^n. На основе этого показано, что функция sop Р„(х) явля-1 х е Л 0

ется равномерно непрерывной монотонно возрастающей функцией по каждому из коэффициентов aj, 0<:j^a с кусочно-непрерывной производной

d(sap Р„(х))/ йа j, G^j^n определенной во всей области значений параметров aj, хеД

а функция inf Р (х) является равномерно непрерывной монотонно убывающей х е Д п

функцией по каждому из коэффициентов aj, Oijin с кусочно-непрерывной произ-

водной inf Рп(х)) /8а.:, O^jsa определенной на всей области значений пара-хеЛ '

метров а:. Показано, что функция sap Р (х), хеД является равномерно непре-* хеЛ1 п 1

рьтной с кусочно-непрерывной производной по каждому из коэффициентов а|, О Skn определенной на всей области значений параметров Q. При этом для фиксированного набора коэффициентов {а.}1*_ g, имеется такое значение aj*, что

функция sap Р (х) на промежутке ase]-®, a¡*[ является монотонно убываю-х еД1 в 1 J

щей, а в промежутке ajefaj*» а>1 монотонно возрастающей. На основе этого доказывается

Теарсма 1.1.1. Функция p(Pn(x), f(x» является всюду дифференцируемой и имеет кусочно-непрерывную производную по каждому коэффициенту aj, Oíko на всей области определения полинома Q.

Задача отыскания полинома наилучшего приближения сеодигся к отысканию минимума функции р(Рн(х), í(x)) на области определения коэффициентов a¡, Ctetei*. Это может быть осуществлено каким-либо численным методом, например, покоординатного спуска. Наличие единственной точки минимума на промежутке ccjej-co, °о[ при фиксированном наборе {а.}?_ гарантирует отсутствие

неоднозначности в работе алгоритма и постоянное движение к полиному наилучшего приближения.

Теорема 1.1.2. Пусть для фиксированного набора коэффициентов {aj}?_g на отрезке Д=[а, Ь] существует только га £ а+1 точек, в которых выполняется равенство

ssgn(f(xk) - Рй(хк)) = -Siga(f{x&+1) - Ptt(sb+1», 1 < k < El.

Тогда справедливо неравенство

р(Рй (Я), f(x)) > ÍEf p(Ptt (X), f(X» .

fotf >

То есть функция равномерного (чебышевского) расстояния между фиксированной кривой f(a) и полиномом Рв(х) является непрерывной с единственной точкой минимума.

Далсс показывается, что если задана регулярная кривая Fj(s) е не имеющая точек самопересечения, а множество ее нормальных плоскостей ®={Р}, и задана регулярная кривая r^ís) е 51й, удовлетворяющая условиям :

а) для любой плоскости Реф существует точка ^(т^), такая, что г2(т0)еР;

б) для любой точки ?2(гд) существует единственная плоскость Реф, такая, чгог2(т0)еР.

Тоща расстояние Хаусдорфа между кривыми Fj(s) и ¡^(s) можно определил, как

x(ri(s),r2(s)) = кгх disl(rj(s),f2(ie)). хо etô,l2l

Эго определяет условия при которых расстояние Хаусдорфа между кривыми будет совпадать с расстоянием от одной кривой до другой.

Пространственный многочлен однозначно задается набором своих коэффициентов ajl, i=l,n, j—G,îû, на фиксированном интервале teja, Ь]. Поэтому расстояние Хаусдорфа от любого многочлена I' (t) до фиксированной кривой r(s)

ш

также однозначно определятся коэффициентами многочлена. Следовательно, существует такой набор коэффициентов aj**, i=l,n, ]=0,и, когда это расстояние ми—*

нимально. Под многочленом наилучшего приближения Pm(t)> teja, b], пространственной кривой r(s), se |0,1], понимается такой многочлен, на котором достигается равенство

X(f(s),P*(t))= Ы x(r(s),Pm(t)). {I'ia}

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

В силу неединственности элемента наилучшего приближения, число точек глобального минимума может быть конечным или бесконечным. К тому же, функция расстояния Хаусдорфа может иметь точки локального минимума, то есть су-

щсствуют такие наборы коэффициентов многочлена (ccj }j ~ и такие их окрестности U(a|î*), что расстояние Хаусдорфа от многочленов с коэффициентами а |ieU(ctji*) до фиксированной 1фивой г (s) удовлетворяет неравенству : X(Pra(0,r(s))*x(P*(t),r(s)).

Отмечено, что множество неулучшаемых многочленов не является выпуклым. Далее доказываются

Теорема 1.3.1. Для того, чтобы многочлен Р_ (t) был неулучшаемым многочлена

ном степени ш для функции r(s), необходимо, чтобы имелось JVfcm+2 точки, такие что

p(Pa<V'F(tk)) = х(Ри(»).?(0)Д = Ï7M,

и чтобы для каждой проекции i существовало подмножество из га+2 точек {t с {{^ j, для которых выполняется равенство

£Îgn(X.(t.) - fj(t.» = -Sîgn(x.(t. + l)~ f.(tj+ j)), j = = M.

Тсорека 1.3.2. Для того чтобы многочлен Рш (t) был неулучшаемым многочленом степени о для функции r(s) пространства а2, необходимо, а в некоторых случаях и достаточно, чтобы имелось М=2а+1 точки, такие что P(Pa(tk),f(tb)) = x(Pn(t),F<t)),k = UM + 1

и

(i&) - r(tk» . F(tb» = - sign^F^ + 1)- r(t& + l)) . F(t& + j)),k = 1ДМ.

Теорзма 1.3.3. Для того чтобы многочлен l'a (t) был неулучшаемьш многочленом степени и для функции r(s) пространства достаточно, чтобы имелось М=2ш+2 точки, такие что

p(Pa(tk),r(tk)) = x(Pra(0,r(t)),k = 1,2га+ 2

и

sign((Pm(tk)-F(tk)).F(tk)) =

- sign((PM(tk + 1)- ?(»k + t))• F(lk + j)),k = 1,2a + 1.

Строится иллюстрационный пример многочлена первой степени аппроксимирующего дугу винтовой линии.

Вводится понятие минимальной окрестности II" регулярной кривой как Ue

окрестность этой кривой, с вычтенными s-окрестностями начальной и конечной точек кривой. Показано, чтобы многочлен Р^ (1) имел расстояние esr до регулярной кривой г (s) е Si3 ограниченной кривизны с минимальным радиусом кривизны г, необходимо и достаточно, чтобы многочлен Р_ (t) лежал в минимальной

ш

окрестности U" кривой и, чтобы существовали такие ig и i£, что точки 1'ы(1р) и

Р (tt ) принадлежали е-окрестностям начальной и конечной точек кривой г (s) ш Л

соответственно.

Далее предлагается алгоритм построения неулучшаемого многочлена Pffl(t)

для фиксированной кривой f (s).

Во второй главе рассматриваются условия построения сплайнов с наименьшим числом звеньев для фиксированной кривой и заданного отклонения, а также условия, при которых сплайн, с заданным числом звеньев, имеет наименьшее отклонение. Вводится понятие многочлена наибольшего удлинения, а также многочлена наибольшего одностороннего удлинения. Исследуется зависимость E(d) расстояния Хаусдорфа x(P_(0»f(s)) между многочленом наилучшего приближения

о

Pm(t),t е [а,Ь] для куска кривой F(s),s е [с,fi], как функции от конечной точки

интервала определения куска кривой d. Показано, что зависимость E(d) является неубывающей непрерывной функцией от значения конечной точки интервала определения кривой. Многочлен Р (i),t е [а, Ь], является многочленом наибаль-

ш

шего удлинения, если он является многочленом наилучшего приближения и лежит в минимальной окрестности U~ кривой F (s), s с {с, d]. Проводятся следующие построения. Для ряулярной кривой r(s), s е [c,d], ограниченной кривизны с минимальным радиусом кривизны г, будем строить кусочно-многочленную кривую с заданной погрешностью е. На интервале [sq, sjJ, sq=c, строим многочлен

P^(t), t t; l»,tj J. Точка si выбирается так, чтобы многочлен P-Lo был много-

членом наибольшего удлинения (полагаем, что это возможно для любого куска данной кривой) с отклонением е от куска кришй r(s),s е [c,Sj]. После этого

строим новый многочлен Р^ (t),t е [tj, t^ ], наибольшего удлинения для куска г (s), s е [Sj^Sj], с отклонением с. Построение продолжаем до тех пор, пока очередная конечная точка яц не выйдет за конечную точку кривой Sft^d. В качестве конечной точки последнего куска кривой r(s),s е берем конечную

точку кривой sjf=d. При этом, естественно, на последнем звене отклонение многочлена наибольшею удлинения не превысит s. Показано, что кусочно-многочленная кривая, казвдое звено которой Р^ (1), t е [t. _ t. J, является многочленом наибольшего удлинения для соответствующего куска кривой г(s),s е [s. _ где 0<feN, sg=c, sfj=d, с задшшым отклонением s, а на куске

[SN-1, sN] не больше е, имеет наименьшее число звеньев при заданном в. Отмечено, что построение кусочно-многочленной кривой с заданным отклонением s приводит к построению кривой с наименьшим числом звеньев. Но последнее звено имеет погрешность не выше е. В силу непрерывности E(d), существует такое s*£s, что каждое звено будет иметь отклонение е*. Такая кривая будет иметь минимальное отклонение при заданном количестве звеньев N. Далее проводится построение кусочно-многочленной кривой приближающей винтовую линию.

Вводится определение сплайна S , (t, Д»т) = S (t), пространства как

S3) S Хч 19

кривой, каждая проекция которой является сплайном не выше m и дефекта не выше

k = a- min (я,- -lî>-

OsteN-ï 1 1

Проводится построение интерполяционной кусочно-многочленной кривой и доказывается, что построенная кусочно-многочленная кривая имеет расстояние Хаус-дорфа до исходной кришй равное е и имеет наименьшее число звеньев для заданного s. Ошечено, что найдется такое е*<е, что интерполяционная кусочно-многочленная кривая будет иметь такое же количество звеньев N, но каждое звено будет иметь отклонение в* и расстояние от конечных точек F(c) и r(d) до этой кривой так же будет равно s*.

Огличигельной особенностью пространственного сплайна является то, что сплайн, каждое звено которою является многочленом наибольшего удлинения, разбивает отрезок определения параметра кривой (с, Л] на неравномерную сетку сг=80<8|<..,<эд=а. При этом сам сплайн может иметь совершенно другой интервал определения и расположение узлов а=1д<11<...<1]^=Ь. Более того, для любой кривой г (в), & е [с,б], всегда можно строил, сплайн на равномерной сетке t е[а,Ь], допустим с узлами в целочисленных значениях 1=0,N. Проекции такого сплайна будут сплайнами дефекта ш+1. При этом, хотя конечные точки звеньев интерполяционного сплайна лежат на кривой, но они не совпадают, поэтому невозможно найти такую параметризацию сплайна, чтобы каждая его проекция была непрерывной функцией от параметра.

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

е. Но производные каждой его проекции Р^ (I) в узловых точках терпят разрыв.

Показано, что непрерывный сплайн (I), в каждом узле которого слева и справа

имеются ненулевые сонаправленные касательные, мохет был. сведен в сплайн

Б степени га дефекта та-1, то есть каждая проекция в узловых

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

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

Для у=1(х) — явной непрерывной кусочно-дифференцируемой функции определенной на интервале хе!а,Ь], причем Г(а)=*1(Ь)=0 существует кусочно-непрерывная функция у*=Г(х), хе[а,Ь]. Пусть Г = шах Г(х) и

а 5 х <: Ь

Р. = шш С'(х). Отсюда имеем шп а£х £ Ь

-15-

fW-f(.) fW-fW^o-)^,

-w b-a

Показано, что для дуга параметрически заданной кривой пространства взаимнооднозначно отображающейся на хорду стягивающую концы дуги, применима та же оценка, что и для явно заданной функции. Далее получена оценка отклонения кривой пространства ЗА Пусть r(t) = (x(t),y(í),z(t)} параметрически заданная

на интервале te [а, Ь) регулярная кривая ограниченной кривизны пространства Ш^. Положим, кривая f(t) такова, что любой ее касательный вектор t(t) составляет с фиксированным вектором ? утоп менее прямого. Выберем новую правую систему координат О'^цС, с центром в точке О' = г (а), осью O'Ç сонаправленной с вектором V; оси О'г) и O'Ç ортогональны оси O'Ç и друг другу. Повернем каждую точку кривой г(1), te [a, Ъ], вохруг оси O'í на угол 2*. След движения кривой будет тело вращения M с осью вращения O'í ; кривая r(t), te [а, Ь], будет лежать на поверхности этого тела вращения М. Зафиксируем произвольную точку кривой r(t*). Построим плоскость L содержащую точку r(t*) и вектор ?. Пересечением плоскости L с телом M является пространственная кривая Ф (t), лежащая в плоскости L, проходящая через точку r(t*) и имеющая ту же начальную точку что и исходная кривая — г(а). Кривую <D(t) параметризуем следующим образом: точка Ф (Í') является точкой пересечения плоскости L и окружности, прочерченной точкой r(t'). при вращении кривой r(t) вокруг оси O'Ç. Построим в точке r(t*) (а, следовательно, и в 0(t*)) касательный вектор а к кривой r(t) и касательный вектор w к кривой Ф (t). Плоскость V натянутая на û и w будет касательной плоскостью к телу M в точке 7(t*). Кривая <1> (t) лежит в плоскости L, поэтому и вектор w лежит с этой же плоскости L. В то же время плоскость V ортогональна плоскости L. Следовательно, угол между векторами w и ¥ равен углу между плоскостью V и вектором ¥ и является минимальным, в том смысле, что любой вектор, принадлежащий плоскости V, будет иметь угол с вектором т не меньше угла между векторами ? и w. То есть угол между векторами V и si не меньше угла между векторами v и W.

Тело вращения М, образованное вращением пространственной кривой г (t) вокруг оси O'Ç, можно также получил, вращением плоской кривой Ф (t) вокруг

той же оси О'г,. В плоскости L выберем прямоугольную систему координат ÇO"0. В этой системе координат кривая Ф (t) может быть выражена явной зависимостыоб( Ç). Найдем максимальную производную 9'(О и построим прямую с этим угловым коэффициентом в системе ÇO'O. Вращение этой прямой вокруг оси O'Ç приведет к образованию конуса вращения Kj, ось которого будет вектор т, построенный в точке О*. Так как построенная прямая мажорирует функцию <D(t), то конус будет охватывать тело М. Пространственная кривая ?(i ) лежит на теле вращения М, следовательно, так же как и тело M внутри конуса Ki.

Построим из точки г(Ь) вектор противоположно направленный вектору т. Повторив все построения проведенные выше получим конус К2, с вершиной в точке г(Ь) и осью -v, охватывающий кривую г (t). Таким образом мы получили тело Q, образованное двумя конусами El и К2, оси которых параллельны друг другу, и охватывающее кривую r(t). Наиболее удаленными точками поверхности Q являются точки линии пересечения конусов — эллипса. Наиболее близкими и

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

расстояния от поверхности Q до отрезка г(я)г(Ь) достаточно посчитать расстоя-

ние от этих точек до отрезка г(а)г(Ь) и выбрать большее. Расстояние от конечной

точки большого диаметра эллипса до отрезка г(а)г(Ь) равно

ICDj^ - jr(ijr(bjp

1 16(1 - cas a) cos р

где а — угол pacraopa конусов; р — угол между осью вращения конуса и отрезком

г(а)г(Ь); r(a)r(b) — длина отрезка г(а)г(Ь). Расстояние от конечной точки ма-

лого диаметра эллипса до отрезка г(а)г(Ъ) определяется как

2

[kl[2=. , (jg=L£-i)

r(a)r<b)

7

.cos р

4 cos2 a

расстояния от конечных точек большего и малого диаметров эллипса до отрезка

г(а)г(Ь) соотносятся как

- 17-

|KL|2 4(1 - cos2 а)

|CD|2 ces2 p - cos2 а

Нетрудно видеть, что это соотношение всегда превышает единицу, так как отрезок

г(а)г(Ь) всегда лежит внутри конусов, а отсюда р<а. Таким образом, для оценки

расстояния между пространственной кривой r(t), te [а, Ь], до ее хорды г(а)г(Ь), достаточно по формуле (3.1.4) определить расстояние от конечной точки малого диаметра эллипса пересечения конусов, охватывающих кривую, до отрезка

г(а)г(Ь).

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

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

ограничивающие угловой сектор касательных к кривой и вектор W, сонаправлен-ный интерполяционному отрезку, совпадающий с касательным вектором к кривой в начальной точке кривой t(a). Двигаясь вдоль кривой, определяем касательный вектор t(t) в текущей точке кривой r(t). Если t(t) составляет положительный ушл с вектором Vj, то значение заменяется на значение вектора t(t). Если

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

,2

А2 = —

[wx vjJIwx т2]

* »21

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

-IB-

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

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

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

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

h2 (y(t)(x(a) - x(t)) - x(t)(y(a) - у(1))2 *2<t)+y2(t)

определим точку t*, касательная в которой удалена от начальной точки f (а) на заданное расстояние е. Из уравнения

j(t)(x(t,) - X(í)) - xOXyííj) - y(a)) = 0

определяем конечную точку интерполяционного звена tj. На следующем шаге точка f(tj) выбирается в качестве начальной и строится новое звено. Алгоритм

заканчивает сбою работу когда очередная конечная точка оказывается вне интерполируемого участка te [a, &J.

Функция отклонения £(t) кривой от интерполяционного звена является монотонно возрастающей функцией, исключая мсжет быть начальный участок, на котором выполняется равенство £(t) ¡9. Следовательно каждое звено интерполяционного сплайна, получаемое в результате работы алгоритма, является звеном наибольшего удлинения, а сплайн имеет наименьшее число звеньев для заданного s. Последнее звено будет иметь отклонение не выше е. Поэтому существует такое что интерполяционный сплайн, построенный с заданным отклонением s*, будет иметь такое же количество звеньев, что и сплайн с отклонением в, но каждое звено будет иметь отклонение е*.

По аналогичной схеме строится аппроксимапионньш сплайн первой степени для гладкой выпуклой кривой пространства Вначале строится интерполяционное звено с двойной погрешностью 2е и перемещается параллельно себе на величину s в сторону кривой. Отыскивается конечная точка звена, а из нее как из начальной точки строится следующее звено. Алгоритм заканчивает свою работу когда очередная конечная точка оказывается вне интерполируемого участка te [а, Ь].

Если r(t) выпуклая замкнутая кривая, то построенный сплайн будет иметь на каждом звене отклонение s, а на последнем звене не больше s. Тогда можно подобрать такое s*, что отклонение на всех звеньях будет одинаковое и равно s*. Но для замкнутой кривой понятие начала кривой имеет смысл лишь как начало движения вдоль кривой и окончание движения в этой же точке (так как конечная точка совпадает с начальной). Поэтому начальная вершина сплайна S^ может находиться как на нормали к кривой восстанавливаемой в точке г(а), так и на нормали восстановленной в произвольной точке кривой r(t). При этом погрешность отклонения многоугольника, с таким же количеством вершин и на каждой стороне имеющего одинаковое отклонение от кривой будет отличаться от е. Поэтому, задавшись количеством вершин а, каждой точке замкнутой кривой r(t), tela, b],

можно поставить в соответствие значение £(t) равное отклонению каждой стороны интерполирующего (аппроксимирующего) многоугольника и имеющего начальную вершину Sq на нормали к этой точке r(t).

Естественно, что функция £(t) имеет точку минимума на интервале te [а, Ь]. Следовательно, сплайн построенный в точке t*, соответствующей равенству

t* = arg mía £(t) astáb

даст многоугольник с минимально возможным отклонением о кривой при заданном числе звеньев п. С другой стороны п-угольник с вершиной в точке S^, взятой

на нормали к кривой в точке г(а), имеет еще п-1 вершину и каждый многоугольник начатый из этих вершин будет иметь такую же погрешность £Г(а). Следовательно, функция расстояния Хаусдорфа между замкнутой кривой и многоугольником является циклической, точек удовлетворяющих уравнению не меньше п, то есть по крайней мере по одной на дуге, соответствующей одной стороне многоугольника, построенного из любой точки кришй. Таким образом для того, чтобы построить п-угольник интерполирующий (аппроксимирующий) замкнутую кривую с минимальной погрешностью, необходимо построил, любой п-угольник с одинаковым отклонением на всех звеньях, а затем искать точку минимума, на дуге, соответствующей одной стороне п-угольника, которой соответствует п-угольник с минимальным отклонением.

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

Процедуры интерполяции и аппроксимации реализованы на языке Borland Pascal 7.0 и вошли в графический пакет визуализации функций и данных разработанный автором на кафедре прикладной математики Томского политехнического университета. Аналогичные процедуры реализованные на языке Си применены в задачах интерполяции линий уровня, при построении карт изолиний поверхностей, натянутых на экспериментальные данные на нерегулярной сетке.

-21-

Выводы

Основные результаты работы сводятся к следующему:

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

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

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

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

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

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

7. На основе подпрограмм интерполирования плоских и пространственных кривых написан пакет программ построения графиков двумерных функций и пространственных кривых.

Основное содержание диссертации изложено в следующих работах.

1. Рыбалка С А, Адаптивная аппроксимация плоских кривых // Тез. докл. Все-союз. семинара по вопросам оптимизации вычислений, Алушта, окг. 1987 г. — Киев, 1987. - С. 187.

2. Рыбалка СЛ. Подготовка исходной информации для синтеза сложных поверхностей // 2 Всесоюз. конф. по методам и средствам обработки сложной графической информации, Горький, сент. 1985 г. ; Тез. докл. — Горький, 1985. — С. 132.

3. Рыбалка СА, Черникова М.В. Адаптивная интерполяция пространственных кривых сплайнами первой степени // Всесоюзный симпоэ. по теории приближения функций, Уфа, июнь 1987 г.: Тез. докл. — Уфа, 1987. — С. 139 - 140.

4. Рыбалка С А., Шумилов Б.М. Локальные хаусдорфовые приближения плоских кривых сплайнами первой степени // Молодые ученые и специалисты — ускорению научно-технического прогресса : Пятая региональная научно - практическая конференция, Томск, 1986 г.: Тез. докл. — Томск, 1987. — С. 38.

5. Рыбалка СА, Шумилов Б.М. О локальной аппроксимации плоских кривых сплайнами первой степени в хаусдорфовой метрике // Изв. вузов. Математика. - 1991. - № 8. - С. 80 - 81.

6. Рыбалка С А, Шумилов Б.М. Приближение плоских и пространственных кривых параметрическими многочленами и сплайнами в хаусдорфовой метрике // Третья Международная Конференция по Компьютерной Графике и Визуализации ГРАФИКОН'93, Санкт-Петербург, сентябрь 1993 г. : Тез. докл. — Санкт-Петербург, 1993. - С. 26 - 27.

7. Рыбалка С А, Шумилов Б.М. Сплайн-интерполяция в геометрическом моделировании // Второй Сибирский конгресс по прикладной и Индустриальной Математике (ИНПРИМ-96), Новосибирск, 1996 г. : Тез. докл. — Новосибирск, 1996. - С. 184.