Исследование и разработка высокопроизводительного алгоритма построения цифровых моделей рельефа тема диссертации и автореферата по ВАК РФ 25.00.35, кандидат технических наук Нгуен Тхе Конг

• Нгуен Тхе Конг
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Нгуен Тхе Конг

ВВЕДЕНИЕ.

ГЛАВА 1. ОБОБЩЕНИЕ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

1.1. ПОНЯТИЕ О ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА.

1. 2. МЕТОДЫ ПРЕДСТАВЛЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА

1.2. 1. Регулярные модели данных (GRID).

1.2. 1. 1. Метод Кригинга (Kriging).

1.2. 1.2. Метод радиальных базисных функций.

1.2. 1.3. Метод обратных расстояний.

1.2.1.4. Метод Шепарда (Shepard).

1.2. 1.5. Метод естественного соседа.

1. 2. 2. Триангуляционная модель данных (TIN).

1.3. ПРИМЕНЕНИЕ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

ГЛАВА 2. АНАЛИЗ АЛГОРИТМОВ ПОСТРОЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

2. 1. ОБОБЩЕННЫЙ МЕТОД ВОРОНОГО-ДЕ ЛОНЕ.

2.1.1. Триангуляция Делоне.

2. 1. 1. 1. Определение триангуляции Делоне.

2. 1. 1.2. Проверка условия Делоне.

2. 1.2. Диаграмма Вороного.

2. 1.3. Связь между диаграммой Вороного и триангуляцией Делоне.

2. 1.4. Метод Вороного-Делоне.

2. 2. АЛГОРИТМ ИНКРЕМЕНТА (INCREMENTAL).

2. 2. 1. Обобщенный алгоритм.

2. 2. 2. Анализ алгоритма.

2. 2. 3. Методы повышения быстродействия вычисления.

2. 2. 4. Вычислительный алгоритм.

2.3. АЛГОРИТМ ЗАМЕТАЮЩЕЙ ЛИНИИ (SWEEP-LINE).

2.3. 1. Обобщенный алгоритм.

2.3.2. Структура данных.

2.3.3. Вычислительный алгоритм.

2. 3. 4. Анализ алгоритма.

2.4. КОМБИНАЦИЯ АЛГОРИТМОВ ИНКРЕМЕНТА И

ЗАМЕТАЮЩЕЙ ЛИНИИ.

2.4. 1. Обобщенный алгоритм.

2. 4. 2. Вычислительный алгоритм.

2. 4. 3. Структура данных.

2. 4. 4. Анализ алгоритма.

2.5. ВЫВОДЫ ПО ГЛАВЕ.

ГЛАВА 3. РАЗРАБОТКА ПРОГРАММЫ ПОСТРОЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

3. 1. БЛОК-СХЕМЫ АЛГОРИТМОВ В ПРОГРАММЕ.

3. 1. 1. Блок-схема алгоритма инкремента (рис. 3.1).

3. 1.2. Блок-схема алгоритма заметающей линии (рис. 3.2).

3.1.3. Блок-схема комбинации алгоритмов инкремента и заметающей линии (рис. 3.3).

3.2. ПРОЕКТИРОВАНИЕ СТРУКТУР ДАННЫХ.

3.3. ЭКСПЕРИМЕНТАЛЬНЫЕ АЛГОРИТМЫ.

3.3.1. Экспериментальные качества алгоритмов.

3.3.2. Экспериментальные скорости алгоритмов.

3.4. СОЗДАНИЕ ПРИКЛАДНЫХ ИНСТРУМЕНТОВ.

3. 4. 1. Интерполяция высот.

3. 4. 2. Построение профилей.

3. 4. 3. Построение изолиний (горизонталей).

3. 4. 4. Построение изоконтуров.

3. 4. 5. Построение изоклин.

3. 4. 6. Расчет объемов земляных работ.

Введение диссертации (часть автореферата) на тему «Исследование и разработка высокопроизводительного алгоритма построения цифровых моделей рельефа»

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

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

Для получения ЦМР на большие территории наиболее эффективным решением является обработка космических снимков, лазерная локация.

