автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Исследование и применение рестриктивных В-сплайнов

ВВЕДЕНИЕ

Глава 1. В-СПЛАЙНЫ С РАЗРЫВНЫМИ ПРОИЗВОДНЫМИ.

1.1. Обзор существующих методов аппроксимации.И

1.2. В-сплайны с разрывными производными.

Случай одной переменной

1.3. В-сплайны с разрывными производными.

Случай двух переменных

1.4. Параметрические В-сплайны с разрывными производными

1.5. Связь между различными типами сплайнов и В-сплайнами с разрывными производными.

ВЫВОДЫ

Глава 2. РЕСТРИКТИВНЫЕ В-СПЛАЙНЫ.

2.1. Постановка задачи.

2.2. Случай одной переменной. Точный метод

2.3. Случай одной переменной. Приближенный метод

2.4. Случай двух переменных. Точный метод.

2.5. Случай двух переменных.Приближенный метод.

ВЫВОДЫ

Глава 3. ИСПОЛЬЗОВАНИЕ ПРЕДСТАВЛЕНИЯ ПОВЕРХНОСТИ С

ПОМОЩЬЮ В-СПЛАЙНОВ С УПРАВЛЯЮЩИМИ КОЭФФИЦИЕНТАМИ ПРИ ИМИТАЦИОННОМ МОДЕЛИРОВАНИИ ГИДРОАКУСТИЧЕСКИХ УСТОЙСТВ

3.1. Обзор существа вопроса.

3.2. Моделирование процесса излучения и распространения гидроакустического сигнала в воде.

3.3. Взаимодействие поля излучения с донной поверхностью.

3.4. Принимаемый сигнал.

3.5. Особенности реализации

ВЫВОДЫ.

Глава 4. ПРИМЕНЕНИЕ РЕСТРИКТИВНЫХ В-СПЛАЙНОВ В

ГЕОИНФОРМАЦИОННЫХ СИСТЕМАХ И В ЗАДАЧАХ МАШИННОЙ ГРАФИКИ.

4.1. Обзор методов представления рельефа в современных геоинформационных системах.

4.2. Особенности реализации рестриктивных

В-сплайнов на ЭВМ.

4.3. Применение рестриктивных В-сплайнов в ГИС ГрафИн.

4.4. Применение рестриктивных В-сплайнов в ГИС МарЬгРэ.

4.5. Применение рестриктивных В-сплайнов в задачах компьютерной графики.

ВЫВОДЫ.

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

В последнее время для аппроксимации таблично заданных функций широкое распространение получили различные сплайновые конструкции [2, 17, 22, 23, 25, 35, 57, 61, 62, 70, 79, 98]. Если аппроксимирующая функция должна проходить через точки исходного набора, то такая задача называется сплайн-интерполяцией [4, 7, 8, 13, 16, 17, 30, 37]. Если исходный набор данных содержит шумовую составляющую, то можно говорить о задаче сплайн-сглаживания. При этом условие прохождения сплайн-функции через точки исходного набора ставится не жестко, и график функции может проходить по некоторому коридору в окрестностях точек набора данных [8, 16,17, 30, 37].

В вычислительной практике наиболее удобными оказались сплайны, построенные на финитных функциях. В частности, на В-сплайнах [8, 16, 17, 57, 58]. С помощью таких конструкций решать задачу сплайн-аппроксимации удобнее, так как задача отыскания коэффициентов сплайна распадается на ряд подзадач меньшей размерности по нахождению коэффициентов локальных сплайнов.

Однако классический кубический сплайн в силу свойства экстремальности кубических сплайнов [8, 13] строит максимально гладкую функцию в классе дважды непрерывно дифференцируемых функций, что не всегда удовлетворяет требованиям задачи аппроксимации. Чтобы учесть априорные ограничения на вид аппроксимирующей функции, сплайновая конструкция должна содержать дополнительные регулирующие параметры. Такие конструкции существуют. Это, например, -сплайны [16, 17, 58], содержащие коэффициенты скоса и напряжения, или О-ЖЖВ Э-констру кции (использующие В-сплайны на неравномерной регулярной сетке), описанные в [84], допускающие регулировку таких параметров, как масса узла, энергия деформации в узле, сила, приложенная к узлу, и т.п.

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

