1. Книги
  2. Алгоритмы построения и анализа триангуляции
  • Издатель: Томск: Изд-во Том. ун-та
  • Страниц: 168
  • ISBN: 5-7511-2028-0
  • DOI: 10.17273/BOOK.2006.1

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

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

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

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

  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. Скворцов А.В. Построение сверхбольшой триангуляции Делоне // Изв. вузов. Физика. 2002. №6. С. 22-25.
  15. Скворцов А.В. Триангуляция Делоне и её применение. - Томск: Изд-во Том. ун-та, 2002. 128 с.
  16. Скворцов А.В., Костюк Ю.Л. Применение триангуляции для решения задач вычислительной геометрии // Геоинформатика: Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 127-138.
  17. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 22-47.
  18. Фукс А.Л. Изображение изолиний и разрезов поверхности, заданной нерегулярной системой отсчётов // Программирование. 1986. № 4. С. 87-91.
  19. Фукс А.Л. Предварительная обработка набора точек при построении триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 48-60.
  20. Agarwal P.K., Suri S. Surface approximation and geometric partitions // Proc. 5th ACM-SIAM Symp. on Discrete Algorithms. 1994. P. 24-33.
  21. Akeley K., Haeberli P., Burns D. The tomesh.c program / Technical Report SGI Developer's Toolbox CD. Silicon Graphics. 1990.
  22. Arkin E., Held M., Mitchell J., Skiena S. Hamiltonian triangulations for fast rendering // Second Annual European Symposium on Algorithms. Vol. 855. Springer-Verlag Lecture Notes in Computer Science, 1994. P. 36-47.
  23. Barber C.B., Dobkin D.P., Huhdanpaa H. The Quickhull Algorithm for Convex Hulls // ACM Transactions on Mathematical Software. 1994. Vol. 22, № 4. P. 469-483.
  24. Bern M., Eppstein D., Yao F. The expected extemes in a Delaunay triangulation // Inter. J. of Comp. Geom. and Appl. 1991. Vol. 1, № 1. P. 79-91.
  25. 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.
  26. Chang R.C., Lee R.C.T. On the average length of Delaunay triangulations//BIT. 1984. Vol. 24. № 3. P. 269-273.
  27. Edelsbrunner H., Seidel R. Voronoi diagrams and arrangements // Discrete and Computational Geometry. 1986. Vol. 8, № 1. P. 25-44.
  28. Evans F., Skiena S., Varshney A. Optimizing triangle strips for fast rendering//Proc. IEEE Visualization. 1996. P. 319-326.
  29. De Floriani L. A pyramidal data structure for triangle-based surface description//IEEE Comp. Graphics and Applications. 1989. Vol. 9, № 2. P. 67-78.
  30. De Floriani L., Falcidieno B., Nagy G., Pienovi C. On sorting triangles in a Delaynay tessellation//Algorithmica. 1991. № 6. P. 522-535.
  31. De Floriani L., Magillo P., Puppo E. Compressing Triangulated Irregular Networks//Geoinformatica. 2000. Vol. 1, № 4. P. 67-88.
  32. De Floriani L., Marzano P., Puppo E. Multiresolution Models for Topographic Surface Description//The Visual Computer. 1996. Vol. 12, № 7. P. 317-345.
  33. De Floriani L., Magillo P., Puppo E., Bertolotto M. Variable resolution operators on a multiresolution terrain model//ACM 4th Workshop on Advances in Geographic Information Systems. 1996. P. 123-130.
  34. Dillencourt M.B. Finding hamiltonian cycles in Delaunay triangulations is NP-complete // Canadian Conf. on Comput. Geometry. 1992. P. 223-228.
  35. Evans F., Skiena S.S., Varshney A. Completing sequential triangulations is hard / Technical Report, Department of Computer Science, State University of New York at Stony Brook, March 1996.
  36. Fowler R.J., Little J.J. Automatic extraction of irregular network digital terrain models//Computer Graphics. 1979. Vol. 13, № 3. P. 199-207.
  37. Gilbert P.N. New results on planar triangulations. Tech. Rep. ACT-15, Coord. Sci. Lab., University of Illinois at Urbana, July 1979.
  38. Graphics Library Programming Guide. Silicon Graphics, Inc. 1991.
  39. Guibas L., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams // ACM Transactions on Graphics. Vol. 4, № 2. 1985. P. 74-123.
  40. Guttmann A., Stonebraker M. Using a Relational Database Management System for Computer Aided Design Data // IEEE Database Engineering. 1982. Vol. 5, № 2.
  41. Heller M. Triangulation algorithms for adaptive terrain modeling // Proc. of the 4th Intern. Symp. on Spatial Data Handling, July 1990. P. 163-174.
  42. Kirkpatrik D.G. A note on Delaunay and optimal triangulations // Inform. Process. Lett. 1980. Vol. 10. P. 127-128.
  43. Kirkpatrik D.G. Optimal search in planar subdivisions // SIAM J. Comput., 1983. Vol. 12, № 1. P. 28-35.
  44. Kornmann D. Fast and simple triangle strip generation / Technical Report, Varian Medical Systems Finland, Espoo, 1999. 5 p.
  45. Lawson C. Software for surface interpolation//Mathematical Software III. NY: Academic Press, 1977. P. 161-194.
  46. Lawson C. Transforming triangulations//Discrete Mathematics. 1972. № 3. P. 365-372.
  47. Lee D. Proximity and reachability in the plane//Tech. Rep. N. R-831, Coordinated Sci. Lab. Univ. of Illinois at Urbana. 1978. 157 p.
  48. Lee D., Schachter B. Two algorithms for constructing a Delaunay triangulation//Int. Jour. Comp. and Inf. Sc. 1980. Vol. 9, № 3. P. 219-242.
  49. 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.
  50. Levcopoulos C. An lower bound for the nonoptimality of the greedy triangulation//Inform. Process. Lett. 1987. Vol. 25. P. 247-251.
  51. Levcopoulos C., Krznaric D. Quasi-greedy triangulations approximating the minimum weight triangulation//Tech. Rep. N. LU-CS-TR. Dept. of Computer Science, Lund University, Sweden. 1995. P. 95-155.
  52. Levcopoulos C., Krznaric D. Tight lower bounds for minimum weight triangulation heuristics//Inform. Process. Lett. 1996. Vol. 57. P. 129-135.
  53. Levcopoulos C., Lingas A. The greedy triangulation approximates the minimum weight triangulation and can be computed in linear time in the average case//Technical Report LU-CS-TR. Dept. of Computer Science, Lund University, Lund, Sweden, 1992. P. 92-105.
  54. Lewis B., Robinson J. Triangulation of planar regions with applications//The Computer Journal. 1978. Vol. 21, № 4. P. 324-332.
  55. Lingas A. The Greedy and Delaunay triangulations are not bad…//Lect. Notes Comp. Sc. 1983. Vol. 158. P. 270-284.
  56. Lloyd E. On triangulation of a set of points in the plain//MIT Lab. Comp. Sc. Tech. Memo. 1977. № 88. 56 p.
  57. 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, № 1. P. 31-34.
  58. McCullagh M.J., Ross C.G. Delaunay triangulation of a random data set for isarithmic mapping//The Cartographic Journ. 1980. Vol. 17, № 2. P. 93-99.
  59. 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.
  60. Mulzer W., Rote G. Minimum-weight triangulation is NP-hard//22nd Annual Symposium on Computational Geometry, 2006.
  61. Nagy G. Terrain visibility//Computers and Graphics. 1994. Vol. 18, № 6.
  62. Plaisted D.A., Hong J. A heuristic triangulation algorithm//J. Algorithms. 1987. Vol. 8. P. 405-437.
  63. Puppo E. Variable resolution triangulations//Computational Geometry. 1998. Vol. 11. P. 219-238.
  64. Santos F., Seidel R. A better upper bound on the number of triangulations of a planar point set//J. Combin. Theory Ser. A. 2003. Vol. 102. P. 186-193.
  65. Shapiro M. A note on Lee and Schachter's algorithm for Delaunay triangulation//Int. Jour. of Comp. and Inf. Sciences. 1981. Vol. 10, № 6. P. 413-418.
  66. Sibson R. Locally equiangular triangulations//Computer Journal. 1978. Vol. 21, № 3. P. 243-245.
  67. Sloan S.W. A fast algorithm for constructing Delaunay triangulations in the plane//Adv. Eng. Software. 1987. Vol. 9, № 1. P. 34-55.
  68. Speckmann B., Snoeyink J. Easy triangle strips for TIN terrain models//Proc. of 9th Canadian Conference on Comput. Geometry, 1997. P. 239-244.
  69. Stewart A.J. Tunneling for triangle strips in continuous Level-of-Detail meshes//Graphics Interface. 2001, June. P. 91-100.
  70. Touma G., Rossignac J. Geometric compression through topological surgery//ACM Transactions on Graphics. 1998. Vol. 17, № 2. P. 84-115.
  71. 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. № 134. P. 198-287.
  72. Watson D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes//The Computer Journal. 1981. Vol. 24, № 2. P. 167-172.