Данное исследование посвящено разработке технологии анализа и вычисления алгоритмов построения цифровых моделей рельефа.

Актуальность темы.

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

Актуальность применения ЦМР объясняется прежде всего тем, что ЦМР обеспечивает большую наглядность и интерпретируемость данных, предоставляет возможность наиболее полно передавать информацию об изменениях объектов и исследуемой среды с течением времени, а также позволяет реализовать ряд прикладных задач, недоступных для решения с использованием двумерных данных.

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

Цель и основные задачи исследования.

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

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

2. Исследование алгоритмов инкремента и заметающей линии для построения триангуляции Делоне.

3. Предложение методов повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

4. Разработка высокопроизводительного алгоритма построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.

5. Исследование алгоритмов анализа поверхностей: построение профилей; построение горизонталей; построение изоконтуров; построение изоклин; расчет объемов земляных работ.

6. Разработка программы построения цифровых моделей рельефа с прикладными инструментами для реализации разработки алгоритмов.

Научная новизна работы.

Исследованы алгоритмы инкремента и заметающей линии для построения триангуляции Делоне.

Предложены методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

Разработан новый высокопроизводительный алгоритм построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.

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

Положения, выносимые на защиту.

1. Алгоритмы инкремента и заметающей линии построения триангуляции Делоне.

2. Методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

3. Высокопроизводительный алгоритм построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.

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

Вклад автора в проведенное исследование.

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

Практическая значимость работы.

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

Структура и объем диссертации.

Диссертация состоит из введения, трёх глав, заключения, списка литературы, приложения и глоссария. Общий объем работы составляет 101 страница машинописного текста, 60 рисунков, 5 таблиц.

Заключение диссертации по теме «Геоинформатика», Нгуен Тхе Конг

