• Издатель: Томск: Изд-во Том. ун-та
• Страниц: 128
• ISBN: 5-7511-1501-5
• DOI: 10.17273/BOOK.2002.1

Триангуляция Делоне и её применение

• Скворцов А.В., д.т.н., профессор, профессор ТГУ (г. Томск), генеральный директор ООО «ИндорСофт» (г. Томск)

В книге рассматриваются триангуляция Делоне и её обобщение – триангуляция Делоне с ограничениями. Приводятся 5 вариантов структуры данных, 4 способа проверки условия Делоне, 4 группы алгоритмов построения триангуляции Делоне (всего 28 алгоритмов) с оценками трудоемкости, 4 алгоритма построения триангуляции Делоне с ограничениями. Рассматривается применение триангуляции Делоне с ограничениями для решения задач пространственного анализа на плоскости (оверлеи, буферные зоны, зоны близости) и моделирования рельефа (построение изолиний, изоконтуров, зон видимости, расчет объемов земляных работ). Описывается структура триангуляции переменного разрешения, используемая для моделирования рельефа, рассматриваются некоторые алгоритмы ее построения. Рекомендуется специалистам, занимающимся разработками в области ГИС и САПР. Может быть использована студентами, изучающими машинную графику, вычислительную геометрию и геоинформатику.

Описание по ГОСТ 7.1−2003

Скворцов А.В. Триангуляция Делоне и её применение [Текст]  — Томск: Изд-во Том. ун-та, 2002. — 128  c. — ISBN 5-7511-1501-5.

Ссылка по ГОСТ Р 7.0.5−2008

Скворцов А.В. Триангуляция Делоне и её применение. Томск: Изд-во Том. ун-та, 2002. 128 с.

Ссылка в формате BiBTeX

@BOOK{Skvortsov2002-Trn,
   author = "Скворцов, А.В.",
   title = "Триангуляция Делоне и её применение",
   publisher = "Изд-во Том. ун-та",
   address = "Томск",
   year = 2002,
   isbn = "5-7511-1501-5",
   language = russian
}

Ссылка на PDF

http://www.indorsoft.ru/books/2002/SkvortsovAV-2002-01.Book(Trn).pdf

Используемая литература

