Обзор алгоритмов построения триангуляции Делоне

Авторы

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

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

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

Аннотация

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

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

Загрузки

Опубликован

2002-02-15

Выпуск

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

Раздел

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

Автор

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

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

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

  1. Делоне Б.Н. О пустоте сферы // Изв. АН СССР, ОМЕН. 1934, 4. 793-800.
  2. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек // Алгоритмы и программы. Вып. 10 (88). М., 1985. 3
  3. Ильман В.М. Экстремальные свойства триангуляции Делоне // Алгоритмы и программы. Вып. 10 (88). М., 1985. 57-66.
  4. Костюк Ю.Л., Грибель В.А. Размещение и отображение на карте точечных объектов // Методы и средства обработки сложной графической информации (тезисы докладов всесоюзной конференции). Часть II. Горький, 1988. 60-61.
  5. Кроновер Р.М. Фракталы и хаос в динамических системах. Основы теории / Пер. с англ. М.: Постмаркет, 2000.
  6. Ласло М. Вычислительная геометрия и компьютерная графика на C++ / Пер. с англ. М.: БИНОМ, 1997.
  7. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989.
  8. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского ун-та, 1998. 22-47.
  9. Фукс А.Л. Изображение изолиний и разрезов поверхности, заданной нерегулярной системой отсчетов // Программирование. 1986. 4. 87-91.
  10. Фукс А.Л. Предварительная обработка набора точек при построении триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Томского ун-та, 1998. 48-60.
  11. Bjorke J.T. Quadtrees and triangulation in digital elevation models // International Archives of Photogrammetry and Remote Sensing, International Society for Photogrammetry and Remote Sensing, Committee of the 16th International Congress of ISPRS, Commission IV. Part B4. 1988. 27. 38-44.
  12. Guibas L., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams // ACM Transactions on Graphics. 1985. 4, N 2. 74-123.
  13. Guttmann A., Stonebraker M. Using a relational database management system for computer aided design data // IEEE Database Engineering. 1982. 5, N 2. 21-28.
  14. Heller M. Triangulation algorithms for adaptive terrain modeling // Proc. of the 4th Intern. Symposium on Spatial Data Handling. 1990. 163-174.
  15. Lawson C. Software for C¹ surface interpolation // Mathematical Software III. NY: Academic Press, 1977. 161-194.
  16. Lawson C. Transforming triangulations // Discrete Mathematics. 1972. 3. 365-372.
  17. Lee D. Proximity and reachability in the plane. Techn. Report R-831. Coordinated Sci. Lab., Univ. of Illinois at Urbana. Urbana, 1978.
  18. Lee D., Schachter B. Two algorithms for constructing a Delaunay triangulation // Int. Jour. Comp. and Inf. Sc. 1980. 9, N 3. 219-242.
  19. Lewis B., Robinson J. Triangulation of planar regions with applications // The Computer Journal. 1978. 21, N 4. 324-332.
  20. Lingas A. The Greedy and Delaunay triangulations are not bad… // Lect. Notes Comp. Sc. 1983. 158. 270-284.
  21. Lloyd E. On triangulation of a set of points in the plain. MIT Lab. Comp. Sc. Tech. Memo. N 88. Boston, 1977.
  22. Manacher G., Zobrist A. Neither the Greedy nor the Delaunay triangulation of planar point set approximates the optimal triangulation // Inf. Proc. Let. 1977. 9, N 1. 31-34.
  23. McCullagh M.J., Ross C.G. Delaunay triangulation of a random data set for isarithmic mapping // The Cartographic Journal. 1980. 17, N 2. 93-99.
  24. Midtbo T. Spatial modeling by Delaunay networks of two and three dimensions. Dr. Ing. thesis. Department of Surveying and Mapping, Norwegian Institute of Technology, University of Trondheim. Trondheim, 1993.
  25. Shapiro M. A note on Lee and Schachter’s algorithm for Delaunay triangulation // Inter. Jour. of Comp. and Inf. Sciences. 1981. 10, N 6. 413-418.
  26. Sibson R. Locally equiangular triangulations // The Computer Journal. 1978. 21, N 3. 243-245.
  27. Watson D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes // The Computer Journal. 1981. 24, N 2. 167-172.