Тоб = Т1 + Т2 = О (TVlog N) + О (Nlog АО = О (NlogN). (2.10) 2.5. ВЫВОДЫ ПО ГЛАВЕ

Алгоритм инкремента является самым простым алгоритмом. Идея алгоритма очень понятна и использует простую структуру данных. Если используется ацикличное дерево для хранения и поиска треугольника, тогда трудоёмкость алгоритма оценивается в среднем О(N log TV). Вычислительный алгоритм очень простой, особенно при окончании процесса построения триангуляции, когда существует дерево поиска треугольника. Эта проблема очень важна для процесса редактирования и анализа цифровых моделей рельефа, например, когда нужно вставить или удалить несколько точек, построить профили и т.д. Но всё-таки алгоритм зависит от распределения исходных данных, в худшем случае алгоритм инкремента может выполняться с трудоёмкостью О(N2).

Алгоритм заметающей линии Фортуне (Fortune's sweep-line) является одним из самых популярных методов ускорения для построения триангуляции. Алгоритм заметающей линии выполняется очень быстро с трудоёмкостью О(N log N). В алгоритме существует N событий точки, самое большее 2N-5 событий круга, но алгоритм требует использования очень сложных структур данных, например, нужна еще одна структура для

60

3. 2. ПРОЕКТИРОВАНИЕ СТРУКТУР ДАННЫХ

Выбор структуры для представления триангуляции оказывает существенное влияние на теоретическую трудоёмкость алгоритмов, а также на скорость конкретной реализации. Кроме того, выбор структуры может зависеть от цели дальнейшего использования триангуляции.

В триангуляции можно выделить 3 основных вида объектов: узлы (точки, вершины), рёбра (отрезки) и треугольники. Для простой операции мы выбираем структуру "Узлы и треугольники".

Type POINT3D //координат. X As Double Y As Double Z As Double

End Type

Type TRIANGLE iD (0 To 2) As Long //Указатель на узел (образующие узлы). iT (0 То 2) As Long /ГУказатель на соседние треугольники.

End Туре

В структуре "Узлы и треугольники" для каждого треугольника хранятся три указателя на образующие его узлы и три указателя на смежные треугольники (рис. 3.4) ч ч

Рис. 3.4. Связи треугольников структуры «Узлы и треугольники» памятью 3.0 Гб, работающим в операционной системе Windows ХР, приведём в таблице 3.3 и на рисунке (рис. 3.8).

ЗАКЛЮЧЕНИЕ

В диссертации выполнены теоретические и экспериментальные исследования, направленные на решение поставленных задач, способных решить проблемы, возникающие при вычислении алгоритмов. В итоге работы получены следующие результаты:

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

2. Исследованы алгоритмы инкремента и заметающей линии для построения триангуляции Делоне.

3. Предложены методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

4. Разработан новый и высокопроизводительный алгоритм построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.

5. Исследованы алгоритмы анализа поверхностей: построение профилей; построение горизонталей; построение изоконтуров; построение изоклин; расчет объемов земляных работ.

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

Автором разработан и протестирован пакет программ для обработки созданной триангуляционной модели:

- построение профилей;

- построение горизонтали;

- построение изоконтуров;

- построение изоклин;

- расчет объемов земляных работ.

Проводились сравнительные исследования скорости вычислений для различного количества исходных точек, которые подтвердили эффективность разработанного метода по сравнению с программой

82 конференции. Томск: Издательство Томского университета, 2000. С. 37-41.

10. Костюк IO.JL, Фукс A.JI. Приближенное вычисление оптимальной триангуляции // Геоинформатика. Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 61-66.

11. Ласло М. Вычислительная геометрия и компьютерная графика на С++: Пер. с англ. М.: БИНОМ, 1997. 304 с.

12. Майоров А. А., Нгуен Т. К. Перспективы развития компьютерных технологий создания цифровых моделей рельефа // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. № 4. С. 107-110.

13. Майоров А. А., Нгуен Т. К. Эффективный алгоритм построения триангуляции Делоне // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. № 1. С. 105-108.

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

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

16. Синицын С.И. Гибридный рекурсивно-инкрементный алгоритм построения триангуляции Делоне. Материалы конференции GraphiCon. Нижний Новгород. 2001.

17. Скворцов A.B. Триангуляция Делоне и ее применение. Томск. Издательство ТГУ. 2002.

18. Скворцов A.B., Костюк Ю.Л. Применение триангуляции для решения задач вычислительной геометрии // Геоинформатика: Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 127-138.

19. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 22—47.

20. Скворцов А.В., Поспелов П.И., Крысин С.П. Геоинформатика в дорожной отрасли (на примере IndorGIS). М.: Издательство МАДИ, 2005. 389 с.

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

22. Фукс А.Л. Предварительная обработка набора точек при построении триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 48-60.

23. Robert Sedgewick Cam nang thuat toan: Пер. с англ. NXB Khoa hoc Ky thuat, Thanh ph6 H6 Chi Minh, 1998. Том 1: 409 с. Том 2: 340 с.

24. Vera В. Anand Do hoa may tinh va mo hinh hoa hinh hoc: Пер. с англ. NXB Thanh ph6 Ho Chi Minh, 2000. 408 c.

25. Agarwal P.K., Suri S. Surface approximation and geometric partitions // Proc. 5th ACM-SIAM Symp. on Discrete Algorithms. 1994. P. 24-33.

26. De Floriani L. A pyramidal data structure for triangle-based surface description // IEEE Computer Graphics and Applications. 1989. Vol. 9. N. 2. P. 67-78.

27. De Floriani L., Falcidieno В., Nagy G., Pienovi C. On sorting triangles in a Delaynay tessellation // Algorithmica. 1991. N. 6. P. 522-535.

28. De Floriani L., Magillo P., Puppo E. Compressing Triangulated Irregular Networks // Geoinformatica. 2000. Vol. 1. N. 4. 67-88.

29. De Floriani L., Marzano P., Puppo E. Multiresolution Models for Topographic Surface Description // The Visual Computer. 1996. Vol. 12. N. 7. P. 317-345.

30. Evans F., Skiena S., Varshney A. Optimizing triangle strips for fast rendering//Proc. IEEE Visualization. 1996. P. 319-326.

31. Fowler R.J., Little J.J. Automatic extraction of irregular network digital terrain models // Computer Graphics. 1979. Vol. 13. N. 3. P. 199-207.

32. Gilbert P.N. New results on planar triangulations. Tech. Rep. ACT-15, Coord. Sci. Lab., University of Illinois at Urbana, July 1979.

33. 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.

34. Guttmann A., Stonebraker M. Using a Relational Database Management System for Computer Aided Design Data // IEEE Database Engineering.

1982. Vol. 5.N. 2.

35. Heller M. Triangulation algorithms for adaptive terrain modeling // Proc. of the 4th Intern. Symp. on Spatial Data Handling, July 1990. P. 163-174.

36. J. L. Bentley, B. W. Weide, and A. C. Yao. Optimal expected time algorithms for closest point problems. ACM Transactions on Mathematical Software, 6(4):563-580, 1980.

37. Kirkpatrik D.G. Optimal search in planar subdivisions // SIAM J. Comput.,

1983. Vol. 12. N. l.P. 28-35.

38. L. Guibas, D. Knuth, and M. Sharir. Randomized incremental construction of delaunay and voronoi diagrams. Algorithmica, 7:381^113, 1992.

39. Lawson C. Transforming triangulations // Discrete Mathematics. 1972. N. 3. P. 365-372.

40. Lee D. Proximity and reachability in the plane // Tech. Rep. N. R-831, Coordinated Sci. Lab. Univ. of Illinois at Urbana. 1978.

41. 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.

42. 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. N. 3. P. 267-285.

43. Lewis B., Robinson J. Triangulation of planar regions with applications // The Computer Journal. 1978. Vol. 21. N. 4. P. 324-332.

44. Lingas A. The Greedy and Delaunay triangulations are not bad. // Lect. Notes Comp. Sc. 1983. Vol. 158. P. 270-284.

45. Lloyd E. On triangulation of a set of points in the plain // MIT Lab. Comp. Sc. Tech. Memo. 1977. N. 88. 56 p.

46. M. T.Goodrich, J.-J. Tsay,D. E.Vengroff, , and J. S. Vitter. External-memory computational geometry. Symposium on Foundations of Computer Science, 34, 1993.

47. 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. l.P. 31-34.

48. Mark de Berg, Marc van Kreveld, Marc Overmars, Otfried Schwarzkopf Computational Geometry: algorithms and applications. 2nd edition. Springer-Verlag, 2000, 367 p., ISBN 3-540-65620-0.

49. McCullagh M.J., Ross C.G. Delaunay triangulation of a random data set for isarithmic mapping // The Cartographic Journal. 1980. Vol. 17. N. 2. P. 9399.

50. 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, February 1993.

51. Nagy G. Terrain visibility // Computers and Graphics. 1994. Vol. 18. N. 6.

52. P. Green and R. Sibson. Computing dirichlet tessellations in the plane. Computing Journal, 21:168-173, 1977.

53. Puppo E. Variable resolution triangulations // Computational Geometry. 1998. Vol. 11. P. 219-238.

54. R. A. Dwyer. A faster divide-and-conquer algorithm for constructing delaunay triangulations. Algorithmica, 2:137-151, 1987.

55. S. Fortune. A sweepline algorithm for voronoi diagrams. Algorithmica, 2:153-174, 1987.

56. S. Fortune. Numerical stability of algorithms for delaunay triangulations and voronoi diagrams. Annual ACM Symposium on Computational Geometry, 1992.

57. S. Fortune. Stable maintenance of point-set triangulations in two dimensions. IEEE Symposium on Foundations of Computer Science, pages 494-499, 1989.

58. 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.

59. Sibson R. Locally equiangular triangulations // Computer Journal. 1978. Vol.21.N.3.P. 243-245.

60. Sloan S.W. A fast algorithm, for constructing Delaunay triangulations in the plane // Adv. Eng. Software. 1987. Vol. 9. N. 1. P. 34-55.

61. Tourna G., Rossignac J. Geometric compression through topological surgery // ACM Transactions on Graphics. 1998. Vol. 17. N. 2. P. 84-115.

62. 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.

63. Zalik B. An efficient sweep-line Delaunay triangulation algorithm // Computer-Aided Design, (37) 2005, pp. 1027-1038.