Описанные выше типы сплайнов, допускающие регулировку формы аппроксимирующей функции посредством управляющих коэффициентов, участвующих в построении сплайн-функции, или посредством внешних сеток деформаций, не совсем удобны в том смысле, что управляющим коэффициентам не всегда можно придать четкий физический смысл. Например, в задачах моделирования рельефа океанского дна [6, 15, 28, 50, 73, 66, 96, 71, 92, 68, 93] часто априорно известна информация о средней кривизне и размерах неровностей. Заложить эту дополнительную информацию в сплайновую модель морского дна посредством дополнительных сеток деформаций или посредством ограничений на массу узлов не всегда возможно.

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

В работах Поддубного В.В. [38, 39] предлагается новый тип сплайнов, способных занимать промежуточное положение между сплайнами соседних дефектов. Конструкции этого типа сплайна обобщают известные и отличаются от них тем, что в условиях сопряжения элементов сплайна в его узлах вводятся ограничения типа неравенств на величину максимально допустимого скачка сопрягаемой производной соответствующего порядка. Обычные сплайны не содержат таких ограничений. Модифицированный таким образом сплайн предложено называть рестриктивным [38, 39].

Задача ограничения скачков производных сплайна и, как следствие, задача конструирования сплайна с плавно изменяющимися свойствами по отношению к сплайнам соседних дефектов до работ [38, 39] не ставилась.

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

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

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

Научная новизна. В работе получены следующие оригинальные результаты:

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

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

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

Работа выполнялась в соответствии с координационными планами важнейших НИР, проводимых в 1986-1995 гг. по заказам-нарядам Минвуза России (№№ гос. регистрации 01860125631, 01950001753), а также в соответствии с планами работ по Межвузовской научно-технической программе «Океанотех-ника» на 1993-1997 гг. [48]

На защиту выносятся следующие положения

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

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

Апробация результатов

Основные результаты диссертационной работы докладывались и обсуждались на следующих научно-технических форумах:

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

2. Третий Сибирский Конгресс по прикладной и индустриальной математике (INPRIM-98), Новосибирск, 1998.

3. Международная конференция «ГИС для оптимизации природопользования в целях устойчивого развития территорий» (ИНТЕРКАРТО-4), Барнаул, 1998.

4. The fourth International symposium on environmental geotechnology and global sustainable development, Boston, 1998.

5. The second Russian-Korean international symposium on science and technology, Tomsk, 1998.

Структура диссертации

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

Выводы

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

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

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

-113

ЗАКЛЮЧЕНИЕ

1. Предложен и исследован новый тип сплайнов - рестриктивные В-сплайны, по своим свойствам занимающие промежуточное положение между сплайнами соседних дефектов. Эти сплайны является дальнейшим развитием идеи рестриктивных сплайнов, предложенных в работах [38, 39]. От существующих типов сплайнов рестриктивные В-сплайны отличается возможностью регулировки ограничений на скачки производных в узлах, что позволяет плавно изменять гладкость аппроксимирующих функций.

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

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

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

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

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

Практические приложения рестриктивных В-сплайнов подтверждены тремя актами о внедрении.

- 115

1. Аммерал J1. Машинная графика на языке Си. Т. 1-4. - М: СолСистем, 1992.

2. Аронов Б.С. Методы математической обработки геологических данных на ЭВМ. М.: Недра, 1977. - 184 с.

3. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 490 с.

4. Бахвалов Н.С. Численные методы. Т. 1. -М.: Наука, 1973. 631 с.

5. Богородский A.B. и др. Гидроакустическая техника исследования дна океана. Л.: Гидрометеоиздат. 1984. - 270 с.

6. Бунчук A.B., Антокольский JIM. Полигональные исследования рассеяния звука дном с конкрециями с помощью приповерхностного локатора бокового обзора // Океанология. 1989. - № 5. - Т. 29. - С. 748-754.

