Условные переменные c. Использование условных переменных для управления отношениями синхронизации. Присвоение значения переменной с помощью функции set

С математической точки зрения кривая, заданная вершинами многоугольника, зависит от интерполяции или аппроксимации, устанавливающей связь кривой и многоугольника. Здесь основой является выбор базисных функций. Как было отмечено в разд. 5-8, базис Бернштейна порождает кривые Безье вида (5-62), но он обладает двумя свойствами, которые ограничивают гибкость кривых. Во-первых, количество вершин многоугольника жестко задает порядок многочлена. Например, кубическая кривая должна быть задана четырьмя вершинами и тремя отрезками. Многоугольник из шести точек всегда порождает кривую пятого порядка. Единственный способ понизить степень кривой - это сократить количество вершин, а повысить степень кривой - увеличить их число.

Второе ограничение следует из глобальной природы базиса Бернштейна. Это означает, что величина аппроксимирующих функций из уравнения (5-63) ненулевая для всех значений параметра на кривой. Любая точка на кривой Безье зависит от всех определяющих вершин, поэтому изменение какой-либо одной вершины оказывает влияние на всю кривую. Локальные воздействия на кривую невозможны.

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

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

Пусть определяет кривую как функцию от параметра , тогда В-сплайн имеет вид

, , , (5-83)

где есть вершина многоугольника, a - нормализованные функции базиса В-сплайна.

Для -й нормализованной функции базиса порядка (степени ) функции базиса определяются рекурсивными формулами Кокса-де Бура:

(5-84а)

Величины - это элементы узлового вектора, удовлетворяющие отношению . Параметр изменяется от до вдоль кривой . Считается, что .

Формально В-сплайн определяется как полиномиальный сплайн порядка (степени ), так как он удовлетворяет следующим условиям:

Функция является полиномом степени на каждом интервале .

И ее производные порядка непрерывны вдоль всей кривой.

Так, например, В-сплайн четвертого порядка - это кусочная кубическая кривая.

Из того что В-сплайн задается базисом В-сплайна, сразу следует еще несколько его свойств:

Сумма базисных функций В-сплайна для любого значения параметра (см. работы и )

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

Кроме , все базисные функции имеют ровно один максимум.

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

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

Общая форма кривой повторяет форму определяющего многоугольника.

Чтобы применить к кривой любое аффинное преобразование, необходимо применить его к вершинам определяющего многоугольника.

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

Последнее свойство В-сплайна сильнее, чем у кривых Безье. У В-сплайна порядка (степени ) точки кривой лежат внутри выпуклой оболочки соседних точек. Таким образом, все точки на В-сплайне должны лежать внутри объединения всех выпуклых оболочек последовательных вершин. На рис. 5-32 приводится иллюстрация для различных значений , причем выпуклые оболочки выделены серым цветом. В частности, при выпуклая оболочка совпадает с многоугольником, т. е. В-сплайн - это сам многоугольник.

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

Если имеется совпадающих вершин, т.е. , то выпуклая оболочка вершин от до - это сама вершина. Отсюда следует, что В-сплайн должен проходить через вершину . На рис. 5-34 изображен пример такой точки для . Далее, так как В-сплайн везде непрерывен, он также непрерывен в .

Наконец, заметим, что свойство непрерывности плавно переводит В-сплайн во вложенные отрезки прямой, как показано на рис. 5-35.

Уравнения (5-84) указывают, что выбор узлового вектора оказывает существенное влияние на базисные функции В-сплайна и, следовательно, на сам В-сплайн. Единственное требование к узловому вектору: , т. е. это монотонно возрастающая последовательность вещественных чисел. Обычно используются три типа узловых векторов: равномерные, открытые равномерные (или открытые) и неравномерные.

Отдельные узловые значения равномерного узлового вектора распределены на одинаковом расстоянии, например

В частности, равномерные узловые векторы обычно начинаются в нуле и увеличиваются на 1 к некоторому максимальному значению или нормируются в диапазоне между 0 и 1 равными десятичными значениями, например,

Рис. 5-32 Свойства выпуклой оболочки В-сплайнов.

Рис. 5-33 Свойства выпуклой оболочки В-сплайнов для коллинеарных сегментов кривой. (а) Внутренние вершины определяющего многоугольника; (b) вершины в конце определяющего многоугольника.

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