1. Делоне Б.Н. О пустой сфере // Изв. АН СССР. ОМЕН. 1934. № 4. С. 793-800.
2. Жихарев С.А., Скворцов А.В. Моделирование рельефа в системе ГрафИн // Геоинформатика: Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 194-205.
3. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек // Алгоритмы и программы. ВИЭМС. Вып. 10 (88). М., 1985. С. 3-35.
4. Ильман В.М. Экстремальные свойства триангуляции Делоне // Алгоритмы и программы. ВИЭМС. Вып. 10(88). М., 1985. С. 57-66.
5. Костюк Ю.Л., Грибель В.А. Размещение и отображение на карте точечных объектов // Методы и средства обработки сложной графической информации: Тезисы докладов Всесоюзной конференции. Ч. 2. Горький, 1988. С. 60-61.
6. Костюк Ю.Л., Фукс А.Л. Визуально гладкая аппроксимация однозначной поверхности, заданной нерегулярным набором точек // Геоинформатика-2000: Труды Международной научно-практической конференции. Томск: Изд-во Том. ун-та, 2000. С. 41-45.
7. Костюк Ю.Л., Фукс А.Л. Гладкая аппроксимация изолиний однозначной поверхности, заданной нерегулярным набором точек // Геоинформатика-2000: Труды Международной научно-практической конференции. Томск: Изд-во Том. ун-та, 2000. С. 37-41.
8. Костюк Ю.Л., Фукс А.Л. Приближенное вычисление оптимальной триангуляции // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 61-66.
9. Кошкарёв А.В., Тикунов В.С. Геоинформатика. М.: Картгеоиздат-Геодезиздат, 1993. 213 с.
10. Кроновер Р.М. Фракталы и хаос в динамических системах. Основы теории / Пер. с англ. М.: Постмаркет, 2000. 352 с.
11. Ласло М. Вычислительная геометрия и компьютерная графика на C++ / Пер. с англ. М.: БИНОМ, 1997. 304 с.
12. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989. 478 с.
13. Роджерс Д., Адамс Дж. Математические основы машинной графики / Пер. с англ. М.: Машиностроение, 1980. 204 с.
14. Скворцов А.В., Костюк Ю.Л. Применение триангуляции для решения задач вычислительной геометрии // Геоинформатика: Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 127-138.
15. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 22-47.
16. Фукс А.Л. Изображение изолиний и разрезов поверхности, заданной нерегулярной системой отсчётов // Программирование. 1986. № 4. С. 87-91.
17. Фукс А.Л. Предварительная обработка набора точек при построении триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 48-60.
18. Agarwal P.K., Suri S. Surface approximation and geometric partitions // Proc. 5th ACM-SIAM Symp. on Discrete Algorithms. 1994. P. 24-33.
19. Bjørke J.T. Quadtrees and triangulation in digital elevation models // International Archives of Photogrammetry and Remote Sensing, 16th Intern. Congress of ISPRS, Commission IV. Part B4. 1988. Vol. 27. P. 38-44.
20. Evans F., Skiena S., Varshney A. Optimizing triangle strips for fast rendering//Proc. IEEE Visualization. 1996. P. 319-326.
21. De Floriani L. A pyramidal data structure for triangle-based surface description//IEEE Comp. Graphics and Applications. 1989. Vol. 9, № 2. P. 67-78.
22. De Floriani L., Falcidieno B., Nagy G., Pienovi C. On sorting triangles in a Delaynay tessellation//Algorithmica. 1991. № 6. P. 522-535.
23. De Floriani L., Magillo P., Puppo E. Compressing Triangulated Irregular Networks//Geoinformatica. 2000. Vol. 1, № 4. P. 67-88.
24. De Floriani L., Marzano P., Puppo E. Multiresolution Models for Topographic Surface Description//The Visual Computer. 1996. Vol. 12, № 7. P. 317-345.
25. Fowler R.J., Little J.J. Automatic extraction of irregular network digital terrain models//Computer Graphics. 1979. Vol. 13, N 3. P. 199-207.
26. Gilbert P.N. New results on planar triangulations. Tech. Rep. ACT-15, Coord. Sci. Lab., University of Illinois at Urbana, July 1979.
27. Guibas L., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams // ACM Transactions on Graphics. Vol. 4, N 2. 1985. P. 74-123.
28. Guttmann A., Stonebraker M. Using a Relational Database Management System for Computer Aided Design Data // IEEE Database Engineering. 1982. Vol. 5, N 2.
29. Heller M. Triangulation algorithms for adaptive terrain modeling // Proc. of the 4th Intern. Symp. on Spatial Data Handling, July 1990. P. 163-174.
30. Kirkpatrik D.G. Optimal search in planar subdivisions // SIAM J. Comput., 1983. Vol. 12, N 1. P. 28-35.
31. Lawson C. Software for surface interpolation // Mathematical Software III. NY: Academic Press, 1977. P. 161-194.
32. Lawson C. Transforming triangulations // Discrete Mathematics. 1972. N 3. P. 365-372.
33. Lee D. Proximity and reachability in the plane//Tech. Rep. N. R-831, Coordinated Sci. Lab. Univ. of Illinois at Urbana. 1978.
34. Lee D., Schachter B. Two algorithms for constructing a Delaunay triangulation // Int. Jour. Comp. and Inf. Sc. 1980. Vol. 9, N 3. P. 219-242.
35. Lee J. Comparison of existing methods for building triangular irregular network models of terrain from grid digital elevation models//Int. Journal of GIS. 1991. Vol. 5, № 3. P. 267-285.
36. Lewis B., Robinson J. Triangulation of planar regions with applications//The Computer Journal. 1978. Vol. 21, N. 4. P. 324-332.
37. Lingas A. The Greedy and Delaunay triangulations are not bad… // Lect. Notes Comp. Sc. 1983. Vol. 158. P. 270-284.
38. Lloyd E. On triangulation of a set of points in the plain // MIT Lab. Comp. Sc. Tech. Memo. 1977. № 88. 56 p.
39. Manacher G., Zobrist A. Neither the Greedy nor the Delaunay triangulation of planar point set approximates the optimal triangulation//Inf. Proc. Let. 1977. Vol. 9, N. 1. P. 31-34.
40. McCullagh M.J., Ross C.G. Delaunay triangulation of a random data set for isarithmic mapping//The Cartographic Journ. 1980. Vol. 17, N. 2. P. 93-99.
41. Midtbø 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, February 1993.
42. Nagy G. Terrain visibility // Computers and Graphics. 1994. Vol. 18, N. 6.
43. Puppo E. Variable resolution triangulations//Computational Geometry. 1998. Vol. 11. P. 219-238.
44. Shapiro M. A note on Lee and Schachter's algorithm for Delaunay triangulation // Inter. Jour. of Comp. and Inf. Sciences. 1981. Vol. 10, N. 6. P. 413-418.
45. Sibson R. Locally equiangular triangulations//Computer Journal. 1978. Vol. 21, N. 3. P. 243-245.
46. Sloan S.W. A fast algorithm for constructing Delaunay triangulations in the plane // Adv. Eng. Software. 1987. Vol. 9, N. 1. P. 34-55.
47. Touma G., Rossignac J. Geometric compression through topological surgery // ACM Transactions on Graphics. 1998. Vol. 17, N. 2. P. 84-115.
48. Voronoi G. Nouvelles applications des parameters continues à la therie des formes quadratiques. Deuxième Mémorie: Recherches sur les parralléloèddres primitifs // J. reine angew. Math. 1908. N. 134. P. 198-287.
49. Watson D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes // The Computer Journal. 1981. Vol. 24, N. 2. P. 167-172.