7. Василенко В.А. Сплайн-функции: теория, алгоритмы, программы. Новосибирск: Наука, 1983. - 224 с.

8. Вершинин В.В., Завьялов Ю. С., Павлов H.H. Экстремальные свойства сплайнов и задача сглаживания. Новосибирск: Наука, 1998. - 101 с.

9. Вирт Н. Алгоритмы + структуры данных = программы / Пер. с англ. М.: Мир, 1985.-250 с.

10. Ю.Владимиров B.C. Уравнения математической физики. М: Наука, 1971. -512 с.

11. П.Ворошко П.П., Петренко О.Н. Полуавтоматическая триангуляция плоской области по заданным узлам // Алгоритмы и программы по расчету на прочность. 1980-№ 7. - С. 123-132.

12. Гроссман К., Каплан A.A. Нелинейное программирование на основе безусловной минимизации. Новосибирск: Наука, 1981 .-181с.

13. Де Бор К. Практическое руководство по сплайнам / Пер. с англ. М.: Радио и связь, 1985. - 303 с.-11614. Дьяконов К.Н., Касимов Н.С., Тикунов B.C. Современные методы географических исследований. М.: Просвещение, 1996. - 207с.

14. Житковский Ю.Ю. Рассеяние звука дном океана //Акустика океана. Современное состояние. М.: 1982. - С. 157-163.

15. Завьялов Ю.С., Квасов Б.И., Мирошниченко B.JL Методы сплайн-функций. -М.: Наука, 1981.-181 с.

16. Завьялов Ю.С., Jleyc В.А., Скороспелов В.А. Сплайны в инженерной геометрии. -М.: Машиностроение, 1985 . -221 с.

17. Зангвилл У. Нелинейное программирование. Единый подход / Пер. с англ. под ред. Е.Г. Голынтейна. М.:. Сов. Радио, 1973. - 312 с.

18. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек // Алгоритмы и программы. М.: ВИЭМС. 1985. - Вып. 10 (88). -С. 3-35.

19. Ильман В.М., Лебедев П.В. Пакет подпрограмм триангуляции плоских областей по нерегулярным сетям точек // Алгоритмы и программы. М.: ВИЭМС, 1985,-Вып. 10 (88). - С. 35-57.

20. Коровин В. П., Зарубежные технические средства в океанологии / Учебное пособие для студентов вузов. СПб.: Изд-во Рос. гос. Гидромет. ин-т, 1994. - 195 с.

21. Костюк Ю.Л. Применение сплайнов для изображения линий в машинной графике // Автоматизация эксперимента и машинная графика. Томск: Изд-во Том. ун-та, 1977. - С. 116-130.

22. Костюк Ю.Л., Фукс АЛ. Построение и аппроксимация изолиний однозначной поверхности, заданной набором исходных точек // Геоинформатика: Теория и практика. Томск: Изд-во Том. ун-та, 1998 - Вып. №1. - С. 119126.

23. Кошкарев A.B., Тикунов B.C. Геоинформатика. М.: Картгеоиздат-Геоиздат, 1993. -213 с.

24. Линник В.Г. Построение геоинформационных систем в физической географии. М.: Изд-во МГУ, 1990. - 80 с.

25. Лисин A.M. Обратные задачи гидролокационной съемки морского дна методом бокового обзора в условиях буксировки гидролокатора // Методика и техника сейсмоакустических и вибросейсмических исследований на акваториях. М.: Наука, 1986. - С. 66-81.

26. Лисицкий Д.В. Основные принципы цифрового картографирования местности. М.: Недра. 1988. - 261 с.

27. Лоран П.Ж. Аппроксимация и оптимизация / Пер. с франц. М.: Мир, 1975. - 496 с.

28. Мараховский Я.М., Тикунов B.C. Некоторые структуры для представления пространственных данных в географических информационных системах // Автоматизированная картография и геоинформатика. М.: Наука, 1991. - С. 41-63.