То есть каждая функция базиса - это параллельный перенос другой функции, см. рис. 5-36.

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

Рис. 5-34 Выпуклая оболочка для кратных вершин, .

Рис. 5-35 Плавное превращение в отрезки прямой.

Рис. 5-36 Базисные функции периодического равномерного В-сплайна, , , .

Несколько примеров с целыми приращениями:

,

или для нормализованных приращений

Рис. 5-37 Базисные функции открытого равномерного В-сплайна, , , .

Формально открытый равномерный узловой вектор определяется как

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

В результате мы имеем кубическую кривую Безье - В-сплайн. Соответствующие базисные функции изображены на рис. 5-27b. На рис. 5-37 приведен еще один пример открытых базисных функций.

Неравномерные узловые векторы отличаются тем, что их внутренние узловые величины располагаются на разном расстоянии друг от друга и/или совмещаются.

Векторы могут быть периодическими или открытыми, например

,

На рис. 5.38b-е показаны примеры неравномерных базисных функций В-сплайна порядка . У соответствующих узловых векторов на концах находится по совмещенных одинаковых значений. Для сравнения на рис. 5-38а приведены базисные функции для открытого равномерного вектора. Отметим, что на рис. 5-38а и b функции симметричны, а также что у неравномерных базисов симметрия нарушается: 5-38с-е. Кроме того, при совмещенных узловых значениях у одной из функций появляется излом. На рис. 5-38d и е видно, что положение излома зависит от расположения совмещенного значения в узловом векторе.

Формула Кокса-де Бура (5-84) для расчета базисных функций В-сплайна рекурсивна, поэтому функция порядка зависит от базисных функций более низкого порядка вплоть до 1. Пусть дана базисная функция . Тогда эту зависимость можно выразить в виде треугольника

.

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

.

Рассмотрим пример расчета базисных функций.

Пример 5-9 Расчет периодических базисных функций Найти четыре базисные функции , , третьего порядка . Число в данном случае равно 4. Зависимость базисных функций для изображается следующей диаграммой: Рис. 5-38 Функции неравномерного базиса для , . Обратные зависимости для : . Каков диапазон узлового вектора, необходимый для этого расчета? Из уравнения (5-84) следует, что для вычисления необходимы узловые величины и , а для - и , т. е. необходимы значения от 0 до . Отсюда количество узловых значений равно . Узловой вектор для заданных периодических функций: где . Диапазон параметра . Используя уравнение (5-84) и приведенные выше диаграммы, получим базисные функции для различных значений параметра: ; ; , , ; ; , ; ; , , ; ; ; , ; ; , ; ; ; , ; ; , , ; ; ; , , ; , . Знак в определении приводит к тому, что при все функции равны 0. Результаты показаны на рис. 5-36 и 5-39с. Отметим, что каждая из базисных функций является кусочной параболической (квадратичной) кривой. Параболические сегменты на интервалах , , объединяются и составляют базисные функции . Каждая функция представляет собой параллельный перенос другой.

Пример 5-9 показывает, как построить базис по функциям базиса более низкого порядка. На рис. 5-39а изображены функции первого порядка из примера 5-9, на рис. 5-39b - второго порядка, и на рис. 5-39с - третьего порядка. Обратим внимание на то, как растягивается диапазон ненулевых значений функций с увеличением их порядка. Говорят, что функция базиса обеспечивает поддержку на интервале от до .

Внимательно рассматривая рис. 5-36, можно заметить важное свойство функций равномерного базиса. Из уравнения (5-85) известно, что для любого значения параметра . Отсюда следует, что все множество периодических базисных функций для определено только в диапазоне . За его границами . Для равномерного начинающегося с 0 узлового вектора с целыми приращениями пригодный диапазон параметра: . Для более общих или нормализованных векторов сокращение диапазона параметра соответствует потере интервала узловых значений на каждом конце вектора.

Рис. 5-39 Построение периодических базисных функций . (а) ; (b) ; (c).

Пример 5-10 Расчет открытого равномерного базиса Найти четыре базисные функции , , третьего порядка . Напомним, что формально открытый узловой вектор с целыми интервалами между внутренними узловыми значениями определяется как Диапазон изменения параметра , т. е. от 0 до максимального узлового значения. Как и в примере 5-9, количество узловых значений равно . Если брать узловые значения, то вектор для данного примера примет вид где . Параметр изменяется от 0 до 2. Пользуясь уравнениями (5-84) и диаграммами зависимости, получаем функции базиса для различных диапазонов параметра: ; ; ; ; , , ; ; ; , . Эти результаты приведены на рис. 5-40.

