Алгоритмы построения триангуляции с ограничениями

Авторы

  • А.В. Скворцов

Ключевые слова:

триангуляция Делоне
вычислительная устойчивость
вычислительная геометрия
машинная графика
геоинформационные системы
итеративные алгоритмы
выпуклая триангуляция

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2002-03-11

Выпуск

Том 3 (2002): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

А.В. Скворцов

Томский государственный университет,
Институт прикладной математики и компьютерных наук
пр. Ленина, 3, 634050, г. Томск

Библиографические ссылки

  1. Делоне Б.Н. О пустоте сферы // Изв. АН СССР, ОМЕН. 1934. 4. 793-800.
  2. Костюк Ю.Л., Фукс А.Л. Приближенное вычисление оптимальной триангуляции // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского гос. ун-та, 1998. 61-66.
  3. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989.
  4. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. 3. 14-39 (http://num-meth.srcc.msu.su).
  5. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского гос. ун-та, 1998. 22-47.
  6. Gilbert P.N. New results on planar triangulations. Tech. Rep. ACT-15. Coord. Sci. Lab., University of Illinois at Urbana. Urbana, 1979.
  7. Guttmann A., Stonebraker M. Using a relational database management system for computer aided design data // IEEE Database Engineering. 1982. 5, N 2. 21-28.