29. Марков Н.Г., Гаряев Р.И., Захарова A.A., Ковин Р.В., Черноусов М.В. Математический аппарат для построения тематических карт при изучении и использовании недр // Трансферные технологии в информатике. Томск: Изд-во ТПУ. - 1999. - Вып. 1. - С. 53-61.

30. Марков Н.Г., Захарова A.A., Ковин Р.В., Гаряев Р.И., Черноусов М.В. Приложения в среде ГИС Mapinfo для геологических и экологических исследований // Вестник Mapinfo. 1998. - № 2. - с. 33-38.

31. Томск: Изд-во. Том. ун-та, 1997. С. 211-212.

32. Михайлов А.Е., Корчуганов Н.И., Баранов Ю.Б. Дистанционные методы в геологии. М.: Недра, 1993. - 224 с.

33. Мудров А.Е. Численные методы для ПЭВМ. Томск: МП Раско, 1991. - 270 с.

34. Поддубный В.В. Методы инвариантного погружения и аппроксимации в ре-стриктивных задачах управления и фильтрации. Томск: Изд-во Том. ун-та, 1993.-271 с.

35. Поддубный В.В. Рестриктивные сплайны для обработки данных // Физика. -1992. -№ 9. -С. 128-135.

36. Поддубный В.В., Черноусов М.В. Имитационное моделирование систем сложных рельефов // Второй Сибирский Конгресс по прикладной и индустриальной математике (INPRIM-96): Тез. докл. Новосибирск: ИМ СО РАН, 1996. - С. 37.

37. Поддубный В.В., Черноусов М.В. Приближение сложных поверхностей с использованием аппарата рестриктивных В-сплайнов // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. - С. 107-118.

38. Прайт М., Фокс А. Вычислительная геометрия, М.: Мир, 1982. - 230 с.

39. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989. - 478 с.

40. Пьюкер Т. Влияние различных математических подходов на изображение рельефа дна океана // Картография. 1988. - № 3. - С 35-38.

41. Разработка компьютерного комплекса проектирования геоинформационной системы гидроакустического зондирования дна океана: Отчеты по НИР «ГИС-Гидрозонд» / Научный руководитель НИР Поддубный В.В. Томск: Изд-во Том. ун-та, 1993-1997.

42. Роджерс Д., Адаме Дж. Математические основы машинной графики / Пер. с англ. М.: Машиностроение, 1980. - 204 с.

43. Саголевич A.M., Римский-Корсаков H.A., Павлов Р.Б., Компьютерные детальные исследования поверхности дна на шельфе Мексиканского залива с использованием подводных аппаратов // Океанология. 1994. - Т. 3. - № 6, -С. 924-927.

44. Скворцов A.B. Графическая интегрированная система ГрафИн // Томский государственный университет. Научно-технические разработки. Каталог. -Томск: Изд-во Томского ЦНТИ, 1998. С. 90.

45. Фукс А.Л. Изображение изолиний и разрезов поверхности, заданной нерегулярной системой отсчетов // Программирование. 1986. -№ 4. - С. 87-91.

46. Хаксхолл В. Введение в городские информационные системы / Пер. с англ. -М.: Русское издательство АГИТ, 1996. 325 с.

47. Цветков В.Я. Геоинформационные системы и технологии. М.: Финансы и статистика, 1998. - 288 с.

48. Цикритзис Д., Лоховский Ф. Модели данных. М.: Финансы и статистика, 1985.-343 с.

49. Шендеров А.В. Волновые задачи гидроакустики. JL: Судостроение, 1972. -352 с.

50. Шикин Е.В., Боресков А.В. Компьютерная графика. М: Диалог-МИФИ, 1985.-288 с.

51. Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. — М: Диалог-МИФИ, 1996. 240 с.

52. Akima H. A method of bivariate interpolation and smooth surface fitting for irregularly distributed data points // ACM Trans, for Math. Software. 1978. - No. 4.-P. 148-159.

53. Allgower E., Quesenberry N. Automatic Triangulations of Bounded Regions in R2 // Z. Angew. Math, und Mesh. 1982. - V. 62. - No. 5. - P. 314-316.