Сравнивая результаты примера 5-10 (рис. 5-40) и 5-9 (рис. 5-39), мы видим, что они существенно различаются для периодического и открытого равномерного узловых векторов. В частности, отметим, что у открытых равномерных узловых векторов на всем диапазоне изменения параметра определен полный набор базисных функций; т.е. для всех . У периодического вектора диапазон параметра уменьшается.

Рис. 5-40 Построение открытых базисных функций . (а) ; (b) ; (с) .

Пример 5-11 Расчет неравномерных базисных функций Найти пять базисных функций , , третьего порядка с узловым вектором , содержащим повторяющееся внутреннее узловое значение. Из уравнений (5-84) и диаграмм зависимости ; ; В частности, как следствие повторения узлового значения, для всех . ; ; , , ; ; , . Результат приведен на рис.5-38d. Заметим, что для всех значений имеем . Например, для , Аналогично для

Рис. 5-41 Зависимость формы В-сплайна от его порядка.

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

Гибкость базиса В-сплайна позволяет воздействовать на форму кривой разными способами:

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

Меняя порядок базисных функций.

Меняя количество и расположение вершин определяющего многоугольника.

Используя повторяющиеся вершины.

Используя повторяющиеся узловые значения в узловых векторах.

Рассмотрим эти способы сначала для открытых В-сплайнов, затем для равномерных периодических и неравномерных В-сплайнов.

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

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

Рис. 5-42 Влияние кратности вершины на форму В-сплайна, .

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

На рис. 5-42 изображается влияние повторяющихся или совпадающих вершин. Все В-сплайны имеют порядок . Нижняя кривая определена четырьмя вершинами с узловым вектором . У средней кривой пять определяющих вершин, причем две из них повторяются во второй вершине многоугольника . Узловой вектор - . Верхняя кривая определена шестью вершинами с тремя повторяющимися в точке . Узловой вектор - . Соответствующие многоугольники для трех кривых соответственно таковы: ; и .

Нижняя кривая состоит из единственного кубического сегмента. Средняя кривая состоит из двух сегментов, соединенных между и . Верхняя кривая состоит из трех сегментов: первый от до , второй от до середины между и , третий от этой точки до . Обратим внимание на то, что с увеличением кратности вершины кривая все ближе подходит к . Когда кратность достигается , возникает острый угол в соответствии со свойством выпуклой оболочки В-сплайнов. При внимательном изучении рис. 5-42 можно заметить, что на обеих сторонах кратной вершины имеется линейный участок.

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

Наконец, заметим, что у всех кривых наклон в концах одинаков.

На рис. 5-43 показаны три В-сплайна четвертого порядка. Каждый определяющий многоугольник состоит из восьми вершин. Кривые отличаются тем, что точка передвигается в и . Передвижение точки воздействует на кривую только локально: изменяются лишь сегменты, отвечающие отрезкам , и , .

Рис. 5-43 Локальная коррекция В-сплайна.

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

Для иллюстрации рассмотрим пример.

Пример 5-12 Расчет открытого В-сплайна Рассмотрим многоугольник из примера 5-7: , , , . Найти В-сплайн второго и четвертого порядка. Для открытый узловой вектор , где , , …, . Параметр изменяется от 0 до 3. Кривая состоит из трех линейных сегментов. Для функции базиса имеют вид: ; ; , , ; ; , . Для каждого из этих интервалов В каждом случае в результате получается уравнение прямой для ребра многоугольника, т.е. кривая совпадает с многоугольником. Последняя точка кривой требует особого внимания. Из-за того что интервал в уравнении (5-84а) открыт справа, все базисные функции при равны нулю. Следовательно, последняя точка многоугольника формально не лежит на кривой. Фактически же это не так. Рассмотрим , где - бесконечно малая величина. Если стремится к нулю, то в пределе последние точки кривой и многоугольника совпадают. На практике либо явно добавляют последнюю точку в описание кривой, либо определяют . Для порядок кривой совпадает с количеством вершин определяющего многоугольника, поэтому В-сплайн сводится к кривой Безье. Узловой вектор с . Функции базиса таковы: ; ; , , ; ; ; ; Из уравнения (5-83) получаем параметрический В-сплайн Итак, при Сравнивая с примером 5-7, видим, что результаты одинаковы. Получившаяся кривая изображена на рис. 5-28.