54. ARC/INFO User's Guide: ARC/INFO Data Model, Concepts, & Key Terms . -NY: ESRI. 1992. - 298 p.

55. ARC/INFO User's Guide: Cell-based Modeling With GRID. NY: ESRI. - 1992. -305 p.

56. ARC/INFO User's Guide: Surface Modeling With TIN. NY: ESRI. - 1992. -240 p.

57. Atteia M. Fonctions-spline avec contraintes lineaires type inégalité // 6 e Congres de L'AFIRO 1967. - P. 1.42-1.54.

58. Bentley J., Fridman J. Data Structures for Range Searching // Computing Surveys 1979. - V. 11.-No. 2.-P. 121-138.

59. Cloef R. L., Edwards C.R. The Bathyscan precision swathe sound // Ocean 86, Conf. Washington - 1986. - V.l - P. 153-152.

60. Hamann В., Trotts I.J., Farin G.E. On Approximating Contours of the Piecewise Trilinear Interpolant Using Triangular Rational-Quadratic Bezier Patches // IEEE Transactions on Visualization and Computer Graphics. 1997. - V.3. - No. 3. -P. 215-227.

61. Henderson T.L., Lacker S.G. Seafloor profiling by a wideband sonar: simulation , frequency-response optimization, and result of brief sea test // IEEE J. Ocean Ing. 30-5.-V. 14.-P. 94-107.

62. Herzen B. and Barr A.H. Accurate triangulations of deformed, intersecting surfaces // Computer & Graphics. 1987. - V.21. - No. 4. - P. 103-110.

63. Keinz W. A classification of digital map data models. EURO-CARTO VI, Proc. - 1987. -P.105-113.

64. Kenyon N., Limonov A., Sidescan Sonar Survey Ocean Sonographs // UNESCO Repts. Mar. Sc. - 1994. - No. 64. - P. 22-23.

65. Kirkpatrick D. A note on Delaunay and optimal triangulations // Inf. Proc. Lett. -1980.-V. 10. -No. 3. -P. 127-128.

66. Knobles D.P., Vidmar P.J. Simulation of bottom interacting waveforms // The journal of Acoustical Society of America. 1986. - No. 6. - V. 79. - P. 17601766.

67. Lawsson G. Software for C1 surface interpolation // Mathematical Software III. -NY: Academic Press. 1977. - P. 161-194.

68. Lee D., Schachter B. Two algorithms for constructing a Delaunay triangulation // Int. Jour. Comp. And Inf. Sc. 1980. - V. 9. - No. 3. - P. 219-242.

69. Lee S., Wolberg G., Shin S.Y. Scattered Data Interpolation with Multilevel B-Splines // IEEE Transactions on Visualization and Computer Graphics. 1997. -V.3.-NO. 3,-P. 228-244.

70. Lewis B., Robinson J. Triangulation of planar regions with applications // The Computer Journal. 1978. - V. 21. - No. 4. - P. 324-332.

71. Lingas A. The Greedy and Delaunay triangulation are not bad // Lect. Notes Comp. Sc. 1983. - V. 158. - P. 270-284.

72. Maplnfo User's Guide. Maplnfo Corp. - 1995. - 252 p.

73. Markov N.G., Zakharova A.A., Kovin R.V., Garjaev R.I., Chernousov M.V. Gis-technologies for geoecology and hydrology // Abstracts of the second Russian-Korean international symposium on science and technology. Tomsk: TPU. -1998.-P. 251.

74. Nievergelt J., Hinterberger H., Sevcik K. The grid file: an adaptable, symmetric multikey file structure // ACM Trans. On Database Systems. 1984. - V. 9. - No. 1.-P. 38-71.

75. Oxley A. Surface fitting by triangulation // Computer Journal. 1985. - V. 28. -No. 3.-P. 243-245.

76. Qin H., Terzopoulos D. D-NURBS: A Physics-Based Framework for Geometric Design // IEEE Transactions on Visualization and Computer Graphics. 1996. -V. 2.-No. l.-P. 85-90.