Рис. 5-44 Зависимость формы периодического В-сплайна от его порядка.

Теперь займемся периодическими В-сплайнами. На рис. 5-44 показаны три периодических В-сплайна разного порядка. Все кривые определены теми же вершинами, что и для открытых В-сплайнов на рис. 5-41. Для В-сплайн опять совпадает с определяющим многоугольником. Отметим, однако, что у периодического сплайна при первая и последняя точки на кривой не совпадают с первой и последней точками многоугольника. Наклон в первой и последней точках также может отличаться от наклона соответствующих сторон многоугольника. Для В-сплайн начинается в середине первого ребра и оканчивается в середине последнего, как отмечено стрелками. Это происходит из-за сокращения диапазона параметра для базисных функций периодического В-сплайна. Для периодический узловой вектор - с диапазоном параметра . Для периодический узловой вектор - с диапазоном параметра . Для периодический узловой вектор - с диапазоном параметра .

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

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

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

Рис. 5-45 Влияние кратности вершины на форму периодического В-сплайна, .

Пример 5-13 Расчет периодического В-сплайна Снова рассмотрим многоугольник на рис. 5-44. Вершины многоугольника - , , , . Найти периодический В-сплайн четвертого порядка , заданный этим многоугольником. Для на диапазоне узловой вектор для периодических базисных функций - . Для этого диапазона базисные функции первого порядка (см. уравнение (5-84а), : Из уравнения (5-84b) получаем базисные функции высших порядков: ; ; , , ; ; ; , , ; . , . Точка на В-сплайне при имеет вид Полная кривая приведена на рис. 5-44.

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

Первая вершина совпадает с последней. В-сплайн получается незамкнутым из-за ограниченного диапазона параметра. Здесь периодический равномерный узловой вектор: с диапазоном параметра .

Повторяя всего вершин в начале и/или конце замкнутого многоугольника, получаем замкнутый периодический В-сплайн. (Далее в этом разделе обсуждается другой метод в матричной формулировке.) Результат показан на рис. 5-46b, где определяющий многоугольник - с периодическим равномерным узловым вектором и диапазоном параметра . Альтернативные многоугольники или приводят к тому же самому результату.

На рис. 5-47 одна вершина многоугольника передвинута на другое место. Ее воздействие распространяется на сегменты кривой, соответствующие ребрам многоугольника по обе стороны от сдвинутой точки. На рис. 5-48 показан эффект кратной вершины . Область вокруг изображена более подробно. Опять отметим, что ее влияние распространяется также только на сегмента кривой по обе стороны кратной вершины.

Теперь рассмотрим неравномерные В-сплайны. На рис. 5-49 кривая изменяется под воздействием кратных внутренних узловых значений.

Рис. 5-46 Замкнутый периодический В-сплайн. (а) определяющий многоугольник; (b) - определяющий многоугольник.

Рис. 5-47 Изменение формы В-сплайна после перемещения одной вершины многоугольника.

Верхняя кривая третьего порядка рассчитана для открытого узлового вектора . Базисные функции для этой кривой изображены на рис. 5-38а. Нижняя кривая третьего порядка построена с неравномерным узловым вектором . Ее базисные функции - на рис. 5-38d.

Рис. 5-48 Влияние кратных вершин на форму замкнутого периодического В-сплайна.

Такая же кривая получается с неравномерным узловым вектором и базисными функциями на рис. 5-38е.

Из рис. 5-49 видно, что кратные внутренние узловые значения порождают излом в вершине . Кратное значение порождает ребро нулевой длины, поэтому уменьшается диапазон поддержки базисных функций. Далее, кратные внутренние узловые значения, в отличие от кратных вершин многоугольника, снижают дифференцируемость базисной функции в до , где равно кратности внутреннего узлового значения. Локально неравномерная кривая на рис. 5-49 непрерывная в окрестности , что и приводит к появлению угла.

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

, ,

, , (5-86)

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

Рис. 5-49 Неравномерные В-сплайны, . (а) ; (b) .

Рис. 5-50 Сравнение открытых неравномерных В-сплайнов: (a) равномерный узловой вектор; (b) неравномерный узловой вектор, пропорциональный длинам хорд; (c) неравномерный узловой вектор, пропорциональный длинам хорд, с двойной вершиной в .

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

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

Пример 5-14 Неравномерный В-сплайн Найти открытый В-сплайн третьего порядка, заданный точками , , , , с помощью неравномерного вектора с узловыми значениями, пропорциональными длинам ребер многоугольника. Сначала найдем длины хорд Их суммарная длина Из уравнения (5-86) получаем внутренние узловые значения . Узловой вектор имеет вид где , , …, . Диапазон параметра . Кривая состоит из трех параболических сегментов. Функции базиса для таковы ; ; , , ; ; ; , . Функции базиса для :, на единицу меньше количества вершин. Заметим, что уравнение (5-87) содержит только: и равны нулю. Используя это свойство, можно значительно сэкономить вычисления., кривой каждая базисная функция - кусочно кубическая, первая производная - кусочно параболическая, вторая производная - кусочно линейная. Третья производная разрывна и состоит из различных констант., .

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

Рассмотрим построение кубического сплайна. Пусть нам даны две соседние точки, через которые проведем кубический полином, но у полинома — 4 коэффициента, следовательно нужно еще два дополнительных условия или точки. Для этого прихватим еще две соседние точки. Чем более плавной мы хотим видеть линию, тем сложнее пройти точно через точки. Если в формуле x = q 3 , то достаточно плавности 3.

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

Рассмотрим . Пусть t — параметр, по которому пробегаем от точки P i к точке P i+1 . При t = 0 мы находимся в точке P i , при t = 1 — в точке P i+1 . Если 0 < t < 1, то мы находимся между P i и P i+1 .

Эта линия в каждой точке имеет систему:

x(t) = ((a 3 t + a 2)t + a 1)t + a 0 , для 0 <= t <= 1

y(t) = ((b 3 t + b 2)t + b 1)t + b 0 , для 0 <= t <= 1 a 3 = (-x i-1 + 3x i - 3x i+1 + x i+2)/6

A 2 = (x i-1 - 2x i + x i+1)/2

A 1 = (-x i-1 + x i+1)/2

A 0 = (x i-1 + 4x i + x i+1)/6

Точки b 3 - b 0 расписывают так же, но вместо x подставляют у. Между P i и P i+1 точки а и b не меняются. Если после последней точки указать первую точку, то система замкнет контур.

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

Следствия

Сглаживание B-сплайнами

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

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

Можно строить достаточно гладкие кривые и поверхности с использованием полиномов. Допустим, что мы хотим построить поверхность в виде графика функции z = z(x, y). Линия y = const на этой поверхности будет представлена линией z = z(x), она будет проходить через последовательность точек (x 0 , z 0), ..., (x i , z i), ..., (x n , z n) с x 0 < ... < x i < ... < x n . Наша цель — провести через эти точки составную кривую f(x), имеющую следующие свойства:

• на каждом подынтервале x i-1 <= x <= x i , i = 1, 2, ..., n функция f(x) является кубическим полиномом;
• ее первые и вторые производные непрерывны в узлах.

Полученная гладкая кривая называется кубическим сплайном. Термин «сплайн» возник по аналогии: это название чертежного инструмента — тонкой металлической линейки, которая может изгибаться так, чтобы проходить через заданные точки. Физически такая кривая минимизирует энергию внутренних напряжений. Математически — имеет минимальную среднеквадратичную кривизну, то есть она наиболее гладкая. Сплайны имеют много приложений в конструировании криволинейных форм. Однако они имеют и некоторые ограничения:

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

Первое ограничение можно устранить с помощью B-сплайна. Общая форма полученной в этом случае кривой показана на .

На этом рисунке сплайн продолжен от его конечных точек x i-4 , x i прямыми линиями, идущими вдоль оси x. В результате получается кубический сплайн на любом числе отрезков, но он не равен нулю только на четырех из них. Такая функция называется B-сплайном (или фундаментальным сплайном) четвертого порядка (или третьей степени). Про него говорят, что он имеет минимальный носитель (носитель — это число отрезков, на которых сплайн отличен от нуля).

Заметим, что кубический B-сплайн полностью определяется множеством узлов, на которых он определен, и только одной заданной величиной z. В более общем виде B-сплайн M mi (x) порядка m (или степени m - 1) на данном множестве узлов везде равен нулю, кроме m последовательных отрезков x i-m < x < x i . Опять-таки M mi (x) определяется множеством узлов и одной величиной z. Принято исключать последнюю степень свободы и фиксировать амплитуду B-сплайна некоторым стандартным образом.

Часто удобно для вычислений использовать нормализованный B-сплайн N mi (x), связанный с M mi (x) соотношением N mi (x) = (x i - x i-m)M mi (x).

Любой сплайн порядка m на множестве узлов x 0 , x 1 , ..., x n может быть выражен в виде линейной комбинации B-сплайнов, определенных на том же множестве узлов, расширенном (m - 1) дополнительными узлами на каждом из концов интервала, которые можно выбрать произвольно: x -m+1 , x -m+2 , ..., x -1 и x n+1 , ..., x n+m-1 . Можно построить m + n - 1 последовательных B-сплайнов на расширенном множестве узлов, каждый из которых отличен от нуля на m последовательных отрезках. Поэтому можно записать:
j (x) = S c i * M mi (x),
где j (x) — любой сплайн степени (m - 1) на первоначальном множестве узлов и M mi (x) есть B-сплайн на расширенном множестве узлов, отличный от нуля при x i-m < x < x i ; c i суть числовые коэффициенты; суммирование ведется по i = 1, ..., m + n - 1.

Если имеется множество векторов r 0 , r 1 , ..., r n , то можно использовать их: r(u) = S r i * N 4, i+1 (u) (суммирование ведется по i = 0, ..., n). Так как имеется (n + 1) векторных коэффициентов, то необходим набор из (n + 1) B-сплайнов. Последняя формула для 0 <= u <= n - 2 является уравнением кривой, образованной кубическими B-сплайнами.

Свойства

Некоторые простейшие свойства следуют из тождества S N 4, i+1 = 1, 0 <= u <= n - 2, i = 0..n. При u = 0 следует: r(0) = N 42 (0)(r 1 - r 0). Из этого следует, что если r 0 , r 1 , .., r n — вершины некоторой замкнутой ломанной, то кривая, построенная на основе B-сплайна, начинается в r 0 и ее касательная в этой точке имеет направление (r 1 - r 0). Аналогичное утверждение верно и для другого конца. Главное преимущество этого сплайна заключается в том, что изменение одной из вершин влечет за собой изменение только четырех отрезков кривой. Далее, мы также можем построить кривую, аппроксимирующую ломанную с любым желаемым числом сторон. Отрезок сплайна всегда лежит в выпуклой оболочке:

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

Имеется еще 2 полезных факта:

• кривая проходит вблизи средней точки каждой стороны, за исключением 1-ой и последней точками;
• при k = 2, ..., n - 2 кривая проходит через точки: 1/6r k-1 + 2/3r k + 1/6r k+1 = 2/3r k + 1/3(1/2(r k-1 + r k+1))

Эти точки, как показано на , лежат на 1/3 расстояния от r k на прямой, соединяющей r k с серединой отрезка между r k-1 и r k+1 .

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

Сущ., кол во синонимов: 1 функция (49) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

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

сплайн - (Spline) Математическая кривая, плавно соединяющая отдельные точки. Применяется для изображения контуров знаков [граница изображения знака]. См. также кривые Безье [метод описания веторных кривых] … Шрифтовая терминология

Кубический эрмитов сплайн сплайн, построенный из кубических полиномов с использованием эрмитовой интерполяции, в соответствии с которой интерполируемая функция задается не только своими значениями в n точках, но и ее первыми производными. Для… … Википедия

Приближенное представление функции или приближенное восстановление функции из заданного класса по неполной информации (напр., по значениям на сетке) с помощью сплайнов. Как и в классич. теории приближения функций, изучаются линейные методы С. а … Математическая энциклопедия

Интерполирование посредством сплайнов, т. е. построение интерполяционного сплайна (и. с.), принимающего в заданных точках {xi}заданные значения {f(xi)}, i=0, 1, . . ., n. Обычно и. с. удовлетворяют дополнительным условиям в концевых точках. Так,… … Математическая энциклопедия

Функция определенная на отрезке ,совпадающая на частичных отрезках [ х i, xi+1], образованных сеткой а=x0Математическая энциклопедия

сплайн - а, ч. Одна з елементарних функцій, включена у сучасний числовий аналіз … Український тлумачний словник

сплайн-апроксимація - іменник жіночого роду …

сплайн-інтерполяція - іменник жіночого роду … Орфографічний словник української мови

Книги

• Сплайн-всплески и их реализации , Бурова И.Г.. В данной книге основное внимание уделяется сплайн-всплесковым разложениям первого и второго порядка. Рассмотрены приемы разложения потоков в эрмитовом случае с использованием потока значений…

Условные переменные

Условная переменная представляет собой семафор, используемый для сигнализации о событии, которое произошло. Сигнала о том, что произошло некоторое событие, может ожидать один или несколько процессов (или потоков) от других процессов или потоков. Следует понимать различие между условными переменными и рассмотренными выше мьютексными семафорами. Назначение мьютексного семафора и блокировок чтения-записи - синхронизировать доступ к данным, в то время как условные переменные обычно используются для синхронизации последовательности операций. По этому поводу в своей книге UNIX Network Programming прекрасно высказался Ричард Стивенс (W. Richard Stevens): « Мьютексы нужно использовать для блокирования, а не для ожидания ».

В листинге 4.6 поток-«потребитель» содержал цикл:

15 while(TextFiles.empty())

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

Условная переменная имеет тип pthread_cond_t. Ниже перечислены типы операций, которые может она выполнять:

Инициализация;

Разрушение;

Ожидание;

Ожидание с ограничением по времени;

Адресная сигнализация;

Всеобщая сигнализация;

Операции инициализации и разрушения выполняются условными переменными подобно аналогичным операциям других мьютексов. Функции класса pthread_cond_t, которые реализуют эти операции, перечислены в табл. 5.7.

Таблица 5.7. Функции класса pthread_cond_t, которые реализуют операции условных переменных

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

pthread_mutex_lock(&Mutex) ;

pthread_cond_wait(&EventMutex, &Mutex);

pthread_mutex_unlock(&Mutex) ;

Итак, некоторая задача делает попытку заблокировать мьютекс. Если мьютекс уже заблокирован, то эта задача блокируется. После разблокирования задача освободит мьютекс Mutex и при этом будет ожидать сигнала для условной переменной EventMutex . Если мьютекс не заблокирован, задача будет ожидать сигнала неограниченно долго. При ожидании с ограничением по времени задача будет ожидать сигнала в течение заданного интервала времени. Если это время истечет до получения задачей сигнала, функция возвратит код ошибки. Затем задача вновь затребует мьютекс.

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

Условная переменная также имеет атрибутный объект, функции которого перечислены в табл. 5.8.

Таблица 5.8. Функции доступа к атрибутному объекту для условной переменной типа pthread_cond_t

Int pthread_condattr_init (pthread_condattr_t * attr) Инициализирует атрибутный объект условной переменной, заданный параметром attr, значениями, действующими по умолчанию для всех атрибутов, определенных реализацией;

Int pthread_condattr_destroy (pthread_condattr_t * attr) ; Разрушает атрибутный объект условной переменной, заданный параметром attr. Этот объект можно инициализировать повторно, вы-звав функцию pthread_condattr_init ()

Int pthread_condattr_setpshared (pthread_condattr_t * attr,int pshared);

Int pthread_condattr_getpshared (const pthread_condattr_t * restrict attr, int *restrict pshared); Устанавливает или возвращает атрибут process-shared атрибутного объекта условной переменной, заданного параметром attr. Параметр pshared может содержать следующие значения:

PTHREAD_PROCESS_SHARED (разрешает блокировку чтения-записи, разделяемую любыми потоками, которые имеют доступ к памяти, выделенной для этой условной переменной, даже если потоки принадлежат различным процессам);

PTHREAD_PROCESS_PRIVATE (Условная Переменная разделяется между потоками одного процесса)

Int pthread_condattr_setclock (pthread_condattr_t * attr, clockid_t clock_id);

Int pthread_condattr_getclock (const pthread_condattr_t * restrict attr, clockid_t * restrict clock_id); Устанавливает или возвращает атрибут clock атрибутного объекта условной переменной, заданного параметром attr . Атрибут clock представляет собой идентификатор часов, используемых для измерения лимита времени в функции pthread_cond_timedwait (). По умолчанию для атрибута clock используется идентификатор системных часов

Условную переменную можно использовать для реализации отношений синхронизации, о которых упоминалось выше: старт-старт (CC), финиш-старт (ФС), старт-финиш (СФ) и финиш-финиш (ФФ). Эти отношения могут существовать между потоками одного или различных процессов. В листингах 5.4 и 5.5 представлены примеры реализации ФС- и ФФ-отношений синхронизации. В каждом примере определено два мьютекса. Один мьютекс используется для синхронизации доступа к общим данным, а другой - для синхронизации выполнения кода.

// Листинг 5.4. ФС-отношения синхронизации между

// двумя потоками

pthread_t ThreadA,ThreadB;

pthread_cond_t Event;

void * worker1 (void *X) {

for(int Count = l;Count

pthread_mutex_lock(&Mutex);

pthread_mutex_unlock(&Mutex);

if(Number == 50){

pthread_cond_signal(&Event);

void * worker2 (void *X) {

pthread_mutex_lock(&EventMutex);

pthread_cond_wait(&Event,&EventMutex);

for(int Count = 1;Count

pthread_mutex_lock(&Mutex);

Number = Number + 20;

pthread_mutex_unlock(&Mutex);

cout « «Выполнение функции worker2 завершено.» « endl; return(0);

int main (int argc, char *argv) {

pthread_mutex_init(&Mutex,NULL);

pthread_mutex_init(&EventMutex,NULL);

pthread_cond_init(&Event, NULL);

pthread_create(&ThreadA, NULL, workerl, NULL);

pthread_create(&ThreadB, NULL, worker2 , NULL);

В листинге 5.4 показан пример реализации ФС-отношений синхронизации. Поток ThreadA не может завершиться до тех пор, пока не стартует поток ThreadB. Если значение переменной Number станет равным 50, поток ThreadA сигнализирует о этом потоку ThreadB. Теперь он может продолжать выполнение до самого конца Поток ThreadB не может начать выполнение до тех пор, пока не получит сигнал от потока ThreadA. Поток ThreadB использует объект EventMutex вместе с условной переменной Event. Объект Mutex используется для синхронизации доступа для записи значения разделяемой переменной Number. Для синхронизации различных событий и доступа к критическим разделам задача может использовать несколько мьютексов.

Пример реализации ФФ-отношений синхронизации показан в листинге 5.5.

// Листинг 5.5. ФФ-отношения синхронизации между // двумя потоками

pthread_t ThreadA, ThreadB ;

pthread_mutex_t Mutex, EventMutex;

pthread_cond_t Event;

void *workerl(void *X) {

for(int Count = l;Count

pthread_mu tex_l ock (&Mutex);

pthread_mutex_unlосk(&Mutex);

cout « «workerl: число равно "

pthread_mutex_lock(&EventMutex) ,-

cout « «Функция workerl в состоянии ожидания. " « endl;

pthread_cond_wait (&Event, &EventMutex) ;

pthread_mutex_unlock(&EventMutex);

void *worker2 (void *X) {

for(int Count = l;Count

pthread_mutex_lock(&Mutex) ;

Number = Number * 2 ;

pthread_mutex_unlock(&Mutex) ;

cout « «worker2: число равно " « Number « endl;

pthread_cond_signal (&Event) ;

cout « «Функция worker2 послала сигнал " « endl; return(0);

int main(int argc, char *argv) {

pthread_mutex_init (&Mutex,NULL) ;

pthread_mutex_init (&EventMutex,NULL) ;

pthread_cond_init (&Event, NULL) ;

pthread_create(&ThreadA, NULL,workerl, NULL);

pthread_create (&ThreadB, NULL, worker2, NULL) ;

В листинге 5.5 поток ThreadA не может завершиться до тех пор, пока не завершится поток ThreadB. Поток ThreadA должен выполнить цикл 10 раз, а ThreadB - 100. Поток ThreadA завершит выполнение своих итераций раньше ThreadB, но будет ожидать до тех пор, пока поток ThreadB не просигналит о своем завершении.

CC- и СФ-отношения синхронизации невозможно реализовать подобным образом. Эти методы используются для синхронизации пор я дка выполнени я процессов.