77. Quak, E., Schumaker L.L., Cubic Spline Fitting using Data Dependent Triangulations // Computer Aided Geometric Design. 1990. - No. 7. - P. 293-301.

78. Rippa S., Adaptive Approximation by Piecewise Linear Polynomials on Triangulations of Subsets of scattered Data // SIAM Journal of Sci. Stat. Comput. 1992. - V.5.-NO. 5.-P. 1123-1141.

79. Rossignac J.R., Requicha A.A.G., Constructive Non-Regularized Geometry // Computer Aided Geometry. 1991. - V. 23. - No. 1. - P. 21-32.

80. Schoenberg I.J. Contribution to the problem of approximation of equidistant data by analytic function // Quart. Appl. Math. 1946. - V. 4. - P. 45-99.

81. Schoenberg I.J. Spline functions and problem of graduation // Proc. Nat. Acad. Sci. 1964. - V. 52. - P. 947-950.

82. Sibson R. Locally equangular triangulations // Computer Journal. 1978. - V. 21. -No. 3.-P. 243-245.

83. Subodh K. and Dinesh M. and Anselmo L. Interactive Display of Large NURBS Models // IEEE Transactions on Visualization and Computer Graphics. 1996. -V.2. - No 4. - P. 323-336.-123

84. Tassev V.T., Side Scan Sonar And Sub-Bottom Profiler For Deep Sea Investigation // Imaem'87, 4th Cong. Varnu - 1987. - V. 3. - P. 105.

85. Tyce R., Miller J., Deep ocean pathfinding high resolution mapping and navigation // Ocean 86, Conf. Washington 86. - 1986. - V. 1. - P. 163-168.

86. Wang C.A., Efficiently Updating Constrained Delaunay Triangulations // BIT. -1993.-V. 33.-P. 238-252.

87. Watson D. F., Computing the «-dimensional Delaunay tessellation with applications to Voronoi polytopes // The Computer Journal. 1981. - V.24. - P. 167-171.

88. Westwood E.K., Tindle C.T. Shadow water time-serials simulation using ray theory // The journal of Acoustical Society of America. 1987. - V. 81. - No. 6. - P. 1752-1761.

89. Wolfe R.N., Wesley M.A., Kyle J.C., Gracer F., Fitzgerald W.J., Solid Modeling for Production Design // IBM Journal of Research and Development. 1997. -V.31. - No. 3. - P. 277-295.

90. Yamaguchi Y., Kimura F., Geometric Modeling with Generalized Topology and Geometry for Product Engineering // Product Modeling for Computer-Aided Design. North Holland. - 1991 - P. 103-112.

91. Zhou J.M., Zhou K.D., Shao K.R. Automatic generation of 3D Meshes for Complicated Solids // IEEE transactions on magnetics. 1992. - V.28. - No. 2, March. -P. 312-321.

92. Утверждаю» Президент Panopticum, LLC Oleg Okhrimets7» 1999r.1. АКТ О ВНЕДРЕНИИрезультатов диссертационной работы Черноусова М.В. «Исследование и применение рестриктивных В-сплайнов»

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

94. Нач. отдела Мае адаптации Колесов И.Б.

95. Нач. коммерческого отдела Атапин Ю.Ю-Щ^шского политехнического

96. УТВЕРЖДАЮ» Директор института -Кибернетический центрущверситета |J||M1 В.З. Ямпольский */Шн~» 1999 г.1. АКТо внедрении НИОКР

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

98. Зав. кафедрой Вычислительной техники O/rO-^^vH Г Mmwrm

99. Программист лаборатории ГИС

100. Программист лаборатории ГИС1. Р.В. Ковин

101. Утверждаю» директор НПО «Сибгеоинформатика»1. АКТ О ВНЕДРЕНИИ1. Рюмкин А.И., .результатов диссертационной работ ы Черноусова М. В.

102. Исследование и применение рестриктивных В-сплайнов»

103. Зам. директора, к.т.н., доцент /^-¿¿х^— Макиенко А.Д.

104. Ведущий программист, к.т.н.1. Скворцов А.В.